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.
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.
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