Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · 2017 · 13 citations · 9 references
Social SciencesCommunicationComplex SystemsComputer NetworksInformation TheoryCommunication NetworksInformation DiffusionInformation SpreadInteraction NetworksNetwork PropagationNetwork TheoryInformation Diffusion ModelsInformation SpreadingMessage DiffusionPropagation AlgorithmsSocial Interaction Networks
We study the potential flow of information in interaction networks, that is, networks in which the interactions between the nodes are being recorded. The central notion in our study is that of an information channel. An information channel is a sequence of interactions between nodes forming a path in the network which respects the time order. As such, an information channel represents a potential way information could have flown in the interaction network. We propose algorithms to estimate information channels of limited time span from every node to other nodes in the network. We present one exact and one more efficient approximate algorithm. Both algorithms are one-pass algorithms. The approximation algorithm is based on an adaptation of the HyperLogLog sketch, which allows easily combining the sketches of individual nodes in order to get estimates of how many unique nodes can be reached from groups of nodes as well. We show how the results of our algorithm can be used to build efficient influence oracles for solving the Influence maximization problem which deals with finding top k seed nodes such that the information spread from these nodes is maximized. Experiments show that the use of information channels is an interesting data-driven and model-independent way to find top k influential nodes in interaction networks.
9
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Mining knowledge-sharing sites for viral marketing
Matthew Richardson, Pedro Domingos · 2002 · 1.6K citations
Patterns of Cascading Behavior in Large Blog Graphs
Jure Leskovec, Mary McGlohon, Christos Faloutsos et al. · 2007 · 566 citations