On the Selection of Information Sources for Gossip Spreading

Wenxiang Dong, Ying Yang and Wenyi Zhang

International Journal of Distributed Sensor Networks, 2015, vol. 11, issue 4, 276014

Abstract: Information diffusion is efficient via gossip or rumor spreading in many of the next generation networks. It is of great importance to select some seed nodes as information sources in a network so as to maximize the gossip spreading. In this paper, we deal with the issue of the selection of information sources, which are initially informed nodes (i.e., seed nodes) in a network, for pull-based gossip protocol. We prove that the gossip spreading maximization problem (GSMP) is NP-hard. We establish a temporal mapping of the gossip spreading process using virtual coupon collectors by leveraging the concept of temporal network, further prove that the gossip spreading process has the property of submodularity, and consequently propose a greedy algorithm for selecting the information sources, which yields a suboptimal solution within 1 - 1 / e of the optimal value for GSMP. Experiments are carried out to study the spreading performance, illustrating the significant superiority of the greedy algorithm over heuristic and random algorithms.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2015/276014 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:11:y:2015:i:4:p:276014

DOI: 10.1155/2015/276014

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().