The spreading of a trend or behavior in a social network is a very active area of research. One very important model of trend spreading is the “tipping” model. With tipping, an individual in a network adopts a trend if at least half (or some other proportion) of his or her friends have previously done so. An important problem in viral marketing is to find a “seed set” of individuals in the social network. If all members of a “seed set” in a social network initially adopt a certain trend, then a cascade initiates through the tipping model which results in the entire population adopting that trend. So, if a viral marketer wants to provide free samples of a product to certain individuals, a seed set is likely a good place to start.
In our recently accepted paper entitled “Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets” Major Paulo Shakarian (EECS faculty) and Cadet Damon Paulo (’14) developed a new algorithm that quickly finds very small seed sets of social networks. For example, we were able to process a 1.4 million node sample of the Dutch social network Hyves in under 13 minutes. Further, we demonstrated that the seed sets in real-world online social networks can be very small. For instance, in a sample from the Friendster social network, we found a seed set that consisted of only 0.8% of the population. We validated our algorithm with a set of comprehensive experiments on over 30 real-world social networks. Our experiments also revealed that dense and segregated community structure seem to suppress the spread of a trend under the tipping model.
Our work is funded by the Army Research Office and the Office of the Secretary of Defense as part of a larger effort to better answer certain questions relating to various social networks of interest to the U.S. military. For instance, how can we best leverage tribal ties to create a better strategy of engaging Afghan villages? How can we better target terrorist networks?
Our work, “Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets,” will be presented at the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) as a full paper this August (16% acceptance rate, http://www.asonam2012.etu.edu.tr/). A pre-print is currently on the arXiv pre-print server at http://arxiv.org/abs/1205.4431.