Cited By
View all- Kurdi HAlnasser SAlhelal M(2015)AuthenticPeerInternational Journal of Distributed Sensor Networks10.1155/2015/6378312015(9-9)Online publication date: 1-Jan-2015
On the selection of information sources for gossip spreading
Article No.: 38, Page 38
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.
References
[1]
S. Selvakennedy and S. Sinnappan, "An adaptive data dissemination strategy for wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 3, no. 1, pp. 23-40, 2007.
[2]
C. Boldrini, M. Conti, and A. Passarella, "Contentplace: socialaware data dissemination in opportunistic networks," in Proceedings of the 11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWiM '08), pp. 203-210, October 2008.
[3]
W. Gao and G. Cao, "User-centric data dissemination in disruption tolerant networks," in Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM '11), pp. 3119-3127, April 2011.
[4]
Z. Li, G. Xie, K. Hwang, and Z. Li, "Churn-resilient protocol for massive data dissemination in P2P networks," IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 8, pp. 1342-1349, 2011.
[5]
H. Zhao and J. Zhu, "Efficient data dissemination in urban VANETs: parked vehicles are natural infrastructures," International Journal of Distributed Sensor Networks, vol. 2012, Article ID 151795, 11 pages, 2012.
[6]
W. Dong, Y. Yang, and W. Zhang, "Gossiping with message splitting on structured networks," International Journal of Distributed Sensor Networks, vol. 2015, Article ID 504581, 8 pages, 2015.
[7]
R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, "Randomized rumor spreading," in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 565-574, Redondo Beach, Calif, USA, November 2000.
[8]
D. Shah, Gossip Algorithms, Now Publishers, 2009.
[9]
J. Tang, S. Dai, J. Li, and S. Li, "Gossip-based scalable directed diffusion for wireless sensor networks," International Journal of Communication Systems, vol. 24, no. 11, pp. 1418-1430, 2011.
[10]
Z. Huang and Q. Huang, "To reach consensus using uninorm aggregation operator: a gossip-based protocol," International Journal of Intelligent Systems, vol. 27, no. 4, pp. 375-395, 2012.
[11]
A. Vahdat and D. Becker, "Epidemic routing for partially connected Ad hoc networks," Tech. Rep. CS-200006, Duke University, 2000.
[12]
S. Sanghavi, B. Hajek, and L. Massoulie, "Gossiping with multiple messages," IEEE Transactions on Information Theory, vol. 53, no. 12, pp. 4640-4654, 2007.
[13]
F. Chierichetti, S. Lattanzi, and A. Panconesi, "Rumor spreading in social networks," Theoretical Computer Science, vol. 412, no. 24, pp. 2602-2610, 2011.
[14]
T. Sauerwald, "On mixing and edge expansion properties in randomized broadcasting," Algorithmica, vol. 56, no. 1, pp. 51- 88, 2010.
[15]
G. Giakkoupis and T. Sauerwald, "Rumor spreading and vertex expansion," in Proceedings of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), pp. 1623-1641, 2012.
[16]
W. Dong, W. Zhang, and G. Wei, "Extracting influential information sources for gossiping," in Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton '12), pp. 1438-1444, Monticello, Ill, USA, October 2012.
[17]
D. Kempe, J. Kleinberg, and E. Tardos, "Maximizing the spread of influence through a social network," in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), pp. 137-146, Washington, DC, USA, August 2003.
[18]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. Vanbriesen, and N. Glance, "Cost-effective outbreak detection in networks," in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '07), pp. 420-429, August 2007.
[19]
B. Han, P. Hui, V. S. A. Kumar, M. V. Marathe, G. Pei, and A. Srinivasan, "Cellular traffic offloading through opportunistic communications: a case study," in Proceedings of the 5th ACM Workshop on Challenged Networks (CHANTS '10), pp. 31-38, ACM, September 2010.
[20]
R. M. Karp, Reducibility Among Combinatorial Problems, Springer, Berlin, Germany, 1972.
[21]
G. Wilfong and P. Winkler, "Ring routing and wavelength translation," in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '98), pp. 333-341, 1998.
[22]
N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire, "Femtocaching: wireless video content delivery through distributed caching helpers," in Proceedings of the 31st IEEE International Conference on Computer Communications (INFOCOM '12), pp. 1107-1115, 2012.
[23]
P. Holme and J. Saramäki, "Temporal networks," Physics Reports, vol. 519, no. 3, pp. 97-125, 2012.
[24]
M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, Cambridge, UK, 2005.
[25]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, "An analysis of approximations for maximizing submodular set functions--I," Mathematical Programming, vol. 14, no. 1, pp. 265-294, 1978.
[26]
Z. Drezner and H.W. Hamacher, Facility Location: Applications and Theory, Springer, 2004.
[27]
A. Krause, A. Singh, and C. Guestrin, "Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies," Journal of Machine Learning Research, vol. 9, no. 1, pp. 235-284, 2008.
[28]
K. Son, H. Kim, Y. Yi, and B. Krishnamachari, "Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks," IEEE Journal on Selected Areas in Communications, vol. 29, no. 8, pp. 1525-1536, 2011.
[29]
U. Feige, "A threshold of ln n for approximating set cover," Journal of the ACM, vol. 45, no. 4, pp. 634-652, 1998.
[30]
P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388- 404, 2000.
[31]
D. J. Watts and S. H. Strogatz, "Collective dynamics of 'smallworld' networks," Nature, vol. 393, no. 6684, pp. 440-442, 1998.
[32]
A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, 1999.
[33]
M. E. Newman, "The structure of scientific collaboration networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 98, no. 2, pp. 404-409, 2001.
[34]
J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations," in Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '05), pp. 177-187, Chicago, Ill, USA, August 2005.
[35]
S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, Cambridge, UK, 1994.
- On the selection of information sources for gossip spreading
Recommendations
Heterogeneous gossip
Middleware '09: Proceedings of the 10th ACM/IFIP/USENIX International Conference on MiddlewareGossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale ...
Simple, fast and deterministic gossip and rumor spreading
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithmsWe study gossip algorithms for the rumor spreading problem which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message ...
On spreading recommendations via social gossip
SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architecturesThis paper introduces and analyzes a variant of distributed gossip which is motivated by the sharing of recommendations in a social network. The social settings bear two implications on gossip. First, rumors fade after a few hops, and so does our gossip ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Hindawi Limited
London, United Kingdom
Publication History
Accepted: 04 March 2015
Published: 01 January 2015
Received: 16 December 2014
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 6Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
Cited By
View all- Kurdi HAlnasser SAlhelal M(2015)AuthenticPeerInternational Journal of Distributed Sensor Networks10.1155/2015/6378312015(9-9)Online publication date: 1-Jan-2015
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in