Fast Information Spreading in Social Networks

General Description: This project is a C implementation for analyzing running times of three distributed information spreading algorithms on social networks.

Code Input: The adjacency list of a social graph G = (V, E).

Code Output: The number of required rounds for spreading a piece of message.

Project Goal: Fast information spreading in social networks.

Possible Scenarios:

Consider the following scenarios:

1- You have a piece of information (e.g. a photo). You want to choose a subset of your friends from your social circle (i.e. your Facebook friends or people in your cellphone contact lists) and send the photo to them in order to spread the photo as fast as possible while saving your cellphone energy. This problem have an obvious application in advertising area. One good example for this is the Hudon river accident in 2009 where a person could spread the airplne photo in Twitter faster than any other communicaton channels.

Hudson River Accident-Twitter

2- You are organizing an event and you want to use social media in order to reach as many people as possible in the shortest time. One example for this is the Arab Spring in 2011 where people in middle eastern countries used social media websites such as Twitter and Facebook to organize their protests efficiently.

Arab Spring

Implementation period: January - April 2011

Technical details:
This code has been developed to analyze running times of three algorithms for information spreading including the random push-pull [1], Censor [2], and Doerr [3] algorithms. In the beginning of the experiment, each node has a piece of information that wants to send to all other nodes. The main challeng is the space complexity of the project which is \Theta(n^{2}). This huge space requirement makes it almost impossible to run the code efficiently on large social networks on a normal PC. For instance, if one represents each message with an integer in C, for running the code on a graph with 80,000 nodes we need around 24GB memory! Instead we have implemented a memory-efficient version of the code that uses 32 times less memory by employing bit operations in C. This allowed us to simply run this code efficiently on a PC with 2GB memory space.

Our empirical results show that for fast information spreading in social networks we need to efficiently find communication bottlenecks (e.g. weak ties) and choose them with a higher probability. Please find the details of our results in our Social Computing paper [4]

[1] D. Mosk-Aoyama and D. Shah,Computing separable functions via gossip, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing,2006.
[2] K. Censor-Hillel and H. Shachnai, Fast Information Spreading in Graphs with Large Weak Conductance, SODA 2011.
[3] B. Doerr, M. Fouz, and T. Friedrich, Social networks spread rumors in sublogarithmic time, Proceedings of the 43rd annual ACM symposium on Theory of computing, 2011.
[4] K. Jahanbakhsh, V. King, G.C. Shoja, Empirical Comparison of Information Spreading Algorithms in the Presence of 1-Whiskers, Social Computing 2011, MIT, Boston, USA.