Finding Influential Nodes in a Social Network from Information Diffusion Data
Published 1 January 2009
Masahiro Kimura, Kazumi Saito, Ryohei Nakano, Hiroshi Motoda
Citations44
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We address the problem of ranking influential nodes in complex social networks by estimating diffusion probabilities from observed information diffusion data using the popular independent cascade (IC) model. For this purpose we formulate the likelihood for information diffusion data which is a set of time sequence data of active nodes and propose an iterative method to search for the probabilities that maximizes this likelihood. We apply this to two real world social networks in the simplest setting where the probability is uniform for all the links, and show that the accuracy of the probability is outstandingly good, and further show that the proposed method can predict the high ranked influential nodes much more accurately than the well studied conventional four heuristic methods.
Keywords
Computer SciencePhysics and Astronomy
Cambridge University Press eBooksSocial Network Analysis
17,041 Citations1994Stanley Wasserman, Katherine Faust
This paper presents mathematical representation of social networks in the social and behavioral sciences through the lens of dyadic and triadic interaction models, which provide insights into the structure and dynamics of relationships between actors and groups.
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Maximizing the spread of influence through a social network
7,314 Citations2003David Kempe, Jon Kleinberg +1 more
An analysis framework based on submodular functions shows that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models, and suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.
NatureError and attack tolerance of complex networks
7,218 Citations2000Réka Albert, Hawoong Jeong +1 more
It is found that scale-free networks, which include the World-Wide Web, the Internet, social networks and cells, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates.
Mining the network value of customers
2,868 Citations2001Pedro Domingos, Matt Richardson
It is proposed to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively, taking advantage of the availability of large relevant databases.
Mining knowledge-sharing sites for viral marketing
1,635 Citations2002Matthew Richardson, Pedro Domingos
This research optimize the amount of marketing funds spent on each customer, rather than just making a binary decision on whether to market to him, and takes into account the fact that knowledge of the network is partial, and that gathering that knowledge can itself have a cost.
Maximizing the spread of influence through a social network
1,078 Citations2003David Kempe, Jon Kleinberg +1 more
Information diffusion through blogspace
1,045 Citations2004Daniel Gruhl, R. Guha +2 more
A macroscopic characterization of topic propagation through the authors' corpus is presented, formalizing the notion of long-running "chatter" topics consisting recursively of "spike" topics generated by outside world events, or more rarely, by resonances within the community.
ACM SIGKDD Explorations NewsletterInformation diffusion through blogspace
951 Citations2004Daniel Gruhl, David Liben‐Nowell +2 more
A macroscopic characterization of topic propagation through the authors' corpus, formalizing the notion of long-running "chatter" topics consisting recursively of "spike" topics generated by outside world events, or more rarely, by resonances within the community.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEmail networks and the spread of computer viruses
796 Citations2002M. E. J. Newman, Stephanie Forrest +1 more
Empirically the structure of this network of connections between individuals over which the virus spreads is investigated using data drawn from a large computer installation, and the implications for the understanding and prevention of computer virus epidemics are discussed.
Lecture notes in computer scienceTractable Models for Information Diffusion in Social Networks
440 Citations2006Masahiro Kimura, Kazumi Saito
This paper proposes two natural special cases of the Independent Cascade Model such that a good estimate of this quantity can be efficiently computed and experimentally demonstrates that for extracting influential nodes, the proposed models can provide novel ranking methods that are different from the ICM, typical methods of social network analysis, and “PageRank” method.
Lecture notes in computer sciencePrediction of Information Diffusion Probabilities for Independent Cascade Model
434 Citations2008Kazumi Saito, Ryohei Nakano +1 more
This work presents a method for predicting diffusion probabilities by using the EM algorithm, and defines the likelihood for information diffusion episodes, where an episode means a sequence of newly active nodes.
Tracking Information Epidemics in Blogspace
411 Citations2005Eytan Adar, Lada A. Adamic
This paper describes a novel inference scheme that takes advantage of data describing historical, repeating patterns of "infection" to track information flow in blogspace, as well as a visualization system that allows for the graphical tracking of information flow.
The dynamics of viral marketing
396 Citations2006Jure Leskovec, Lada A. Adamic +1 more
A model is presented that successfully identifies product and pricing categories for which viral marketing seems to be very effective and how the recommendation network grows over time and how effective it is from the viewpoint of the sender and receiver of the recommendations is established.
Mining knowledge-sharing sites for viral marketing
216 Citations2002Matthew Richardson, Pedro Domingos
Link analysis, eigenvectors and stability
203 Citations2001Andrew Y. Ng, Alice X. Zheng +1 more
This paper addresses the question of when HITS and PageRank can be expected to give stable rankings under small perturbations to the hyperlink patterns, using tools from matrix perturbation theory and Markov chain theory.
The American SurgeonExtracting influential nodes for information diffusion on a social network
180 Citations2007Masahiro Kimura, Kazumi Saito +1 more
This paper proposes a method of efficiently estimating all those quantities on the basis of bond percolation and graph theory, and applies it to approximately solving the optimization problem under the greedy algorithm, and demonstrates that it can outperform the conventional method, and achieve a large reduction in computational cost.
National Conference on Artificial IntelligenceMinimizing the spread of contamination by blocking links in a network
117 Citations2008Masahiro Kimura, Kazumi Saito +1 more
This work proposes a method for efficiently finding a good approximate solution to the problem of minimizing the propagation of undesirable things by blocking a limited number of links in a network based on a naturally greedy strategy and demonstrates experimentally that the proposed method significantly outperforms conventional link-removal methods.