Influence Spread in Social Networks for Spreading Health Information

This project focuses on the study of diffusion processes in social networks of hard to reach populations (such as homeless youth) in order to spread information and raise general levels of awareness about dangerous diseases (such as HIV) in order to reduce rates of such diseases among such populations. Scientifically, the goal is not only to model these influence spread phenomena, but to also develop algorithms or mechanisms using which information can be spread in these social networks in the most efficient manner. A big focus of the work in this project is to validate all our models, algorithms and techniques in the real world by testing it out with actual homeless youth (specifically youth in Los Angeles. Recently, we have been talking to homeless shelter officials in Los Angeles about the problems that they face in raising awareness about HIV among homeless youth, come up with innovative ways to solve their problems and then test out our algorithms by doing pilot deployment studies with actual homeless youth.

Participants:

Alumni:

Preventing HIV Spread in Homeless Populations:

AIDS is a very dangerous disease that sees no race, no color, no gender, no economic background and not even a specific age group. It can affect anyone, at any time if they put themselves in a situation where they could be at risk. HIV is seen to be highly prevalent amongst the homeless youth of Los Angeles. Studies have shown that a major factor that encourages people to engage in high HIV risk behavior is whether people in their social circle engage in those behaviors.

Therefore, anyone trying to come up with decent intervention strategies for the homeless youth network must take into account the social aspect of this problem. We, in our work try to help shelter homes and agencies use their resources more effectively by modeling the entire problem as an Influence Maximization Problem(IMP).

Heather Carmichael and team in the field conducting interventions for homeless youth

However, standard influence maximization literature looks at a single shot decision problem (in which a single subset is chosen which then spreads influence throughout the network). This model is not usable as-is in the real world as agencies (working with homeless youth) would not want to conduct only one intervention. They typically want to conduct a series of small size interventions, so it becomes a sequential decision making problem. Moreover, in the real world, it is not always clear how the network linkages look like. In our discussions with people from agencies, we found that while they have a first approximation of the network, finding out with certainty whether two people are friends is extremely difficult and would likely be very expensive. Therefore, another novel feature of this work is that we perform influence maximization while dealing with uncertainty in the network structure.

Friendship based social network of homeless people visiting My Friend's Place

We cast this sequential decision making problem under uncertainty as a Partially Observable Markov Decision Process (POMDP). Unfortunately, our POMDP is extremely large, due to which existing POMDP solvers are unable to scale up to our sizes. Therefore, we come up with a heuristic QMDP based online POMDP solver which beats the existing state-of-the-art in our simulations on artificial networks and on real world graphs. Our paper on this problem just got accepted at IAAI 2015.

Flowchart of techniques used in PSINET: Our solver

 

Pilot Study with Safe Place for Youth:

We were fortunate enough to test our algorithms by conducting a pilot study recently with Safe Place for Youth, a homeless shelter in Venice Beach, Los Angeles. Safe Place for Youth provides free food and clothing to homeless youth of the ages 12-25, three times a week. We enrolled 62 homeless youth from this shelter into our study and we conducted three test interventions. Right now, we are busy in trying to analyze all the results and data that we collected during this pilot study. We are also planning to conduct a much larger study with 900 homeless youth in Fall 2016. If you are interested and would like to contribute, feel free to talk to us!

Safe Place for Youth

Social Network of 62 homeless youth in Safe Place for Youth

News:

Publications:

Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization Under Uncertainty
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2016

POMDPs for Assisting Homeless Shelters - Computational and Deployment Challenges
In Proceedings of the IDEAS Workshop in International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2016 (Winner of the Most Visionary Paper Award)

Simultaneous Influencing and Mapping Social Networks (Extended Abstract)
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2016

HEALER: POMDP Planning for Scheduling Interventions among Homeless Youth (Demonstration)
In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2016

Preventing HIV Spread in Homeless Populations using PSINET
In Proceedings of the Annual Conference on Innovative Applications of Artificial Intelligence (IAAI), Jan 2015