research-article

Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty

Authors:

Albert Xin Jiang,

Milind TambeAuthors Info & Claims

AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

Pages 740 - 748

Published: 09 May 2016 Publication History

Abstract

This paper presents HEALER, a software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER's sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. While previous work presents influence maximizing techniques to choose intervention participants, they do not address three real-world issues: (i) they completely fail to scale up to real-world sizes; (ii) they do not handle deviations in execution of intervention plans; (iii) constructing real-world social networks is an expensive process. HEALER handles these issues via four major contributions: (i) HEALER casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable real-world sizes; (ii) HEALER allows shelter officials to modify its recommendations, and updates its future plans in a deviation-tolerant manner; (iii) HEALER constructs social networks of homeless youth at low cost, using a Facebook application. Finally, (iv) we show hardness results for the problem that HEALER solves. HEALER will be deployed in the real world in early Spring 2016 and is currently undergoing testing at a homeless shelter.

References

[1]

C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing Social Influence in Nearly Optimal Time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 946--957. SIAM, 2014.

Digital Library

[2]

CDC. HIV Surveillance Report. www.cdc.gov/hiv/pdf/g-l/hiv_surveillance_report_vol_25.pdf, Mar. 2013.

[3]

E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based Influence Maximization and Computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 629--638. ACM, 2014.

Digital Library

[4]

J.-P. Cointet and C. Roth. How Realistic Should Knowledge Diffusion Models Be? Journal of Artificial Societies and Social Simulation, 10(3):5, 2007.

[5]

N. H. Council. HIV/AIDS among Persons Experiencing Homelessness: Risk Factors, Predictors of Testing, and Promising Testing Strategies. www.nhchc.org/wp-content/uploads/2011/09/InFocus_Dec2012.pdf, Dec. 2012.

[6]

A. Eck and L.-K. Soh. To Ask, Sense, or Share: Ad Hoc Information Gathering. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 367--376. International Foundation for Autonomous Agents and Multiagent Systems, 2015.

Digital Library

[7]

D. Golovin and A. Krause. Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization. Journal of Artificial Intelligence Research, 42:427--486, 2011.

Digital Library

[8]

J. A. Kelly, D. A. Murphy, K. J. Sikkema, T. L. McAuliffe, R. A. Roffman, L. J. Solomon, R. A. Winett, and S. C. Kalichman. Randomised, Controlled, Community-Level HIV-Prevention Intervention for Sexual-Risk Behaviour among Homosexual men in US cities. The Lancet, 350(9090):1500, 1997.

[9]

D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the Spread of Influence through a Social Network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137--146. ACM, 2003.

Digital Library

[10]

M. Kim and J. Leskovec. The Network Completion Problem: Inferring Missing Nodes and Edges in Networks. In Proceedings of the SIAM Conference on Data Mining. SIAM, 2011.

[11]

L. Kocsis and C. Szepesvári. Bandit based Monte-Carlo Planning. In Machine Learning: ECML 2006, pages 282--293. Springer, 2006.

Digital Library

[12]

D. LaSalle and G. Karypis. Multi-threaded Graph Partitioning. In Parallel & Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on, pages 225--236. IEEE, 2013.

Digital Library

[13]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420--429. ACM, 2007.

Digital Library

[14]

M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2009.

Digital Library

[15]

E. Rice. The Positive Role of Social Networks and Social Networking Technology in the Condom-using Behaviors of Homeless Young People. Public health reports, 125(4):588, 2010.

[16]

E. Rice, A. Barman-Adhikari, N. G. Milburn, and W. Monro. Position-specific HIV risk in a Large Network of Homeless Youths. American journal of public health, 102(1):141--147, 2012.

[17]

E. Rice, A. Fulginiti, H. Winetrobe, J. Montoya, A. Plant, and T. Kordic. Sexuality and Homelessness in Los Angeles public schools. American Journal of Public Health, 102, 2012.

[18]

E. Rice, E. Tulbert, J. Cederbaum, A. B. Adhikari, and N. G. Milburn. Mobilizing Homeless Youth for HIV Prevention: a Social Network Analysis of the Acceptability of a face-to-face and Online Social Networking Intervention. Health education research, 27(2):226, 2012.

[19]

S. Ross, J. Pineau, S. Paquet, and B. Chaib-Draa. Online Planning Algorithms for POMDPs. Journal of Artificial Intelligence Research, pages 663--704, 2008.

Digital Library

[20]

J. A. Schneider, A. N. Zhou, and E. O. Laumann. A new HIV Prevention Network Approach: Sociometric Peer Change Agent Selection. Social Science & Medicine, 125:192--202, 2015.

[21]

D. Silver and J. Veness. Monte-Carlo Planning in large POMDPs. In Advances in Neural Information Processing Systems, pages 2164--2172, 2010.

Digital Library

[22]

A. Somani, N. Ye, D. Hsu, and W. S. Lee. DESPOT: Online POMDP Planning with Regularization. In Advances In Neural Information Processing Systems, pages 1772--1780, 2013.

[23]

Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-Optimal Time Complexity meets Practical Efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75--86. ACM, 2014.

Digital Library

[24]

UNAIDS. Report on the Global AIDS Epidemic. www.unaids.org/en/resources/campaigns/20121120_globalreport2012/globalreport/, Mar. 2012.

[25]

T. W. Valente and P. Pumpuang. Identifying Opinion Leaders to Promote Behavior Change. Health Education & Behavior, 2007.

[26]

A. Yadav, H. Chan, A. Jiang, H. Xu, E. Rice, and M. Tambe. Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty - an extended version. arXiv:1602.00165, 2016.

Digital Library

[27]

A. Yadav, L. Marcolino, E. Rice, R. Petering, H. Winetrobe, H. Rhoades, M. Tambe, and H. Carmichael. Preventing HIV Spread in Homeless Populations Using PSINET. In Proceedings of the Twenty-Seventh Conference on Innovative Applications of Artificial Intelligence (IAAI-15), 2015.

Digital Library

[28]

Q. Yan, S. Guo, and D. Yang. Influence Maximizing and Local Influenced Community Detection based on Multiple Spread Model. In Advanced Data Mining and Applications, pages 82--95. Springer, 2011.

Digital Library

[29]

S. D. Young and E. Rice. Online Social Networking Technologies, HIV knowledge, and Sexual Risk and Testing Behaviors among Homeless Youth. AIDS and Behavior, 15(2):253--260, 2011.

Cited By

Tabar MPark HWinkler SLee DBarman-Adhikari AYadav AGupta RLiu YShah MRajan STang JPrakash B(2020)Identifying Homeless Youth At-Risk of Substance Use DisorderProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403360(3092-3100)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403360
Ko JLee KShin KPark NAlhajj R(2020)MONSTORProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381460(204-211)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381460
Rahmattalabi AVayanos PFulginiti ATambe MElkind EVeloso MAgmon NTaylor M(2019)Robust Peer-Monitoring on Graphs with an Application to Suicide Prevention in Social NetworksProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3332046(2168-2170)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3332046
Show More Cited By

Index Terms

Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Influence Maximization in the Field: The Arduous Journey from Emerging to Deployed Application
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

This paper focuses on a topic that is insufficiently addressed in the literature, i.e., challenges faced in transitioning agents from an emerging phase in the lab, to a deployed application in the field. Specifically, we focus on challenges faced in ...
Gender differences in the addiction to social networks in the Southern Spanish university students
Graphical abstract

Display Omitted
Highlights
- The prevalence of addiction to social media is rising among male and female young people.
Abstract
Social networks sites have become the most popular instrument used to communicate and exchange information resulting in the addiction to this media. Previous studies suggested that personal characters play an essential role in ...
Racial Homophily and Its Persistence in Newcomers' Social Networks

This study examined the formation and persistence of homophilous, or same-race, friendship ties among racial minorities and whites in a "newcomer" setting. Homophilous ties provide valuable sources of mutual support but may limit racial minorities' ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

May 2016

1580 pages

ISBN:9781450342391

General Chairs:
Catholijn M. Jonker
TU Delft, Netherlands
,
Stacy Marsella
University of Southern California, USA
,
Program Chairs:
John Thangarajah
RMIT University. Australia
,
Karl Tuyls
University of Liverpool, UK

Sponsors

IFAAMAS

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 09 May 2016

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NIMH
MURI

Conference

AAMAS '16

Sponsor:

AAMAS '16: International Conference on Agents and Multiagent Systems

May 9 - 13, 2016

Singapore, Singapore

Acceptance Rates

AAMAS '16 Paper Acceptance Rate 137 of 550 submissions, 25%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
216
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tabar MPark HWinkler SLee DBarman-Adhikari AYadav AGupta RLiu YShah MRajan STang JPrakash B(2020)Identifying Homeless Youth At-Risk of Substance Use DisorderProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403360(3092-3100)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403360
Ko JLee KShin KPark NAlhajj R(2020)MONSTORProceedings of the 12th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1109/ASONAM49781.2020.9381460(204-211)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1109/ASONAM49781.2020.9381460
Rahmattalabi AVayanos PFulginiti ATambe MElkind EVeloso MAgmon NTaylor M(2019)Robust Peer-Monitoring on Graphs with an Application to Suicide Prevention in Social NetworksProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3332046(2168-2170)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3332046
Mothilal RYadav ASharma AChen JMankoff JGomes C(2019)Optimizing peer referrals for public awareness using contextual banditsProceedings of the 2nd ACM SIGCAS Conference on Computing and Sustainable Societies10.1145/3314344.3332497(74-85)Online publication date: 3-Jul-2019
https://dl.acm.org/doi/10.1145/3314344.3332497
Tang JHuang KXiao XLakshmanan LTang XSun ALim ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)Efficient Approximation Algorithms for Adaptive Seed MinimizationProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319881(1096-1113)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319881
Yadav AWilder BRice EPetering RCraddock JYoshioka-Maxwell AHemler MOnasch-Vera LTambe MWoo D(2018)Bridging the gap between theory and practice in influence maximizationProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304774(5399-5403)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304774
Yadav ANoothigattu RRice EOnasch-Vera LSoriano Marcolino LTambe MAndre EKoenig SDastani MSukthankar G(2018)Please be an Influencer?Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237912(1423-1431)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237912
Wilder BOnasch-Vera LHudson JLuna JWilson NPetering RWoo DTambe MRice EAndre EKoenig SDastani MSukthankar G(2018)End-to-End Influence Maximization in the FieldProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237911(1414-1422)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237911
De ABhattacharya SGanguly NAndre EKoenig SDastani MSukthankar G(2018)Shaping Opinion Dynamics in Social NetworksProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237899(1336-1344)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237899
Wilder BOu Hde la Haye KTambe MAndre EKoenig SDastani MSukthankar G(2018)Optimizing Network Structure for Preventative HealthProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237507(841-849)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237507
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents