document: Maximizing the spread of influence through a social network Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains , including the diffusion of medical and technological innovations , the sudden and widespread adoption of various strategies in game-theoretic settings , and the effects of `` word of mouth '' in the promotion of new products . Recently , motivated by the design of viral marketing strategies , Domingos and Richardson posed a fundamental algorithmic problem for such social network processes : if we can try to convince a subset of individuals to adopt a new product or innovation , and the goal is to trigger a large cascade of further adoptions , which set of individuals should we target ? We consider this problem in several of the most widely studied models in social network analysis . The optimization problem of selecting the most influential nodes is NP-hard here , and we provide the first provable approximation guarantees for efficient algorithms . Using an analysis framework based on submodular functions , we show that a natural greedy strategy obtains a solution that is provably within 63 % of optimal for several classes of models ; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks . We also provide computational experiments on large collaboration networks , showing that in addition to their provable guarantees , our approximation algorithms significantly out-perform node-selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O B I O