Maximizing the Spread of Influence via Generalized Degree Discount

It is a crucial and fundamental issue to identify a small subset of influential spreaders that can control the spreading process in networks. In previous studies, a degree-based heuristic called DegreeDiscount has been shown to effectively identify multiple influential spreaders and has severed as a...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2016-10, Vol.11 (10), p.e0164393-e0164393
Main Authors: Wang, Xiaojie, Zhang, Xue, Zhao, Chengli, Yi, Dongyun
Format: Article
Language:English
Subjects:
Algorithms
Benchmarks
Computer and Information Sciences
Computer Simulation
Decomposition
Efficiency
Empirical analysis
Heuristic
Heuristic methods
Identification methods
Immunization
Information Dissemination - methods
Information Systems
Internet
Medicine and Health Sciences
Methods
Networks
People and Places
Physical Sciences
Physics
Probability
Research and Analysis Methods
Science
Semantic web
Semantics
Social networks
Social Sciences
Spreaders
Statistical mechanics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is a crucial and fundamental issue to identify a small subset of influential spreaders that can control the spreading process in networks. In previous studies, a degree-based heuristic called DegreeDiscount has been shown to effectively identify multiple influential spreaders and has severed as a benchmark method. However, the basic assumption of DegreeDiscount is not adequate, because it treats all the nodes equally without any differences. To consider a general situation in real world networks, a novel heuristic method named GeneralizedDegreeDiscount is proposed in this paper as an effective extension of original method. In our method, the status of a node is defined as a probability of not being influenced by any of its neighbors, and an index generalized discounted degree of one node is presented to measure the expected number of nodes it can influence. Then the spreaders are selected sequentially upon its generalized discounted degree in current network. Empirical experiments are conducted on four real networks, and the results show that the spreaders identified by our approach are more influential than several benchmark methods. Finally, we analyze the relationship between our method and three common degree-based methods.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0164393