{'fraction_non_alphanumeric': 0.035421440600756464, 'fraction_numerical': 0.00913834515888573, 'mean_word_length': 4.807599807599807, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Influence Maximization for Social Good: Use of Social Networks in Low Resource Communities

This thesis proposal makes the following technical contributions: (i) we provide a definition of the Dynamic Influence Maximization Under Uncertainty (or DIME) problem, which models the problem faced by homeless shelters accurately; (ii) we propose a novel Partially Observable Markov Decision Process (POMDP) model for solving the DIME problem; (iii) we design two scalable POMDP algorithms (PSINET and HEALER) for solving the DIME problem, since conventional POMDP solvers fail to scale up to sizes of interest; and (iv) we test our algorithms effectiveness in the real world by conducting a pilot study with actual homeless youth in Los Angeles. The success of this pilot (as explained later) shows the promise of using influence maximization for social good on a larger scale.


Introduction
Since ancient times, humans have intertwined themselves into various social networks. These networks can be of many different kinds, such as friendship based networks, consumer/seller networks, professional networks, etc. Besides these networks being used for more direct reasons (e.g., friendship based networks used for connecting with old and new friends, consumer/seller networks used for finding out highly rated sellers providing cheap deals, etc.), these networks also play a critical role in the formulation and propagation of opinions and ideas among the people in that network. In recent times, this property of social networks has been exploited by companies to popularize their products among consumers, and by election campaigners to win support among voters, among other examples.
From a computer science perspective, the question of finding out the most "influential" people in a social network is well studied in the field of influence maximization, which looks at the problem of selecting the K (an input parameter) most influential nodes in a social network (represented as a graph), who will be able to influence the most number of people in the network within a given time period. Influence in these networks is assumed to spread according to a known influence model (popular ones are independent cascade [23] and linear threshold [4]). Since the field's inception in 2003 by Kempe et. al. [16], influence maximization has seen a lot of progress over the years [23,18,4,5,2,34,1,19,3,22,12,13,37,11,10].
Unfortunately, most models and algorithms from previous work do not address challenges that are crucial in many real-world domains such as uncertainties in network structure, selection of nodes in multiple stages, etc. Specifically, most previous work suffers from four potential major limitations. First, almost every previous work focuses on single-shot decision problems, where only a single subset of graph nodes is to be chosen and then evaluated for influence spread. Instead, most realistic applications of influence maximization would require selection of nodes in multiple stages (as we illustrate later). Second, the state of the network is not known; thus, the selection of nodes in multiple stages (which is unhandled in previous work) introduces additional uncertainty about which network nodes are influenced at a given point in time, which complicates the node selection procedure. Third, network structure is assumed to be known with certainty in most previous work, which is untrue in reality, considering that there is always noise in any network data collection procedure. Fourth, most previous work in influence maximization has used two probabalistic influence models (the independent cascade model and the linear threshold model) for their mathematical elegance, but their effectiveness in modeling the influence spread process remains invalidated in the real world.
This thesis attempts to resolve these limitations and is motivated by an important domain, where influence maximization could be used for social good: raising awareness about Human Immunodeficiency Virus (HIV) among homeless youth. HIV-AIDS is a dangerous disease which claims 1.5 million lives annually [36], and homeless youth are particularly vulnerable to HIV due to their involvement in high risk behavior such as unprotected sex, sharing drug needles, etc. [7]. To prevent the spread of HIV, many homeless shelters conduct intervention camps, where a select group of homeless youth are trained as "peer leaders" to lead their peers towards safer practices and behaviors, by giving them information about safe HIV prevention and treatment practices. These peer leaders are then tasked with spreading this information among people in their social circle.
However, due to financial/manpower constraints, the shelters can only organize a limited number of intervention camps. Moreover, in each camp, the shelters can only manage small groups of youth (∼3-4) at a time (as emotional and behavioral problems of youth makes management of bigger groups difficult). Thus, the shelters prefer a series of small sized camps organized sequentially [29]. As a result, the shelter cannot intervene on the entire target (homeless youth) population. Instead, it tries to maximize the spread of awareness among the target population (via word-of-mouth influence) using the limited resources at its disposal. To achieve this goal, the shelter uses the friendship based social network of the target population to strategically choose the participants of their limited intervention camps. Unfortunately, the shelters' job is further complicated by a lack of complete knowledge about the social network's structure [27]. Some friendships in the network are known with certainty whereas there is uncertainty about other friendships.
Thus, the shelters face an important challenge: they need a sequential plan to choose the participants of their sequentially organized interventions. This plan must address three key points: (i) it must deal with network structure uncertainty; (ii) it needs to take into account new information uncovered during the interventions, which reduces the uncertainty in our understanding of the network; and (iv) the intervention approach should address the challenge of gathering information about social networks of homeless youth, which usually costs thousands of dollars and many months of time [29].
The contributions of this thesis are as follows. First, we use the homeless youth domain to motivate the definition of the Dynamic Influence Maximization Under Uncertainty (DIME) problem [42,46,39,44,38,43,47,40,49,41,48], which models the aforementioned challenge faced by the homeless shelters accurately. Infact, the sequential selection of network nodes in multiple stages in DIME sets it apart from any other previous work in influence maximization [23,18,4,5]. Second, we introduce a novel Partially Observable Markov Decision Process (POMDP) based model for solving DIME, which takes into account uncertainties in network structure and evolving network state . Third, since conventional POMDP solvers fail to scale up to sizes of interest (our POMDP had 2 300 states and 150 6 actions), we design two scalable (and more importantly, "deployable") algorithms, which use our POMDP model to solve the DIME problem [45].
Our first algorithm PSINET [38] relies on the following key ideas: (i) compact representation of transition probabilities to manage the intractable state and action spaces; (ii) combination of the QMDP heuristic with Monte-Carlo simulations to avoid exhaustive search of the entire belief space; and (iii) voting on multiple POMDP solutions, each of which efficiently searches a portion of the solution space to improve accuracy. Unfortunately, even though PSINET was able to scale up to real-world sized networks, it completely failed at scaling up in the number of nodes that get picked in every round (intervention). To address this challenge, we designed HEAL, our second algorithm. HEAL [42] hierarchically subdivides our original POMDP at two layers: (i) In the top layer, graph partitioning techniques are used to divide the original POMDP into intermediate POMDPs; (ii) In the second level, each of these intermediate POMDPs is further simplified by sampling uncertainties in network structure repeatedly to get sampled POMDPs; (iii) Finally, we use aggregation techniques to combine the solutions to these simpler POMDPs, in order to generate the overall solution for the original POMDP.
Finally, we have also tested HEAL's performance in a real-world pilot study, in collaboration with Safe Place for Youth 1 , a homeless shelter in Los Angeles which provides food and lodging to homeless youth. We enrolled 60 homeless youth from Safe Place for Youth and conducted multiple interventions and post-intervention surveys to evaluate the effectiveness of HEAL at spreading awareness about HIV. Our pilot results showed that HEAL was able to propagate information to 66% of all surveyed youth. More importantly, HEAL was successful in behavior change as well, with a 25% increase in the number of youth who get tested for HIV regularly. These results point to the usability of HEAL in the real world. More importantly, it illustrates one way (among many others) in which social networks and influence maximization can be harnessed for doing social good.

Chapter 2
Background and Related Work

Related Work
The influence maximization problem, as stated by Kempe et. al. [16], takes in a social network as input (in the form of a graph), and outputs a set of K 'seed nodes' which maximize the expected influence spread in the social network within T time steps. Note that the expectation of influence spread is taken with respect to a probabilistic influence model (explained later), which is also provided as input to the problem.
There are many algorithms for finding 'seed sets' of nodes to maximize influence spread in networks [16,23,2,34,22,12,13,37,11,10]. However, all these algorithms assume no uncertainty in the network structure and select a single seed set. In contrast, we select several seed sets sequentially in our work to select intervention participants, as that is a natural requirement arising from our homeless youth domain. Also, our work takes into account uncertainty about the network structure and influence status of network nodes (i.e., whether a node is influenced or not). Finally, unlike most previous work [16,23,2,34,22,12,13,37,11,10], we use a different influence model as we explain later.
There is another line of work by Golovin et. al. [14], which introduces adaptive submodularity and discusses adaptive sequential selection (similar to our problem). They prove that a Greedy algorithm provides a (1 − 1/e) approximation guarantee. However, unlike our work, they assume no uncertainty in network structure. Also, while our problem can be cast into the adaptive stochastic optimization framework of [14], our influence function is not adaptive submodular (as shown later), because of which their Greedy algorithm loses its approximation guarantees.

Network Representation and Influence Model
We represent social networks as directed graphs (consisting of nodes and directed edges) where each node represents a person in the social network and a directed edge between two nodes A and B (say) represents that node A considers node B as his/her friend. We assume directed-ness of Note that uncertainties about friendships exist because HEALER's Facebook application misses out on some links between people who are friends in real life, but not on Facebook.
To model the uncertainty about missing edges, every uncertain edge e ∈ E u has an existence probability u(e) associated with it, which represents the likelihood of "existence" of that uncertain edge. For example, if there is an uncertain edge (A, B) (i.e., we are unsure whether node B is node A's friend), then u(A, B) = 0.75 implies that B is A's friend with a 0.75 chance. In addition, each edge e ∈ E (both certain and uncertain) has a propagation probability p(e) associated with it. A propagation probability of 0.5 on directed edge (A, B) denotes that if node A is influenced (i.e., has information about HIV prevention), it influences node B (i.e., gives information to node B) with a 0.5 probability in each subsequent time step (our full influence model is defined below). This graph G with all relevant p(e) and u(e) values represents an uncertain network and serves as an input to the DIME problem. Figure 2.1 shows an uncertain network on 6 nodes (A to F) and 7 edges. The dashed and solid edges represent uncertain (edge numbers 1, 4, 5 and 7) and certain (edge numbers 2, 3 and 6) edges, respectively.
Influence Model We use a variant of the independent cascade model [50]. In the standard independent cascade model, all nodes that get influenced at round t get a single chance to influence their un-influenced neighbors at time t + 1. If they fail to spread influence in this single chance, they don't spread influence to their neighbors in future rounds. Our model is different in that we assume that nodes get multiple chances to influence their un-influenced neighbors. If they succeed in influencing a neighbor at a given time step t , they stop influencing that neighbor for all future time steps. Otherwise, if they fail in step t , they try to influence again in the next round. This variant of independent cascade has been shown to empirically provide a better approximation to real influence spread than the standard independent cascade model [6,50]. Further, we assume that nodes that get influenced at a certain time step remain influenced for all future time steps.

POMDP
Partially Observable Markov Decision Processes (POMDPs) are a well studied model for sequential decision making under uncertainty [26]. Intuitively, POMDPs model situations wherein an agent tries to maximize its expected long term rewards by taking various actions, while operating in an environment (which could exist in one of several states at any given point in time) which reveals itself in the form of various observations. The key point is that the exact state of the world is not known to the agent and thus, these actions have to be chosen by reasoning about the agent's probabilistic beliefs (belief state). The agent, thus, takes an action (based on its current belief), and the environment transitions to a new world state. However, information about this new world state is only partially revealed to the agent through observations that it gets upon reaching the new world state. Hence, based on the agent's current belief state, the action that it took in that belief state, and the observation that it received, the agent updates its belief state. The entire process repeats several times until the environment reaches a terminal state (according to the agent's belief). More formally, a full description of the POMDP includes the sets of possible environment states, the set of actions that the agent can take, and the set of possible observations that the agent can observe. In addition, the full POMDP description includes a transition matrix, for storing transition probabilities, which specify the probability with which the environment transitions from one state to another, conditioned on the immediate action taken. Another component of the POMDP description is the observation matrix, for storing observation probabilities, which specify the probability of getting different observations in different states, conditioned on the action taken to reach that state. Finally, the POMDP description includes a reward matrix, which specifies the agent's reward of taking actions in different states.
A POMDP policy Π provides a mapping from every possible belief state (which is a probability distribution over world states) to an action a = Π(β). Our aim is to find an optimal policy Π * which, given an initial belief β 0 , maximizes the expected cumulative long term reward over H horizons (where the agent takes an action and gets a reward in each time step until the horizon H is reached). Computing optimal policies offline for finite horizon POMDPs is PSPACE-Complete. Thus, focus has recently turned towards online algorithms, which only find the best action for the current belief state [24,32]. Thus, online planning interleaves planning and execution at every time step.

Chapter 3 DIME Problem
We now provide some background information that helps us define a precise problem statement for DIME. After that, we will show some hardness results about this problem statement.
Given the uncertain network as input, we plan to run for T rounds (corresponding to the number of interventions organized by the homeless shelter). In each round, we will choose K nodes (youth) as intervention participants. These participants are assumed to be influenced postintervention with certainty. Upon influencing the chosen nodes, we will 'observe' the true state of the uncertain edges (friendships) out-going from the selected nodes. This translates to asking intervention participants about their 1-hop social circles, which is within the homeless shelter's capabilities [28].
After each round, influence spreads in the network according to our influence model for L time steps, before we begin the next round. This L represents the time duration in between two successive intervention camps. In between rounds, we do not observe the nodes that get influenced during L time steps. We only know that explicitly chosen nodes (our intervention participants in all past rounds) are influenced. Informally then, given an uncertain network G 0 = (V, E) and integers T , K, and L (as defined above), our goal is to find an online policy for choosing exactly K nodes for T successive rounds (interventions) which maximizes influence spread in the network at the end of T rounds.
We that takes in histories of length less than or equal to i and outputs a K node choice for the current time step. We now provide an explicit problem statement for DIME.  ∈ [1, T ], and G i are drawn according to the distribution over uncertain edges of G i−1 that are revealed by A i . The objective of DIME is to find an optimal T -step policy We now analyze the hardness of computation in the DIME problem in the next two theorems. More details and proofs of these theorems can be found in Yadav et. al. [42].

Theorem 1
The DIME problem is NP-Hard.
Some NP-Hard problems exhibit nice properties that enable approximation guarantees for them. Golovin et. al. [14] introduced adaptive submodularity, an analog of submodularity for adaptive settings. Presence of adaptive submodularity ensures that a simply greedy algorithm provides a (1 − 1/e) approximation guarantee w.r.t. the optimal solution defined on the uncertain network. However, as we show next, while DIME can be cast into the adaptive stochastic optimization framework of [14], our influence function is not adaptive submodular, because of which their Greedy algorithm does not have a (1 − 1/e) approximation guarantee.

Theorem 2
The influence function of DIME is not adaptive submodular.

Chapter 4 POMDP Model
The theorems in the previous chapter show that DIME is a hard problem as it is difficult to even obtain any reasonable approximations. We model DIME as a POMDP [26] because of two reasons. First, POMDPs are a good fit for DIME as (i) we conduct several interventions sequentially, similar to sequential POMDP actions; and (ii) we have partial observability (similar to POMDPs) due to uncertainties in network structure and influence status of nodes. Second, POMDP solvers have recently shown great promise in generating near-optimal policies efficiently [32]. We now explain how we map DIME onto a POMDP. Observations. Upon taking a POMDP action, we "observe" the ground reality of the uncertain edges outgoing from the nodes chosen in that action. Consider Θ(a) = {e | e = (x,y) s.t. x ∈ a ∧ e ∈ E u } ∀a ∈ A, which represents the (ordered) set of uncertain edges that are observed when we take action a. all network nodes are un-influenced (as we assume that all nodes are un-influenced to begin with). Inside its support, each F i is distributed independently according to P (F i = 1) = u(e). Transition And Observation Probabilities. Computation of exact transition probabilities T (s |s, a) requires considering all possible paths in a graph through which influence could spread, which is O(N !) (N is number of nodes in the network) in the worst case. Moreover, for large social networks, the size of the transition and observation probability matrix is prohibitively large (due to exponential sizes of state and action space). Therefore, instead of storing huge transition/observation matrices in memory, we follow the paradigm of large-scale online POMDP solvers [32,9] by using a generative model Λ(s, a) ∼ (s , o, r) of the transition and observation probabilities. This generative model allows us to generate on-the-fly samples from the exact distributions T (s |s, a) and Ω(o|a, s ) at very low computational costs. Given an initial state s and an action a to be taken, our generative model Λ simulates the random process of influence spread to generate a random new state s , an observation o and the obtained reward r. Details of the random process of simulation can be found in Yadav et. al. [38,42]. First, we tried to solve this POMDP using current state-of-the-art solvers. Initial experiments with ZMDP [33] showed that state-of-the-art offline POMDP planners ran out of memory on 10 node graphs. Thus, we focused on POMCP [32], a state-of-the-art online POMDP solver. Unfortunately, even POMCP ran out of memory on 30 node graphs. In the next two chapters, we provide two different scalable POMDP algorithms (PSINET and HEAL) for solving the DIME problem.

Chapter 5 PSINET
As a first attempt at solving DIME, we proposed PSINET, a Monte Carlo (MC) sampling based online planner that simplifies the POMDP into smaller sub-problems and then uses various kinds of voting techniques to aggregate the solutions of the sub-problems.
The flow of PSINET proceeds in three distinct steps, as shown in Figure 5.1(a). First, graph sampling techniques are used to get many different graph instances, each of which is solved as an independent POMDP. Second, each of these independent POMDPs is run (in parallel) to find out the best action to take in each independent POMDP. Finally, all these independent POMDPs vote for the best action to be taken. These votes are then aggregated using different voting mechanisms (each different voting mechanism gives rise to different variants of PSINET, as we explain later), and the overall best action that wins this vote is executed by PSINET. We now go through each of the three distinct steps shown in Figure 5.1(a) in more detail.
Sampling Graphs First, we randomly keep or remove uncertain edges to create one graph instance. As a single instance might not represent the real network well, we instantiate the graph several times to create a set ∆ of instances. Then, we use each of these instances to vote for the best action to be taken. Finding Best Action For each sampled graph instance, we find the action which maximizes long term rewards averaged across η (we use η=2 8 ) MC simulations starting from states (particles) sampled from the current belief β. Each MC simulation samples a particle from β and chooses an action to take (choice of action is explained in Yadav et. al. [38]). Then, upon taking this action, we follow a uniform random rollout policy (until either termination, i.e., all nodes get influenced, or the horizon is breached) to estimate the long term reward, which we get by taking the "selected" action. Finally, we pick the action with the maximum average reward. Voting Mechanisms Finally, each network instance votes for the best action (found in the previous step) to take in the uncertain graph and the overall best action (approximate) is chosen by aggregating these votes according to different voting schemes. We propose using the following three different voting schemes, each of which leads to a different variant of PSINET: PSINET-S Each instance's vote gets equal weight. PSINET-W Every instance's vote gets weighted differently. This weighting scheme approximates the probabilities of occurrences of real world events by giving low weights to instances which removes either too few or too many uncertain edges, since those events are less likely to occur. Instances which remove exactly half the number of uncertain edges get the highest weight, since that event is most likely [38].
PSINET-C Given a ranking over actions, the Copeland rule makes pairwise comparisons among all actions, and picks the one preferred by a majority of instances over the highest number of other actions [25]. In PSINET-C, similar to Jiang. et. al. [15], rankings over actions are generated for each instance, and the winner decided using Copeland rule. Figure 5.1(b) compares solution qualities of Degree Centrality (DC), POMCP and PSINET-(S,W and C) on BTER [31] networks of varying sizes. DC selects nodes in decreasing order of out-degrees, where every uncertain edge e adds u(e) to the node degrees. We choose DC as our baseline as it is the current modus operandi of agencies working with homeless youth. The x-axis shows number of network nodes and the y-axis shows influence spread across varying horizons (number of interventions). This figure shows that all POMDP based algorithms beat DC by around 60%, which shows the value of our POMDP model. Further, it shows that PSINET-W beats PSINET-(S and C). Also, POMCP runs out of memory on 30 node graphs.
Unfortunately, even though PSINET was able to scale up to real-world sized networks, it completely failed at scaling up in the number of nodes that get picked in every round (intervention). Thus, while PSINET was successful in scaling up to the required POMDP state space, it failed to deal with the explosion in action space that occurred with scale up in the number of nodes picked per round. To address this challenge, we designed HEAL, which we present next.

Chapter 6
HEAL HEAL solves the original POMDP using a novel hierarchical ensembling heuristic: it creates ensembles of imperfect (and smaller) POMDPs at two different layers, in a hierarchical manner (see Figure 6.1). HEAL's top layer creates an ensemble of smaller sized intermediate POMDPs by subdividing the original uncertain network into several smaller sized partitioned networks by using graph partitioning techniques [20], which generates partitions that minimize the edges going across partitions (while ensuring that partitions have similar sizes). Since these partitions are "almost" disconnected, we solve each partition separately. Each of these partitioned networks is then mapped onto a POMDP, and these intermediate POMDPs form our top layer ensemble of POMDP solvers.
In the bottom layer, each intermediate POMDP is solved using TASP (Tree Aggregation for Sequential Planning), our novel POMDP planner, which subdivides the POMDP into another ensemble of smaller sized sampled POMDPs. Each member of this bottom layer ensemble is created by randomly sampling uncertain edges of the partitioned network to get a sampled network having no uncertain edges, and this sampled network is then mapped onto a sampled POMDP. Each sampled POMDP is solved using a novel tree search algorithm, which avoids the exponential branching factor seen in PSINET [38]. Finally, the solutions of POMDPs in both the bottom and top layer ensembles are aggregated using novel techniques to get the solution for HEAL's original POMDP.
These heuristics enable scale up to real-world sizes (at the expense of sacrificing performance guarantees), as instead of solving one huge problem, we now solve several smaller problems. However, these heuristics perform very well in practice. Our simulations show that even on smaller settings, HEAL achieves a 100X speed up over PSINET, while providing a 70% improvement in solution quality; and on larger problems, where PSINET is unable to run at all, HEAL continues to provide high solution quality. edges. We repeat this sampling process to get ∆ (a variable parameter) different instantiated networks. These ∆ different instantiated networks are then mapped onto to ∆ different POMDPs, which form our ensemble of sampled POMDPs. Each sampled POMDP shares the same action space (defined on the input partitioned network) as the different POMDPs only differ in the sampling of uncertain edges. Next, for each instantiated network δ ∈ [1, ∆], we generate an α δ list of rewards. The i th element of α δ gives the long term reward achieved by taking the i th action in instantiated network δ. After these α δ lists are generated, we find the expected reward r i of taking the i th action, by taking a reward expectation across the α δ lists (for each δ ∈ [1, ∆]). For e.g., if α δ 1 1 = 10 and α δ 2 1 = 20, i.e., the rewards of taking the 1 st action in instantiated networks δ 1 and δ 2 (which occurs with probabilities P (δ 1 ) and P (δ 2 )) are 10 and 20 respectively, then the expected reward r 1 = P (δ 1 ) × 10 + P (δ 2 ) × 20. Note that P (δ 1 ) and P (δ 2 ) are found by multiplying existence probabilities u(e) (or 1 − u(e)) for uncertain edges that were kept (or removed) in δ 1 and δ 2 . Finally, the action κ = argmax j r j is returned by TASP. More details on the generation of α δ lists can be found in Yadav et. al. [42]. and T as input, we first partition the uncertain network into K partitions. In each round from 1 to T , we invoke the bottom layer TASP algorithm to select 1 node from each of the K clusters. These singly selected nodes from the K clusters give us an action of K nodes, which is given to shelter officials to execute. and T as input, we first partition the uncertain network into T partitions and TASP picks K nodes from the i th partition (i ∈ [1, T ]) in the i th round. Simulation Results Figure 6.2(a) shows the influence spread of different algorithms on four real world networks of homeless youth. The x-axis shows the four networks and the y-axis shows the influence spread achieved by the different algorithms. This figure shows that (i) HEAL outperforms all other algorithms on every network; (ii) it achieves ∼70% improvement over PSINET-W in VE and HD networks; (iii) it achieves ∼25% improvement over HEAL-T. The difference between HEAL and other algorithms is not significant in the FB) and MYS networks, as HEAL is already influencing almost all nodes in these two relatively small networks. Figure 6.2(b) shows the influence spread achieved by HEAL, HEAL-T, Greedy and PSINET-W on the VE and HD networks respectively (T = 5), as we scale up values of K, i.e., number of nodes picked per round. The x-axis shows increasing K values, and the y-axis shows the influence spread. This figure show that (i) PSINET-W and HEAL-T fail to scale up -they cannot handle more than K = 2 and K = 3 respectively (thereby not fulfilling real world demands); (ii) HEAL outperforms all other algorithms, and the difference between HEAL and Greedy increases linearly with increasing K values.

Real World Pilot Study
We conducted a pilot study [30] with actual homeless youth in collaboration with Safe Place for Youth (a homeless shelter in Los Angeles) to test the effectiveness of HEAL in spreading information in a social network. We enrolled 62 homeless youth and constructed a social network using their Facebook contact and follower lists. We conducted three interventions, with four homeless youth selected in every intervention. For each intervention, HEAL would take the social network as input and come up with a recommendation of four network nodes as intervention attendees. Out of the 48 surveyed youth, 36 youth reported that they received HIV related information from youth in our study. Thus, HEAL was able to influence 66% of all surveyed youth.
To the best of our knowledge, this is the first deployment of an influence maximization algorithm in the real world. Further, it is the first time that influence maximization has been applied for social good. The success of this pilot study illustrates one way (among many others) in which social networks and influence maximization can be harnessed for doing social good.

Chapter 8
Future Work

Explanation system for POMDPs
The goal of this thesis is to make influence maximization algorithms that actually get deployed in the real world for society's benefit. One big impediment in front of this goal in the homeless youth domain, is the reluctance of homeless shelter officials to adopt state-of-the-art technology (i.e., our algorithms) in selecting their intervention attendees. Thus, there is a need to convince homeless shelter officials that our algorithms are very good at selecting "influential" attendees for their interventions.
Explanation systems for machine learning algorithms [35] have shown great promise in convincing end-users of the algorithm's usefulness. These explanation systems generate an easy-tounderstand explanation of the algorithm's output for the end-user, which facilitates widespread adoption of the algorithm. Recently, explanation systems have also been built for Markov Decision Processes [17,8]. However, no previous work has tackled the problem of building explanation systems for POMDPs, due to challenges of handling partial observability in POMDPs.
In the future, we plan to explore the feasibility of building such an explanation system for HEAL, our POMDP solver. Our goal is to be able to justify the solutions of HEAL to the homeless shelter officials in an intuitive manner. To that end, our first goal is to find out what kind of reasoning do officials (or humans in general) use to pick nodes in very simple graph settings. That will give us an understanding about what kinds of reasons are most likely to persuade humans and offials to adopt HEAL's solutions.

Hybrid approaches
Recently, we investigated the Greedy algorithm introduced by Golovin et. al. [14] more carefully. This work (under submission) was led by another Ph.D. student 1 , and resulted in a non-trivial adaptation of Golovin et. al.'s Greedy algorithm [14], which showed promising results. While this new Greedy algorithm has not been tested in the real world, it outperforms our POMDP algorithms (HEAL and PSINET) in simulation for some cases. As shown in Figure 8.1(a)), this Greedy algorithm achieves more influence spread for smaller values of K (i.e., nodes picked per round). It also run much faster than HEAL (as shown in Figure 8.1(b)).
However, there are still cases where HEAL still outperforms this new Greedy algorithm (see large values of K in Figure 8.1(a)). This leads us to the following question: Can we combine ideas from HEAL and the new Greedy algorithm to design a "hybrid" algorithm which runs much faster than HEAL, and outperforms the Greedy algorithm in all cases? We would like to explore this question as part of future work.

Real world validation
We plan to conduct a much larger study with 900 homeless youth, to test the effectiveness of our algorithms. In this study, we plan to have four different groups of homeless youth (each group has its own social network) which are separated geographically, so as to ensure that the same homeless youth is not a member of two different social networks. We plan to conduct interventions about HIV awareness simultaneously in each of these four groups, with intervention attendees being selected by a different algorithm in each group. This study will allow us to compare the influence spread achieved by different algorithms such as HEAL, Greedy algorithms, Degree Centrality based approaches, uniform random selection, etc.
Further, the data collected in this study will allow us to validate the effectiveness of different influence spread models (such as independent cascade, linear threshold, or our own repeated activation model, etc.) in the real world. Similar to Lerman et. al. [21], information cascade data about who influenced whom, could be used from this study, which will allow us to fit different influence models to the data, and determine which model provides the best fit.