Influence Maximization for Social Good

This project focuses on the study of diffusion processes in social networks of hard to reach populations (such as homeless youth) in order to spread information and raise general levels of awareness about dangerous diseases (such as HIV) among such populations. On a humanitarian level, the end goal of this project is to reduce rates of HIV infection among disadvantaged populations by influencing and inducing behavior change in homeless youth populations that drives them towards safer practices, such as regular HIV testing, etc. On a scientific level, the goal is not only to model these influence spread phenomena, but to also develop decision support systems (and the necessary tools/algorithms/mechanisms) using which information can be spread in the social networks of homeless youth in the most efficient manner. Our primary focus in this project is to develop algorithms and tools which are actually usable and deployable in the real world, i.e., algorithms which can actually benefit society for good. In fact, we strive to validate all our models, algorithms and techniques in the real world by testing it out with actual homeless youth (specifically youth in Los Angeles). Over the past three years, we have been collaborating with social workers from Safe Place for Youth (SPY) and My Friend’s Place (homeless shelters in Los Angeles) to understand the problems that they face in raising awareness about HIV (and other STDs) among homeless youth, come up with innovative ways to solve their problems, and finally test out our algorithms by doing pilot deployment studies with actual homeless youth.

MOTIVATION:

Best Video and Best Student Video at AAAI 2017 Video Competition




Field Research
Field Research
HIV-AIDS is a very dangerous disease that sees no race, no color, no gender, no economic background and not even a specific age group. It can affect anyone, at any time if they put themselves in a situation where they could be at risk. HIV-AIDS kills 2 million people worldwide every year. In USA alone, AIDS kills around 10,000 people per annum. HIV has an extremely high incidence among homeless youth, as they are more likely to engage in high HIV-risk behaviors (e.g., unprotected sexual activity, injection drug use) than other sub-populations. In fact, previous studies show that homeless youth are at 16X greater risk of HIV infection than stably housed populations. Thus, any attempt at eradicating HIV crucially depends on our success at minimizing rates of HIV infection among homeless youth. As a result, many homeless shelters (including our collaborators SPY and My Friend’s Place) organize intervention camps for homeless youth in order to raise awareness about HIV prevention and treatment practices. These intervention camps consist of day-long educational sessions in which the participants are provided with information about HIV prevention measures. However, due to financial/manpower constraints, the shelters cannot intervene on the entire target (homeless youth) population. Instead, they try to maximize the spread of awareness among the target population (via word-of-mouth influence) using the limited resources at their disposal. To achieve this goal, the shelter uses the friendship based social network of the target population to strategically choose the participants of their limited intervention camps. Therefore, the key question is how can we, as computer scientists, help these shelters in finding the most "influential" youth from the social network of homeless youth? We want to find the youth who can spread awareness about HIV and induce behavior change among their peers, in the quickest and most efficient possible manner. Finding these "influential" youth will enable homeless shelters to focus their precious time/manpower on the correct youth, who are likely to achieve more information spread than any other possible choice of youth.

Heather Carmichael and team in the field conducting interventions for homeless youth

Field Research
Field Research


Friendship based social network of homeless people visiting My Friend's Place


Field Research

RESEARCH OVERVIEW:

We, in our work, try to help homeless shelters use their resources more effectively by modeling this entire problem of selecting the most influential youth as an Influence Maximization Problem, which is a widely studied problem in the field of Artificial Intelligence. However, most previous work in this area has failed at addressing some key challenges that show up in the real world. Specifically, there are 4 major challenges, out of which we highlight two here. First, constructing social networks of homeless youth is a big challenge, since these youth are a hard-to-reach population, and mapping out their social circles requires a lot of time and money. Second, even if we are able to construct these networks, there is always noise in the data collection procedure, which leads to uncertainty about the true structure of the social network. This uncertainty needs to be accounted before deciding who is “influential” in the social network and who isn’t To address the first challenge, we have developed a Facebook application which parses Facebook contact lists of homeless youth to create a first approximation of the social network. On top of that, we use state-of-the-art link prediction techniques to infer additional friendships in between the homeless youth. To address the second and other challenges, we use a combination of state-of-the-art techniques from Artificial Intelligence, Sequential Planning, Decision Theory and Mathematics (that we developed in our lab) in order to overcome these challenges. In order to find out more about our techniques and algorithms, please have a look at our publications.

Flowchart of techniques used in PSINET: Our solver

Field Research
Field Research


HEALER:


Healer Image
HEALER is an adaptive decision support system which has two components: a Facebook application and HEAL, the core algorithm that powers HEALER. Before the homeless shelter begins its interventions, HEALER's Facebook application interacts with homeless youth to parse their contact lists on Facebook in order to generate an approximation of the friendship based social network that connects these youth. This network is then refined by running state-of-the-art link prediction techniques, in order to infer potential friendships, which may not be present on Facebook. This refined network is then passed onto HEAL, the core algorithm that powers HEALER. It uses a combination of state-of-the-art techniques from Artificial Intelligence, Sequential Planning, Online Learning, Decision Theory and Mathematics (which we developed in our lab) to generate recommendations about which homeless youth should be chosen as intervention attendees. The shelter official acts on that recommendation by conducting the intervention with the selected youth. After the intervention, HEALER incorporates real-time feedback provided by shelter officials (about what happened during the intervention) to update its decision making policy for future interventions. To learn more about how HEALER works, please refer to our publications.

PILOT STUDY:


Pilot Study
Pilot Study
We have deployed HEALER in the real world by conducting a pilot study recently with Safe Place for Youth, a homeless shelter in Venice Beach, Los Angeles. Safe Place for Youth provides free food and clothing to homeless youth of the ages 12-25, three times a week. We enrolled 62 homeless youth from this shelter into our study and we conducted three test interventions. We used HEALER’s Facebook application to generate the network (see figure below) that connected these youth. Each number here is a homeless youth (their names have been replaced by numbers to protect their anonymity), and the edges between them represent their friendships. The results from this pilot were very promising. We found that HEALER was able to spread information to almost 66% of homeless youth in the network (one month after interventions had ended). This shows that HEALER is successful at finding the most influential youth in the network. More importantly, we found that due to HEALER’s interventions, there was a 25% self-reported increase in the number of homeless youth who get tested for HIV regularly. Thus, HEALER was successful in inducing behavior change among the youth as well. We are currently conducting a second pilot study to further test our algorithms. We also plan to conduct a much larger study with 900 homeless youth in Spring 2017. A very long term goal of ours is to introduce HEALER in homeless shelters across the country, which could potentially change the way health interventions work. If you are interested and would like to contribute, feel free to talk to us!



Social Network of 62 homeless youth in Safe Place for Youth

Pilot Study
Pilot Study

AWARDS:

Pragnesh Jay Modi Best Student Paper Award at the International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2016
Most Visionary Paper Award at the International Workshop on Issues with Deployment of Emerging Agent Based Systems (IDEAS) 2016

MEDIA:


Mashable News, December 20, 2015: Incredible innovations that improved the world in 2015.
Mashable News, February 6, 2015: How an algorithm could help spread HIV information among homeless teens.
My Friend's Place, February 23, 2015: My Friend's Place and USC Partner to Prevent Spread of HIV.
Next City News, February 18, 2015: Can an algorithm help prevent HIV from Spreading Among Homeless Young People?
Motherboard News, February 4, 2015: Artificial Intelligence Could Help Reduce HIV Among Homeless Youths.
USC Press Release, January 27, 2015: USC Social Work Professors Team With Computer Scientists to Prevent HIV Spread Among Homeless Youth.

PUBLICATIONS:

Feb, 2017

Amulya Yadav, Bryan Wilder, Robin Petering, Eric Rice, Milind Tambe Influence Maximization in the Field: The Arduous Journey from Emerging to Deployed Application In Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems (AAMAS)

Feb, 2017

Bryan Wilder, Amulya Yadav, Nicole Immorlica, Eric Rice, Milind Tambe Uncharted but not Uninfluenced: Influence Maximization with an Uncertain Network In International Conference on Autonomous Agents and Multi-agent Systems (AAMAS)

May, 2016

Amulya yadav, Hau Chan, Albert Jiang, Haifeng Xu, Eric Rice, Milind Tambe Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization Under Uncertainty In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).(Winner of the Pragnesh Jay Modi Best Student Paper Award).

May, 2016

Amulya yadav, Hau Chan , Albert Jiang , Eric Rice, Ece Kamar , Barbara Grosz, Milind Tambe POMDPs for Assisting Homeless Shelters - Computational and Deployment Challenges In Proceedings of the IDEAS Workshop in International Conference on Autonomous Agents and Multiagent Systems (AAMAS). (Winner of Most Visionary Paper Award)

May, 2016

Leandro Marcolino, Aravind Laskhminarayanan, Amulya Yadav, Milind Tambe Simultaneous Influencing and Mapping Social Networks (Extended Abstract) In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

May, 2016

Amulya yadav, Ece Kamar , Barbara Grosz , Milind Tambe HEALER: POMDP Planning for Scheduling Interventions among Homeless Youth (Demonstration) In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

Jan, 2015

Amulya Yadav , Leandro Marcolino, Eric Rice, Robin Petering, Hailey Winetrobe, Harmony Rhoades, Milind Tambe, Heather carmichael Preventing HIV Spread in Homeless Populations using PSINET In Proceedings of the Annual Conference on Innovative Applications of Artificial Intelligence (IAAI).