Magazine article AI Magazine

PSINET: Assisting HIV Prevention among Homeless Youth by Planning Ahead

Magazine article AI Magazine

PSINET: Assisting HIV Prevention among Homeless Youth by Planning Ahead

Article excerpt

Homelessness affects around 2 million youths in the United States annually, 11 percent of whom are infected with the human immunodeficiency virus (HIV), which is 10 times the rate of infection in the general population (Aidala and Sumartojo 2007). Peer-led HIV prevention programs such as Popular Opinion Leader (POL) (Kelly et al. 1997) try to spread HIV prevention information through network ties and recommend selecting intervention participants based on degree centrality (that is, nodes with the most number of friendships picked first). Such peer-led programs are highly desirable to agencies working with homeless youth as these youth are often disengaged from traditional health-care settings and are distrustful of adults (Rice and Rhoades 2013, Rice 2010).

Agencies working with homeless youth prefer a series of small-size interventions deployed sequentially as they have limited personnel to direct toward these programs. This fact, along with the emotional and behavioral problems of youth, makes managing groups of more than five or six young people at a time very difficult (Rice et al. 2012b). Strategically choosing intervention participants is important so that information percolates through their social network in the most efficient way.

The purpose of this article is to introduce partially observable Markov decision process (POMDP)-based social interventions in networks for enhanced HIV treatment (PSINET), a novel system that chooses the participants of successive interventions in a social network. The key novelty of our work is a unique combination of POMDPs and influence maximization to handle uncertainties about friendships between people in the social network; and the evolution of the network state in between two successive interventions. Traditionally, influence maximization has not dealt with these uncertainties, which greatly complicates the process of choosing intervention participants. Moreover, this problem is a very good fit for POMDPs as we conduct several interventions sequentially, similar to sequential actions taken in a POMDP; and we must handle uncertainty over network structure and evolving state, similar to partial observability over states in a POMDP.

However, there are scalability issues that must be addressed. Unfortunately, our POMDP's state (2300 states) and action (150 10) actions) spaces are beyond the reach of current state-of-the-art POMDP solvers and algorithms. To address this scaleup challenge, PSINET provides a novel online approximation algorithm that relies on the following key ideas: (1) compact representation of transition probabilities (explained later) to manage the intractable state and action spaces; (2) combination of the QMDP heuristic (a well known offline approximate solver) with Monte Carlo simulations to avoid exhaustive search of the entire belief space; and (3) voting on multiple POMDP solutions, each of which efficiently searches a portion of the solution state space to improve accuracy. Each such POMDP solution (which votes for the final solution) is a decomposition of the original problem into a simpler problem. Thus, PSINET efficiently searches the combinatorial state and action spaces based on several heuristics in order to come up with good solutions.

Our work is done in collaboration with My Friend's Place (MFP),1 a nonprofit agency assisting Los Angeles's homeless youth to build self-sufficient lives by providing education and support to reduce high-risk behavior. Our collaborators conducted extensive interviews with homeless youth at My Friend's Place to ascertain the structure of their friendship-based social networks. Therefore, we evaluate PSINET on real social networks of youth attending this agency. This work is being reviewed by officials at My Friend's Place toward final deployment.

Related Work

There are three primary areas of related work that we discuss in this section. First, we discuss work in the field of influence maximization, which was first explored by Kempe, Kleinberg, and Tardos (2003), who provided a constant-ratio approximation algorithm to find "seed" sets of nodes that can optimally spread influence in a graph. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed


An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.