ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Overlapping influence of multiple spreaders in complex networks

  • 1.

    Department of Electronic Science and Technology, University of Science and Technology of China, Hefei 230027, China

  • 2.

    Department of Computer Science,Shenzhen University, Shenzhen, 518060

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2016.01.005
  • Received Date: 27 August 2015
  • Accepted Date: 29 September 2015
  • Rev Recd Date: 29 September 2015
  • Publish Date: 30 January 2016
    Abstract

  • Abstract

    With the development of computer technology and the Internet, network science is attracting many scientists from various fields. One field in network science is epidemic spreading, in which the key problem is the selection of source spreaders. Conventional methods select spreaders according to the importance of nodes (degree, betweenness and so on) and nodes with high importance are selected. Traditional methods perform well in characterizing the spreading ability of single nodes, but poorly in multiple nodes. An anahysis is made and the reasons poor performance of multiple spreaders is attributed to the overlapping influences that decrease the overall spreading ability of multiple nodes. Then, an improved method is proposed to suppress the overlapping influences. The validity of the proposed method is illustrated in four real-world networks in which the method could select better multiple spreaders. Further, it was found that improving the sparsity could reduce the overlapping influence of multiple spreaders, which enhances the overall spreading ability of nodes.

    Abstract

    With the development of computer technology and the Internet, network science is attracting many scientists from various fields. One field in network science is epidemic spreading, in which the key problem is the selection of source spreaders. Conventional methods select spreaders according to the importance of nodes (degree, betweenness and so on) and nodes with high importance are selected. Traditional methods perform well in characterizing the spreading ability of single nodes, but poorly in multiple nodes. An anahysis is made and the reasons poor performance of multiple spreaders is attributed to the overlapping influences that decrease the overall spreading ability of multiple nodes. Then, an improved method is proposed to suppress the overlapping influences. The validity of the proposed method is illustrated in four real-world networks in which the method could select better multiple spreaders. Further, it was found that improving the sparsity could reduce the overlapping influence of multiple spreaders, which enhances the overall spreading ability of nodes.
    • FullText(HTML)
  • loading
    • References(27)
  • [1]
    Boccaletti, S., et al., Complex networks: Structure and dynamics. Physics reports, 2006. 424(4): p. 175-308.
    [2]
    Strogatz S H. Exploring complex networks[J]. Nature, 2001. 410(6825): 268-276.
    [3]
    Diekmann O, Heesterbeek J A P. Mathematical epidemiology of infectious diseases: Model building, analysis and interpretation[M]. Chichester: John Wiley & Sons, 2000.
    [4]
    Chierichetti F, Lattanzi S, Panconesi A. Rumor spreading in social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2009: 375-386.
    [5]
    Staniford S, Paxson V, Weaver N. How to own the internet in your spare time[C]// Proceedings of the 11th USENIX Security Symposium. Berkeley, USA: ACM Press, 2002:149-167.
    [6]
    Kempe D, Kleinberg J, Tardos . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge discovery and Data Mining. Washington, USA: ACM Press, 2003: 137-146.
    [7]
    Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: ACM Press, 2009: 199-208.
    [8]
    苏晓萍, 申情，宋玉蓉，等. 利用社会网络上最有影响力节点实现高效病毒营销[J]. 小型微型计算机系统, 2014. 35(8): 1803-1807.
    Su Xiaoping, Shen Qing, Song Yurong, etal. Improving the efficiency of viral of marketing in a social network using influential nodes[J]. Jounal of Chinese Computer Systems,2014. 35(8): 1803-1807.
    [9]
    Kempe D, Kleinberg J, Tardos . Influential nodes in a diffusion model for social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2005: 1127-1138.
    [10]
    Chen D B, Lü L Y, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012. 391(4): 1777-1787.
    [11]
    Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
    [12]
    Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013. 377(14): 1031-1035.
    [13]
    Liu J G, Ren Z M, Guo Q. Ranking the spreading influence in complex networks. Physica A: Statistical Mechanics and its Applications, 2013. 392(18): 4154-4159.
    [14]
    任晓龙, 吕琳媛, 网络重要节点排序方法综述. 科学通报, 2014, 59(13): 1175-1197.
    Ren Xiaolong,Lü Linyuan. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.
    [15]
    刘建国, et al., 复杂网络中节点重要性排序的研究进展. 物理学报, 2013. 62(17): p. 178901-178901.
    [16]
    Chen D B, Gao H, Lü L, et al. Identifying influential nodes in large-scale directed networks: the role of clustering[J]. Plos One, 2013, 8(8): e77455.
    [17]
    Cha M, Haddadi H, Benevenuto F, et al. Measuring user influence in twitter: The million follower fallacy[C]// Proceedinds of the 4th International Conference on Weblogs and Social Media. Washington, USA: ACM Press, 2010, 14: 30.
    [18]
    Henderson K, Henderson K, Gallagher B, et al. Rolx: Structural role extraction & mining in large graphs[]CP// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China: ACM Press, 2012: 1231-1239.
    [19]
    Bakshy E, Hohman J M, Mason W, et al. Everyone's an influencer: Quantifying influence on twitter[C]// Proceedings of the 4th ACM International Conference on Web Search and Data Mining. Hong Kong, China: ACM Press, 2011: 65-74.
    [20]
    Hou B N, Yao Y P, Liao D B. Identifying all-around nodes for spreading dynamics in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012. 391(15): 4012-4017.
    [21]
    Gao S, Ma J, Chen Z M, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 403: 130-147.
    [22]
    Fu Y H, Huang C Y, Sun C T. Identifying super-spreader nodes in complex networks[J]. Mathematical Problems in Engineering, 2015, 2015: 675713(1-8).
    [23]
    Zou Y L, Chen G R. Choosing effective controlled nodes for scale-free network synchronization[J]. Physica A: Statistical Mechanics and its Applications, 2009. 388(14): 2931-2940.
    [24]
    汪小帆, 李翔, 陈关荣. 网络科学导论[J]. 北京: 高等教育出版社, 2012.
    [25]
    Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection[EB/OL]. http://snap.stanford.edu/data.
    [26]
    Song C M, Havlin S, Makse H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395.
    [27]
    Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009. 6(1): 29-123.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Boccaletti, S., et al., Complex networks: Structure and dynamics. Physics reports, 2006. 424(4): p. 175-308.
    [2]
    Strogatz S H. Exploring complex networks[J]. Nature, 2001. 410(6825): 268-276.
    [3]
    Diekmann O, Heesterbeek J A P. Mathematical epidemiology of infectious diseases: Model building, analysis and interpretation[M]. Chichester: John Wiley & Sons, 2000.
    [4]
    Chierichetti F, Lattanzi S, Panconesi A. Rumor spreading in social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2009: 375-386.
    [5]
    Staniford S, Paxson V, Weaver N. How to own the internet in your spare time[C]// Proceedings of the 11th USENIX Security Symposium. Berkeley, USA: ACM Press, 2002:149-167.
    [6]
    Kempe D, Kleinberg J, Tardos . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge discovery and Data Mining. Washington, USA: ACM Press, 2003: 137-146.
    [7]
    Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: ACM Press, 2009: 199-208.
    [8]
    苏晓萍, 申情，宋玉蓉，等. 利用社会网络上最有影响力节点实现高效病毒营销[J]. 小型微型计算机系统, 2014. 35(8): 1803-1807.
    Su Xiaoping, Shen Qing, Song Yurong, etal. Improving the efficiency of viral of marketing in a social network using influential nodes[J]. Jounal of Chinese Computer Systems,2014. 35(8): 1803-1807.
    [9]
    Kempe D, Kleinberg J, Tardos . Influential nodes in a diffusion model for social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2005: 1127-1138.
    [10]
    Chen D B, Lü L Y, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012. 391(4): 1777-1787.
    [11]
    Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
    [12]
    Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013. 377(14): 1031-1035.
    [13]
    Liu J G, Ren Z M, Guo Q. Ranking the spreading influence in complex networks. Physica A: Statistical Mechanics and its Applications, 2013. 392(18): 4154-4159.
    [14]
    任晓龙, 吕琳媛, 网络重要节点排序方法综述. 科学通报, 2014, 59(13): 1175-1197.
    Ren Xiaolong,Lü Linyuan. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.
    [15]
    刘建国, et al., 复杂网络中节点重要性排序的研究进展. 物理学报, 2013. 62(17): p. 178901-178901.
    [16]
    Chen D B, Gao H, Lü L, et al. Identifying influential nodes in large-scale directed networks: the role of clustering[J]. Plos One, 2013, 8(8): e77455.
    [17]
    Cha M, Haddadi H, Benevenuto F, et al. Measuring user influence in twitter: The million follower fallacy[C]// Proceedinds of the 4th International Conference on Weblogs and Social Media. Washington, USA: ACM Press, 2010, 14: 30.
    [18]
    Henderson K, Henderson K, Gallagher B, et al. Rolx: Structural role extraction & mining in large graphs[]CP// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China: ACM Press, 2012: 1231-1239.
    [19]
    Bakshy E, Hohman J M, Mason W, et al. Everyone's an influencer: Quantifying influence on twitter[C]// Proceedings of the 4th ACM International Conference on Web Search and Data Mining. Hong Kong, China: ACM Press, 2011: 65-74.
    [20]
    Hou B N, Yao Y P, Liao D B. Identifying all-around nodes for spreading dynamics in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012. 391(15): 4012-4017.
    [21]
    Gao S, Ma J, Chen Z M, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 403: 130-147.
    [22]
    Fu Y H, Huang C Y, Sun C T. Identifying super-spreader nodes in complex networks[J]. Mathematical Problems in Engineering, 2015, 2015: 675713(1-8).
    [23]
    Zou Y L, Chen G R. Choosing effective controlled nodes for scale-free network synchronization[J]. Physica A: Statistical Mechanics and its Applications, 2009. 388(14): 2931-2940.
    [24]
    汪小帆, 李翔, 陈关荣. 网络科学导论[J]. 北京: 高等教育出版社, 2012.
    [25]
    Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection[EB/OL]. http://snap.stanford.edu/data.
    [26]
    Song C M, Havlin S, Makse H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395.
    [27]
    Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009. 6(1): 29-123.)
    Recommended articles
    TrendMD
    Volume 46 Issue 1 page: 28-35
    Cover

    Article Metrics

    Article views (24) PDF downloads(72)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return