PSINET - An Online POMDP Solver for HIV Prevention in Homeless Populations

Amulya Yadav, Leandro Soriano Marcolino, Eric Rice, Robin Petering, Hailey Winetrobe, Harmony Rhoades, Milind Tambe, Heather CarmichaelLancaster 2015

Abstract

Homeless youth are at high risk for HIV. Non-profit agencies conduct peer-led interventions, relying on word-of-mouth spread of information. Strategic participant selection is difficult due to uncertainties in social network structure and state. We developed PSINET, a decision support system that models this problem as a Partially Observable Markov Decision Process (POMDP). PSINET achieves 60% more information spread than current state-of-the-art methods and scales to real-world network sizes where traditional solvers fail.

Introduction

In urban centers like Los Angeles, homeless youth face significant barriers to healthcare. Peer-led interventions are a vital tool for HIV prevention, where a small group of "influencers" is trained to educate their social circles. The core technical challenge is influence maximization under uncertainty: selecting the best influencers when the social network is only partially known and constantly evolving.

The PSINET Framework

PSINET is an online POMDP solver designed for social interventions. It addresses the massive state space of social networks through several key innovations:

  • Heuristic Transition Probabilities: Uses a "diffusion vector" to estimate the likelihood of information spread, avoiding the need to compute every possible path.
  • QMDP + Monte-Carlo Sampling: Samples potential network structures and uses the QMDP heuristic to pick the best immediate action, preventing the search tree from becoming unmanageable.
  • Voting Mechanisms: Generates multiple network instances that "vote" on participant selection. The PSINET-W variant weights these votes by the probability of the network structure, providing the best balance of speed and quality.
Figure 3: PSINET-W robustness to propagation probability and scaling of nodes per round.

Key Results and Scalability

Evaluations on real-world data from "My Friend’s Place" in Los Angeles show that PSINET significantly outperforms traditional baselines.

Superior Information Spread

PSINET-W achieves approximately 60% more indirect influence spread than Degree Centrality (DC), the current industry standard. By "looking ahead," PSINET avoids redundant selections within the same social cluster, instead targeting "bridge" nodes that connect different communities.

Scalability and Robustness

While standard POMDP solvers like POMCP run out of memory on networks with just 30 nodes, PSINET scales to networks with nearly 200 nodes. Furthermore, as shown in Figure 3, the algorithm is robust to noise in the estimated propagation probabilities between individuals.

Figure 4: Solution quality and scalability comparison. Note that POMCP fails to scale beyond 30 nodes.

Conclusion

PSINET demonstrates the power of POMDPs in addressing real-world social challenges. By accounting for network uncertainty and providing scalable approximate solutions, it offers a practical tool for non-profits to maximize the impact of life-saving HIV prevention programs. Future work will focus on refining network data collection and ensuring the social suitability of selected influencers.

Summary updated

Abstract

Homeless youth are prone to Human Immunodeficiency Virus (HIV) due to their engagement in high risk behavior such as unprotected sex, sex under influence of drugs, etc. Many non-profit agencies conduct interventions to educate and train a select group of homeless youth about HIV prevention and treatment 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 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; and (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.
BibTeX
@inproceedings{yadav2015psinet,
  author = {Amulya Yadav and Leandro Soriano Marcolino and Eric Rice and Robin Petering and Hailey Winetrobe and Harmony Rhoades and Milind Tambe and Heather Carmichael},
  title = {{PSINET - An Online POMDP Solver for HIV Prevention in Homeless Populations}},
  booktitle = {Lancaster},
  year = {2015},
}
Figure