In a “tipping” model, each node in a social network, representing anindividual, adopts a property or behavior if a certain number of his incomingneighbors currently exhibit the same. In viral marketing, a key problem is toselect an initial “seed” set from the network such that the entire networkadopts any behavior given to the seed. Here we introduce a method for quicklyfinding seed sets that scales to very large networks. Our approach finds a setof nodes that guarantees spreading to the entire network under the tippingmodel. After experimentally evaluating 31 real-world networks, we found thatour approach often finds seed sets that are several orders of magnitude smallerthan the population size and outperform nodal centrality measures in mostcases. In addition, our approach scales well – on a Friendster social networkconsisting of 5.6 million nodes and 28 million edges we found a seed set inunder 3.6 hours. Our experiments also indicate that our algorithm providessmall seed sets even if high-degree nodes are removed. Lastly, we find thathighly clustered local neighborhoods, together with dense network-widecommunity structures, suppress a trend’s ability to spread under the tippingmodel.
See on springpad.com