Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A spiderweb model for community detection in dynamic networks

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Community detection in dynamic networks is one of the most challenging tasks in the field of network analysis. In general, networks often evolve smoothly between successive snapshots. Therefore, the community structure detected in each snapshot should not only be of high quality but also reflect the smoothness of the variations compared with the previous snapshot. In this paper, we propose a novel incremental community-detection method named Spiderweb, which detects the community structure in each snapshot by simulating the evolution of spiderwebs. We categorize the evolutionary events of the network into three types, and then address the changed nodes and edges according to three corresponding evolution rules. In this procedure, some nodes are assigned to proper communities. Then, we construct a new subgraph for the unclassified changed nodes, and detect its communities efficiently. Finally, we merge some communities to obtain the resulting community structure. We conduct extensive experiments on both artificial networks and real-world networks to test the proposed method, and the experimental results show the superiority of the proposed method over some state-of-the-art algorithms in terms of both the quality and the temporal smoothness of the detected community structures. The proposed method provides us with a stable and promising solution for the problem of community detection in dynamic networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. In our previous work, a parameter α is used to control the proportion of the common neighbors to the neighbors of u or v. According to the discussion of the parameter settings and the experimental results presented in [32], a setting of α = 0.5 is recommended for most networks. For the sake of simplicity, we remove the parameter α and use 0.5 directly here.

  2. The parameter β is used in our previous work, and for the same reason as α, we directly adopt the setting of β = 0.5 in this paper.

  3. http://cnerg.org

References

  1. Fortunato S (2009) . Phys Rep 486(3):75

    Google Scholar 

  2. Fortunato S, Hric D (2016) . Phys Rep 659:1. Community detection in networks: A user guide

    Article  MathSciNet  Google Scholar 

  3. Shang R, Shuang L, Zhang W, Stolkin R, Jiao L (2016) . Physica A Stat Mech Appl 453:203

    Article  Google Scholar 

  4. Brelger R, Carley K, Pattison P (2003) Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers

  5. Backstrom L, Huttenlocher D, Kleinberg J, Lan X In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006), pp. 44–C54

  6. Asur S, Parthasarathy S, Ucar D (2007) In: Acm sigkdd international conference on knowledge discovery & data mining

  7. Aynaud T, Fleury E, Guillaume J, Wang Q (2013) Communities in evolving networks: Definitions, Detection, and Analysis Techniques

  8. Amelio A, Pizzuti C (2017) . Comput Intell 33(2):181

    Article  MathSciNet  Google Scholar 

  9. Yun C, Song X, Zhou D, Hino K, Tseng BL (2009) . Acm Trans Knowl Discov Data 3(4):1

    Google Scholar 

  10. Kim MS, Han J (2009) . Proc Vldb Endow 2(1):622

    Article  Google Scholar 

  11. Spiliopoulou M, Ntoutsi I, Theodoridis Y, Schult R (2006) In: Twelfth acm sigkdd international conference on knowledge discovery & data mining

  12. Folino F, Pizzuti C (2014) . IEEE Trans Knowl Data Eng 26(8):1838

    Article  Google Scholar 

  13. Gergely P, Albert-Lászlá B, Tamás V (2007) . Nature 446(7136):664

    Article  Google Scholar 

  14. Greene D, Doyle D, Cunningham P (2010) In: 2010 International Conference on Advances in Social Networks Analysis and Mining, pp 176–183

  15. Blondel VD, Guillaume J, Lambiotte R, Lefebvre E (2008) . J Stat Mech Theory Exper 2008(10):P10008

    Article  Google Scholar 

  16. Aynaud T, Guillaume J (2010) In: 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, pp 513–519

  17. Lin YR, Yun C, Zhu S, Sundaram H, Tseng BL (2008) International conference on world wide web

  18. Kim MS, Han J (2009) . Proc VLDB Endow 2(1):622

    Article  Google Scholar 

  19. Yu W, Wang W, Jiao P, Li X (2019) . Knowl-Based Syst 167:1

    Article  Google Scholar 

  20. Pizzuti C (2018) . IEEE Trans Evol Comput 22(3):464

    Article  Google Scholar 

  21. Samie ME, Hamzeh A (2016) J Inf Sci 43(5):0165551516657717

  22. Niu X, Si W, Wu C (2017) . Comput Commun 108:110

    Article  Google Scholar 

  23. Zhou X, Zhao X, Liu Y (2018) . Appl Intell 48(9):3081

    Article  Google Scholar 

  24. Cazabet R, Amblard F, Hanachi C (2010) In: IEEE Second international conference on social computing

  25. Nguyen NP, Dinh TN, Ying X, Thai MT (2011) IEEE Infocom

  26. Xie J, Chen M, Szymanski BK (2013) Workshop on dynamic networks management & mining

  27. Han J, Li W, Zhao L, Su Z, Zou Y, Deng W (2017) Plos One 12(11)

  28. Sun H, Huang J, Zhang X, Liu J, Wang D, Liu H, Zou J, Song Q (2014) . Knowl-Based Syst 72:1

    Article  Google Scholar 

  29. Shang J, Liu L, Li X, Xie F, Wu C (2016) . Physica A Stat Mech Appl 443:70

    Article  Google Scholar 

  30. Agarwal P, Verma R, Agarwal A, Chakraborty T (2018) In: PAKDD

  31. Tabarzad MA, Hamzeh A (2018) Applied Intelligence (2):1

  32. Yang H, Cheng J, Leng M, Su X, Zhang W, Chen X (2019) Int J Modern Phys C 30(12):1950104

  33. Newman ME (2004) Phys Rev E 69(6):066133

  34. Newman ME, Girvan M (2004) Phys Rev E 69(2):026113

  35. Cheng J, Li L, Yang H, Li Q, Chen X (2018) Web and Big Data. In: Cai Y, Ishikawa Y, Xu J (eds) . Springer International Publishing, Cham, pp 90–104

  36. Leskovec J, Kleinberg J, Faloutsos C (2005) In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD ’05. ACM, New York, pp 177–187

  37. Tang X, Wang J, Liu B, Li M, Chen G, Pan Y (2011) . BMC Bioinform 12:339

    Article  Google Scholar 

  38. Klimt B, Yiming Y (2004) CEAS

  39. Gehrke J, Ginsparg P, Kleinberg J (2003) . Acm Sigkdd Explor Newslett 5(2):149

    Article  Google Scholar 

  40. Panzarasa P, Opsahl T, Carley KM (2009) . J Assoc Inf Sci Technol 60(5):911

    Article  Google Scholar 

  41. Chakraborty T, Sikdar S, Tammana V, Ganguly N, Mukherjee A (2013) In: 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp 426–433

  42. Rosvall M, Bergstrom CT (2008) . Proc Natl Acad Sci 105(4):1118

    Article  Google Scholar 

  43. Hao L, Li S, Zhao Y (2013) . Physica A Stat Mech Appl 392(14):3095

    Article  Google Scholar 

  44. Ana LNF, Jain AK (2003) In: 2003. Proceedings. 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol 2, pp II–128–II–133

  45. Zhang J, Ding X, Yang J (2019) . Knowl-Based Syst 165:407

    Article  Google Scholar 

  46. Ding X, Zhang J, Yang J (2020) . Knowl-Based Syst 105935:198

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Information Science and Engineering, Lanzhou University, Lanzhou, China

    Haijuan Yang, Jianjun Cheng, Xing Su, Wenbo Zhang, Shiyan Zhao & Xiaoyun Chen

  2. Department of Electronic Information Engineering, Lanzhou Vocational Technical College, Lanzhou, China

    Haijuan Yang

Authors
  1. Haijuan Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jianjun Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xing Su
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wenbo Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Shiyan Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Xiaoyun Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Jianjun Cheng or Xiaoyun Chen.

Ethics declarations

Conflict of interests

The authors declare that they have no conflict of interest.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, H., Cheng, J., Su, X. et al. A spiderweb model for community detection in dynamic networks. Appl Intell 51, 5157–5188 (2021). https://doi.org/10.1007/s10489-020-02059-7

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-020-02059-7

Keywords

Search

Navigation