Bridging the Gap Between Theory and Practice in Influence Maximization: Raising Awareness about HIV among Homeless Youth

1 Introduction

The nearly two million homeless youth in the United States [Toro et al., 2007] are at high risk of contracting Human Immunodeficiency Virus (HIV) [Pfeifer and Oliver, 1997]. In fact, homeless youth are twenty times more likely to be HIV positive than stably housed youth, due to high-risk behaviors that they engage in (such as unprotected sex, exchange sex, sharing drug needles, etc.) [CDC, 2013; Council, 2012]. Given the important role that peers play in these high-risk behaviors of homeless youth [Rice et al., 2012a; Green et al., 2013], it has been suggested that peer leader based interventions for HIV prevention be developed for these youth [Arnold and Rotheram-Borus, 2009; Rice et al., 2012a; Green et al., 2013].

As a result, many homeless youth service providers (henceforth just "service providers") conduct peer-leader based social network interventions [Rice, 2010], where a select group of homeless youth are trained as peer leaders. This peer-led approach is particularly desirable because service providers have limited resources and homeless youth tend to distrust adults. The training program of these peer leaders includes detailed information about how HIV spreads and what one can do to prevent infection. The peer leaders are also taught effective ways of communicating this information to their peers [Rice et al., 2012b].

1Amulya Yadav (amulyaya@usc.edu) is the contact author

Because of their limited financial and human resources, service providers can only train a small number of these youth and not the entire population. Thus, the selected peer leaders in these interventions are tasked with spreading messages about HIV prevention to their peers in their social circles, thereby encouraging them to adopt safer practices. Using these interventions, service providers aim to leverage social network effects to spread information about HIV, and induce behavior change (increased HIV testing) among people in the homeless youth social network.

In fact, there are further constraints that service providers face - behavioral struggles of homeless youth means that service providers can only train 3-4 peer leaders in every intervention. This leads us to do sequential training; where groups of 3-4 homeless youth are called one after another for training. They are trained as peer leaders in the intervention, and are asked information about friendships that they observe in the real-world social network. This newer information about the social network is then used to improve the selection of the peer leaders for the next intervention. As a result, the peer leaders for these limited interventions need to be chosen strategically so that awareness spread about HIV is maximized in the social network of homeless youth.

Previous work proposed HEALER [Yadav et al., 2016] and DOSIM [Wilder et al., 2017], two agents which assist service providers in optimizing their intervention strategies. These agents recommend "good" intervention attendees, i.e., homeless youth who maximize HIV awareness in the realworld social network of youth. In essence, both HEALER and DOSIM reason strategically about the multiagent system of homeless youth to select a sequence of 3-4 youth at a time to maximize HIV awareness. Unfortunately, while earlier research [Yadav et al., 2016; Wilder et al., 2017] published promising simulation results from the lab, neither of these agent based systems have ever been tested in the real world.

(b) Emergency Resource Shelf

Figure 1: Facilities at our Collaborating Service Providers

Several questions need to be answered before these agents can be deployed in the field. First, do peer leaders actually spread HIV information in a homeless youth social network, and are they are able to provide meaningful information about the social network structure during intervention training (as assumed by HEALER and DOSIM)? Second, the benefits of deploying a social influence maximization agent which selects peer leaders needs to be ascertained, i.e., would these agents outperform standard techniques used by service providers to select peer leaders? If they do not, for some unforeseen reason, then a large-scale deployment is unwarranted. Third, which agent out of HEALER or DOSIM performs better in the field?

Thus, it is necessary to conduct real-world pilot tests, before deployment of these agents on a large scale. Indeed, the health-critical nature of the domain and complex influence spread models used by social influence maximization agents makes conducting pilot tests even more important, to validate their real-world effectiveness. This paper presents results from three real-world pilot studies, involving 173 homeless youth in Los Angeles. This is an actual test involving word-of-mouth spread of information, and actual changes in youth behavior in the real-world, as a result. To the best of our knowledge, these are the first such pilot studies which provide head-to-head comparison of different software agent (with POMDP, robust optimization driven) approaches for social influence maximization, including a comparison with a baseline approach. Our pilot study results show that HEALER and DOSIM achieve 160% more information spread than Degree Centrality (baseline), and do significantly better at inducing behavior change among homeless youth. For more detailed results and analysis, please refer to Yadav et al. [Yadav et al., 2017].

2 HEALERDescription

HEALER [Yadav et al., 2016] is a software agent that casts the problem of selecting influential peer leaders as a Partially Observable Markov Decision Process (POMDP) [Puterman, 2009] to compute a T-step online policy for selecting K nodes for T stages. Unfortunately, the POMDP models (defined in Yadav et. al. [Yadav et al., 2016]) for realworld network sizes end up having huge state and action spaces (2300 states and (150 6 ) actions), because of which solving these POMDPs is not possible with standard offline or online techniques [Smith, 2013; Silver and Veness, 2010].

Thus, HEALER utilizes hierarchical ensembling techniques - it creates ensembles of smaller POMDPs at two different levels. Figure 2 shows the flow of HEALER. First, the original POMDP is divided into several smaller intermediate POMDPs using graph partitioning techniques. Next, each intermediate POMDP is further subdivided into several smaller sampled POMDPs using graph sampling techniques. These sampled POMDPs are then solved in parallel using novel online planning methods - each sampled POMDP executes a Monte Carlo tree search [Silver and Veness, 2010] to select the best action in that sampled POMDP. The solutions of these smaller POMDPs are combined to form the solution of the original POMDPs. See [Yadav et al., 2016] for more details on HEALER.

3 DOSIMDescription

DOSIM [Wilder et al., 2017] is a novel algorithm that generalizes an assumption about knowing propagation probability values for each edge in the social network of homeless youth. HEALER dealt with this issue by assuming specific propagation probability values (pe) based on suggestions by service providers. DOSIM instead works with interval uncertainty over these pe parameter values. DOSIM chooses an action which is robust to this interval uncertainty. Specifically, it finds a policy which achieves close to optimal value regardless of where the unknown probabilities lie within the interval. The problem is formalized as a zero sum game between the algorithm, which picks a policy, and an adversary (nature) who chooses the model parameters. This game formulation represents a key advance over HEALER's POMDP policy (which was constrained to fixed propagation probabilities), as it enables DOSIM to output mixed strategies over POMDP policies, which make it robust against worst-case propagation probability values. The strategy space for the game is intractably large because there are an exponential number of policies (each of which specifies an action to take for any possible set of observations). Hence, DOSIM uses a double oracle approach. By iteratively computing best responses for each player, DOSIM finds an approximate equilibrium of the game without having to enumerate the entire set of policies.

4 Pilot Study Pipeline

Starting in Spring 2016, we conducted three different pilot studies at two service providers in Los Angeles, over a seven month period. Each pilot study recruited a unique network of youth. Each of these pilot studies had a different intervention mechanism, i.e., a different way of selecting actions (or a set of K peer leaders). The first and second studies used HEALER and DOSIM (respectively) to select actions, whereas the third study served as the control group, where actions were selected using Degree Centrality (i.e., picking K nodes in order of decreasing degrees). We chose Degree Centrality (DC) as the control group mechanism, because this is the current modus operandi of service providers in conducting these network based interventions [Valente, 2012].

Pilot Study Process The pilot study process consists of five sequential steps. Figure 3 illustrates these five steps. First, we recruit homeless youth from a service provider into our study. Second, the friendship based social network that connects these homeless youth is generated using (i) online contacts of homeless youth; and (ii) field observations made by the authors and service providers. Third, the generated network is used by the software agents to select actions (i.e., K peer leaders) for T stages. Fourth, the follow up phase consists of meetings, where the peer leaders are asked about any difficulties they faced in talking to their friends about HIV. Finally, we conduct in-person surveys, one month after all interventions have ended. During the surveys, they are asked if some youth from within the pilot study talked to them about HIV prevention methods, after the pilot study began. Their answer helps determine if information about HIV reached them in the social network or not. Moreover, they are asked to take a survey about HIV risk which helps us measure behavior change among these youth. These postintervention surveys enable us to compare HEALER, DOSIM and DC in terms of information spread (i.e., how successful were the agents in spreading HIV information through the social network) and behavior change (i.e., how successful were the agents in causing homeless youth to test for HIV), the two major metrics that we use for evaluation.

5 Results from the Field

We now provide results from all three pilot studies. In each study, three interventions were conducted (or, T = 3), i.e., Step 3 of the pilot study process (Figure 3) was repeated three times. The actions (i.e., set of K peer leaders) were chosen using intervention strategies (policies) provided by HEALER, DOSIM, and Degree Centrality (DC) in the first, second and third pilot studies, respectively. Recall that we provide comparison results on two different metrics. First, we provide results on information spread, i.e., how well different software agents were able to spread information about HIV through the social network. Second, even though HEALER and DOSIM do not explicitly model behavior change in their objective function (both maximize the information spread in the network), we provide results on behavior change among homeless youth, i.e., how successful were the agents in inducing behavior change among homeless youth.

Figure 4 shows a Venn diagram that explains the results that we collect from the pilot studies. To begin with, we exclude peer leaders from all our results, and focus only on non peer-leaders. This is done because peer leaders cannot be used to differentiate the information spread (and behavior change) achieved by HEALER, DOSIM and DC. In terms of information spread, all peer leaders are informed about HIV directly by study staff in the intervention trainings. In terms of behavior change, the proportion of peer leaders who change their behavior does not depend on the strategies recommended by HEALER, DOSIM and DC. Thus, Figure 4 shows a Venn diagram of the set of all non peer-leaders (who were surveyed at the end of one month). This set of non peer-leaders can be divided into four quadrants based on (i) whether they were informed about HIV or not (by the end of one-month surveys in Step 5 of Figure 3); and (ii) whether they were already tested for HIV at baseline (i.e., during recruitment, they reported that they had got tested for HIV in the last six months) or not.

For information spread results, we report on the percentage of youth in this big rectangle, who were informed about HIV by the end of one month (i.e., boxes A+B as a fraction of the big box). For behavior change results, we exclude youth who were already tested at baseline (as they do not need to undergo "behavior change", because they are already exhibiting desired behavior of testing). Thus, we only report on the percentage of untested informed youth, (i.e., box B), who now tested for HIV (i.e., changed behavior) by the end of one month (which is a fraction of youth in box B). We do this because we can only attribute conversions (to testers) among youth in box B (Figure 4) to strategies recommended by HEALER and DOSIM (or the DC baseline). For example, non peer-leaders in box D who convert to testers (due to some exogenous reasons) cannot be attributed to HEALER or DOSIM's strategies (as they converted to testers without getting HIV information).

Information Spread Figure 5a compares the information spread achieved by HEALER, DOSIM and DC in the pilot studies. The X-axis shows the three different intervention strategies and the Y-axis shows the percentage of non-peerleaders to whom information spread (box A+B as a percentage of total number of non-peer leaders in Figure 4). This figure shows that PL chosen by HEALER (and DOSIM) are able to spread information among ∼70% of the non peer-leaders in the social network by the end of one month. Surprisingly, PL chosen by DC were only able to inform ∼27% of the non peer-leaders. This result is surprising, as it means that HEALER and DOSIM's strategies were able to improve over

(a) Comparison of Information Spread Among Non Peer-Leaders

(b) Behavior Change

Figure 5: Results show improvement over previous work

DC's information spread by ∼160%.

Behavior Change Figure 5b compares behavior change observed in homeless youth in the three pilot studies. The X-axis shows different intervention strategies, and the Y-axis shows the percentage of non peer-leaders who were untested for HIV at baseline and were informed about HIV during the pilots (i.e. youth in box B in Figure 4). This figure shows that PL chosen by HEALER (and DOSIM) converted 37% (and 25%) of the youth in box B to HIV testers. In contrast, PL chosen by DC did not convert any youth in box B to testers. DC's information spread reached a far smaller fraction of youth (Figure 5a), and therefore it is unsurprising that DC did not get adequate opportunity to convert anyone of them to testing. This shows that even though HEALER and DOSIM do not explicitly model behavior change in their objective function, the agents strategies still end up outperforming DC significantly in terms of behavior change. We now explain reasons behind this significant improvement achieved by HEALER and DOSIM (over DC).

Redundant Edges In Figure 6a, the X-axis shows different pilots and the Y-axis shows what percentage of network edges were redundant, i.e., they connected two peer leaders. Such edges are redundant, as both its nodes (peer leaders) already have the information. This figure shows that redundant edges accounted for only 8% (and 4%) of the total edges in HEALER (and DOSIM's) pilot study. On the other hand, 21% of the edges in DC's pilot study were redundant. Thus, DC's strategies picks PL in a way which creates a lot of redundant edges, whereas HEALER picks PL which create only 1/3 times the number of redundant edges. DOSIM performs best in this regard, by selecting nodes which creates the fewest redundant edges (∼ 5X less than DC, and even 2X less than HEALER), and is the key reason behind its good performance in Figure 5a.

Community Structure Figure 6b illustrates patterns of PL selection (for each stage of intervention) by HEALER, DOSIM and DC across the four different communities uncovered in Figure 6b. Recall that each pilot study comprised of three stages of intervention (each with four selected PL). The X-axis shows the three different pilots. The Y-axis shows what percentage of communities had a PL chosen from within them. For example, in DC's pilot, the chosen PL covered 50% (i.e., two out of four) communities in the 1st stage, 75% (i.e., three out of four) communities in the 2nd stage, and so on.

This figure shows that HEALER's chosen peer leaders cover all possible communities (i.e., 100% communities touched) in the social network in all three stages. On the other hand, DC concentrates its efforts on just a few clusters in the network, leaving ∼50% communities untouched (on average). Therefore, while HEALER ensures that its chosen PL covered most real-world communities in every intervention, the PL chosen by DC focused on a single (or a few) communities in each intervention. This further explains why HEALER is able to achieve greater information spread, as it spreads its efforts across communities unlike DC. While DOSIM's coverage of communities is similar to DC, it outperforms DC because of ∼5X less redundant edges than DC (Figure 6a).

6 Conclusion &Lessons Learned

This paper presents first-of-its-kind results from three realworld pilot studies, involving 173 homeless youth in an American city. Conducting these pilot studies underlined their importance in this transition process - they are crucial milestones in the arduous journey of an agent from an emerging phase in the lab, to a deployed application in the field.

These pilot studies also helped to establish the superiority (and hence, their need) of HEALER and DOSIM - we are using complex agents (involving POMDPs and robust optimization), and they outperform DC (the modus operandi of conducting peer-led interventions) by 160% (Figures 5a, 5b). The pilot studies also helped us gain a deeper understanding of how HEALER and DOSIM beat DC (shown in Figures 6a, 6b) - by minimizing redundant edges and exploiting community structure of real-world networks. Out of HEALER and DOSIM, the pilot tests do not reveal a significant difference in terms of either information spread or behavior change (Figures 5a, 5b). Thus, carrying either of them forward would lead to significant improvement over the current state-of-theart techniques for conducting peer-leader based interventions. However, DOSIM runs significantly faster than HEALER (∼ 40×), thus, it is more beneficial in time-constrained settings [Wilder et al., 2017]. Thus, these pilot studies open the door to future deployment of these agents in the field (by providing positive results about the performance of HEALER and DOSIM).

Acknowledgements

This research was supported by MURI grant W911NF-11-10332 and NIMH Grant R01-MH093336.