HIV Prevention among Homeless Youth by Influence Maximization

Two young men laughing

HIV Prevention among Homeless Youth by Influence Maximization



Influence Maximization for Social Good Using Social Networks to Spread Health Based Information

This project focuses on the development of decision support systems for homeless youth drop-in center staff who need to find the most influential homeless youth to raise awareness about HIV (and other sexually transmitted infections) among their peers, and to drive the homeless youth community towards safer behaviors and lifestyles.

Over the past three years, we have been collaborating with drop-in agency staff and youth experiencing homelessness at Safe Place for Youth (SPY), the Los Angeles LGBT Center’s Youth Center on Highland, and My Friend’s Place.


HIV is a very serious infection 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. Internationally, 37 million people are living with HIV.

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.

In order to reduce the transmission of HIV, we are using a peer leader social network-based intervention, for information dissemination about HIV. Therefore, the key question is how can we identify the most “influential” youth, to be trained as peer leaders, 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.



Have You Heard? (HYH) focuses on the study of information diffusion 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.

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. 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. One of our primary foci in this project is to develop algorithms and tools that can be deployed in the real world.

Over the past three years, we have been collaborating with drop-in agency staff and youth experiencing homelessness at Safe Place for Youth (SPY), the Los Angeles LGBT Center’s Youth Center on Highland, and My Friend’s Place.




We, in our work, try to help homeless drop-in centers 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. Two major challenges are:

1) 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.  Their networks are constantly changing, and there is not a constant/consistent roster like a classroom of school children.

2) 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 overcome these 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 find out more about our techniques and algorithms, please have a look at our publications.



We conducted a 3-year study, which enrolled 718 young people experiencing homelessness at 3 Los Angeles area drop-in centers–My Friend’s Place, Safe Place for Youth, and the Los Angeles LGBT Center’s Youth Center on Highland.  This study is using the CHANGE algorithm, created by our team members.

CHANGE uses social network data is that is gathered via in-person interviews with a subsample of the youth.  Specifically, we randomly sample about 10% of the youth and then, for each of them, randomly sample one of their friends.  This allows us to begin to identify the network of homeless young persons accessing services at each drop-in center.   We use a combination of state-of-the-art techniques from Artificial Intelligence, Sequential Planning, Decision Theory and Mathematics to then identify who are the most influential youth, based on their positions within the network, to then train as peer leaders.

Flowchart of techniques used in the CHANGE algorithm

Diagram about observations, CHANGE agent and Actions

The results from this trial show that youth in the CHANGE arm of the intervention experience statistically significant improvements in their risk of engaging in unprotected sex compared to youth enrolled in an observation-only control group. We also observe a tendency towards larger and faster decrease in rates of unprotected sex in youth in the CHANGE arm compared to youth who receive an intervention where the highest degree nodes in the network are chosen as peer leaders.

Diagram about observations, CHANGE agent and Actions




We deployed an algorithm named HEALER in the real world at Safe Place for Youth–a homeless drop-in center 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.

Computer room


Clinical trial of an AI-augmented intervention for HIV prevention in youth experiencing homelessness 

Having developed an artificial intelligence system to optimize social network interventions in a community health setting, to maximize the spread of information through peer leaders, in this work,  we conducted a field trial enrolling 713 Youth Experiencing Homelessness (YEH) at drop-in centers in a large US city. The field trial compared interventions planned with the algorithm to those where the highest-degree nodes in the youths’ social network were recruited as peer leaders (the standard method in public health) and to an observation-only control group. Results from the field trial show that youth in the AI group experience statistically significant reductions in key risk behaviors for HIV transmission, while those in the other groups do not. This provides, to our knowledge, the first empirical validation of the usage of AI methods to optimize social network interventions for health. We also discuss lessons learned over the course of this project which may inform future attempts to use AI in community-level interventions.

Read more in our AAAI 2021 paper.




California HIV/AIDS Research Program
The California HIV/AIDS Research Program (CHRP) logo

Army Research Office



Eric Rice, Bryan Wilder, Laura Onasch-Vera, Graham Diguiseppi, Robin Petering, Chyna Hill, Amulya Yadav, Sung-Jae Lee, and Milind Tambe. 6/21/2021. “A Peer-Led, Artificial Intelligence-Augmented Social Network Intervention to Prevent HIV among Youth Experiencing Homelessness.” to appear in the Journal of Acquired Immune Deficiency Syndrome (JAIDS).Abstract
Youth experiencing homelessness (YEH) are at elevated risk for HIV/AIDS and disproportionately identify as racial, ethnic, sexual, and gender minorities. We developed a new peer change agent (PCA) HIV prevention intervention with three arms: (1) an arm using an Artificial Intelligence (AI) planning algorithm to select PCAs; (2) a popularity arm, the standard PCA approach, operationalized as highest degree centrality (DC); and (3) an observation-only comparison group.
Amulya Yadav, Leandro Marcolino, Eric Rice, Robin Petering, Hailey Winetrobe, Harmony Rhoades, Milind Tambe, and Heather Carmichael. 2015. “Preventing HIV Spread in Homeless Populations Using PSINET.” In Conference on Innovative Applications of Artificial Intelligence (IAAI-15).Abstract
Homeless youth are prone to HIV due to their engagement in high risk behavior. Many agencies conduct interventions to educate/train a select group of homeless youth about HIV prevention practices and rely on word-of-mouth spread of information through their social network. Previous work in strategic selection of intervention participants does not handle uncertainties in the social network’s structure and in the evolving network state, potentially causing significant shortcomings in spread of information. Thus, we developed PSINET, a decision support system to aid the agencies in this task. PSINET includes the following key novelties: (i) it handles uncertainties in network structure and evolving network state; (ii) it addresses these uncertainties by using POMDPs in influence maximization; (iii) it provides algorithmic advances to allow high quality approximate solutions for such POMDPs. Simulations show that PSINET achieves ∼60% more information spread over the current state-of-the-art. PSINET was developed in collaboration with My Friend’s Place (a drop-in agency serving homeless youth in Los Angeles) and is currently being reviewed by their officials.
Amulya Yadav, Ece Kamar, Barbara Grosz, and Milind Tambe. 2016. “HEALER: POMDP Planning for Scheduling Interventions among Homeless Youth (Demonstration).” In International conference on Autonomous Agents and Multiagent Systems.Abstract
Adaptive software agents like HEALER have been proposed in the literature recently to recommend intervention plans to homeless shelter officials. However, generating networks for HEALER’s input is challenging. Moreover, HEALER’s solutions are often counter-intuitive to people. This demo paper makes two contributions. First, we demonstrate HEALER’s Facebook application, which parses the Facebook contact lists in order to construct an approximate social network for HEALER. Second, we present a software interface to run human subject experiments (HSE) to understand human biases in recommendation of intervention plans. We plan to use data collected from these HSEs to build an explanation system for HEALER’s solutions.
Amulya Yadav, Hau Chan, Albert Jiang, Eric Rice, Ece Kamar, Barbara Grosz, and Milind Tambe. 2016. “POMDPs for Assisting Homeless Shelters - Computational and Deployment Challenges.” In AAMAS 2016 IDEAS Workshop.Abstract
This paper looks at challenges faced during the ongoing deployment of HEALER, a POMDP based 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. In order to compute its plans, HEALER (i) 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) and constructs social networks of homeless youth at low cost, using a Facebook application. HEALER is currently being deployed in the real world in collaboration with a homeless shelter. Initial feedback from the shelter officials has been positive but they were surprised by the solutions generated by HEALER as these solutions are very counterintuitive. Therefore, there is a need to justify HEALER’s solutions in a way that mirrors the officials’ intuition. In this paper, we report on progress made towards HEALER’s deployment and detail first steps taken to tackle the issue of explaining HEALER’s solutions.
Leandro Soriano Marcolino, Aravind Lakshminarayanan, Amulya Yadav, and Milind Tambe. 2016. “Simultaneous Influencing and Mapping Social Networks (Extended Abstract).” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
Influencing a social network is an important technique, with potential to positively impact society, as we can modify the behavior of a community. For example, we can increase the overall health of a population; Yadav et al. (2015) [4], for instance, spread information about HIV prevention in homeless populations. However, although influence maximization has been extensively studied [2, 1], their main motivation is viral marketing, and hence they assume that the social network graph is fully known, generally taken from some social media network. However, the graphs recorded in social media do not really represent all the people and all the connections of a population. Most critically, when performing interventions in real life, we deal with large degrees of lack of knowledge. Normally the social agencies have to perform several interviews in order to learn the social network graph [3]. These highly unknown networks, however, are exactly the ones we need to influence in order to have a positive impact in the real world, beyond product advertisement. Additionally, learning a social network graph is very valuable per se. Agencies need data about a population, in order to perform future actions to enhance their well-being, and better actuate in their practices [3]. As mentioned, however, the works in influence maximization are currently ignoring this problem. Each person in a social network actually knows other people, including the ones she cannot directly influence. When we select someone for an intervention (to spread influence), we also have an opportunity to obtain knowledge. Therefore, in this work we present for the first time the problem of simultaneously influencing and mapping a social network. We study the performance of the classical influence maximization algorithm in this context, and show that it can be arbitrarily low. Hence, we study a class of algorithms for this problem, performing an experimentation using four real life networks of homeless populations. We show that our algorithm is competitive with previous approaches in terms of influence, and is significantly better in terms of mapping.
  • 1 of 3
  • »