Skip to main content
SpringerLink
Log in

RETRACTED ARTICLE: A dynamic clustering based method in community detection

  • Published:
Cluster Computing Aims and scope Submit manuscript

This article was retracted on 05 December 2022

This article has been updated

Abstract

Social networks are growing, community detection has become one of the hot topics in social network research. As various types of social networks continue to emerge, universal community detection approaches are becoming increasingly important. As the real community division is dynamic, the community structure will appear or disappear with the passage of time. Therefore, the authenticity and real-time of the division become the core foundation of community detection, and the design of a real-time algorithm based on real division has great challenges. In this paper, we propose a dynamic community detection algorithm dynamic clustering by fast search and find of density peaks (D-CFSFDP) based on the partition of nodes-follow relationships to improve the accuracy and adaptability of real complex community detection. In D-CFSFDP, a distance metric based on trust is defined, the user relationship in the social network is quantified as a distance matrix, and the size of the matrix element is used to measure the degree of the user relationship. Then we use kernel density estimation on the distance matrix, and compile the statistics of the impact of each node in the network. We combine the improved KD-Tree model and mean integrated squared error criterion to improve the calculation flow, so that it adapts to different sizes of data sets to improve the calculation accuracy. Based on the principle of density peak clustering and the community attributes, the internal structure and natural outside structure of the community can be obtained according to the distance between the nodes. Finally, the remaining nodes are allocated by distance to the corresponding community to complete the community division. The static community division is further extended to a dynamic detection algorithm that gets linear time complexity. Therefore, we can change the community structure by updating the node relationships in the network. Through the visualization software we can observed that, the D-CFSFDP algorithm give the results of community division with a clear natural and internal hierarchical structure. With the increase of community scale and difficulty of division, D-CFSFDP algorithm has excellent stability. In the real data set and the Douban network, the community division is more close to the real division result, the adaptability is good and the feasibility and validity are verified.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

Change history

References

  1. Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)

    Article  MathSciNet  Google Scholar 

  2. Newman, M.E.: Communities, modules and large-scale structure in networks. Nat. Phys. 8(1), 25 (2012)

    Article  Google Scholar 

  3. Hric, D., Darst, R.K., Fortunato, S.: Community detection in networks: structural communities versus ground truth. Phys. Rev. E 90(6), 062805 (2014)

    Article  Google Scholar 

  4. Nascimento, M.C., De Carvalho, A.C.: Spectral methods for graph clustering-a survey. Eur. J. Oper. Res. 211(2), 221–231 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Shen, H., Cheng, X., Cai, K., Hu, M.B.: Detect overlapping and hierarchical community structure in networks. Physica A 388(8), 1706–1712 (2009)

    Article  Google Scholar 

  6. Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004)

    Article  Google Scholar 

  7. Newman, M.E.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69(6), 066133 (2004)

    Article  Google Scholar 

  8. Muff, S., Rao, F., Caflisch, A.: Local modularity measure for network clusterizations. Phys. Rev. E 72(5), 056107 (2005)

    Article  Google Scholar 

  9. Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582 (2006)

    Article  Google Scholar 

  10. Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. 2008(10), P10008 (2008)

    Article  MATH  Google Scholar 

  11. Lancichinetti, A., Fortunato, S.: Limits of modularity maximization in community detection. Phys. Rev. E 84(6), 066122 (2011)

    Article  Google Scholar 

  12. Sun, P.G., Gao, L., Yang, Y.: Maximizing modularity intensity for community partition and evolution. Inf. Sci. 236, 83–92 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  13. Donetti, L., Munoz, M.A.: Detecting network communities: a new systematic and efficient algorithm. J. Stat. Mech. 2004(10), P10012 (2004)

    Article  MATH  Google Scholar 

  14. Papadopoulos, S., Kompatsiaris, Y., Vakali, A., Spyridonos, P.: Community detection in social media. Data Min. Knowl. Discov. 24(3), 515–554 (2012)

    Article  Google Scholar 

  15. Van Dongen, S.M.: Graph clustering by flow simulation (Doctoral dissertation) (2001)

  16. Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)

    Article  Google Scholar 

  17. Huang, J., Sun, H., Liu, Y., Song, Q., Weninger, T.: Towards online multiresolution community detection in large-scale networks. PLoS ONE 6(8), e23829 (2011)

    Article  Google Scholar 

  18. Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA 101(9), 2658–2663 (2004)

    Article  Google Scholar 

  19. Luo, F., Wang, J.Z., Promislow, E.: Exploring local community structures in large networks. Web Intell. Agent Syst. 6(4), 387–400 (2008)

    Article  Google Scholar 

  20. Chen, J., Zaïane, O., Goebel, R.: Local community identification in social networks. In: Social Network Analysis and Mining, 2009. ASONAM’09. International Conference on Advances, pp. 237–242. IEEE (2009)

  21. Barber, M.J., Clark, J.W.: Detecting network communities by propagating labels under constraints. Phys. Rev. E 80(2), 026129 (2009)

    Article  Google Scholar 

  22. Leung, I.X., Hui, P., Lio, P., Crowcroft, J.: Towards real-time community detection in large networks. Phys. Rev. E 79(6), 066107 (2009)

    Article  Google Scholar 

  23. Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)

    Article  MATH  Google Scholar 

  24. Kumpula, J.M., Kivelä, M., Kaski, K., Saramäki, J.: Sequential algorithm for fast clique percolation. Phys. Rev. E 78(2), 026109 (2008)

    Article  Google Scholar 

  25. Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. arXiv preprint arXiv:0903.3178 (2009)

  27. Adomavicius, G., Tuzhilin, A.: Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng. 17(6), 734–749 (2005)

    Article  Google Scholar 

  28. Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)

    Article  Google Scholar 

  29. Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. 105(4), 1118–1123 (2008)

    Article  Google Scholar 

  30. Zhou, H.: Network landscape from a Brownian particle’s perspective. Phys. Rev. E 67(4), 041908 (2003)

    Article  Google Scholar 

  31. Liu, W., Pellegrini, M., Wang, X.: Detecting communities based on network topology. Sci. Rep. 4, 5739 (2014)

    Article  Google Scholar 

  32. Agarwal, G., Kempe, D.: Modularity-maximizing graph communities via mathematical programming. Eur. Phys. J. B 66(3), 409–418 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  33. Rodriguez, A., Laio, A.: Clustering by fast search and find of density peaks. Science 344(6191), 1492–1496 (2014)

    Article  Google Scholar 

  34. Hennig, C., Hausdorf, B.: Design of dissimilarity measures: a new dissimilarity between species distribution areas. In: Data Science and Classification, pp. 29–37. Springer, Berlin (2006)

  35. Takaffoli, M.: Community evolution in dynamic social networks–challenges and problems. In: Proceedings 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW), pp. 1211–1214. IEEE (2011)

  36. Giatsoglou, M., Vakali, A.: Capturing social data evolution using graph clustering. IEEE Internet Comput. 17(1), 74–79 (2013)

    Article  Google Scholar 

  37. Cuzzocrea, A., Folino, F., Pizzuti, C.: DynamicNet: an effective and efficient algorithm for supporting community evolution detection in time-evolving information networks. In: Proceedings of the 17th International Database Engineering & Applications Symposium, pp. 148–153. ACM (2013)

  38. Zang, L., Wang, H., Ma, X.F.: Community evolution mining in dynamic social network. Jisuanji Gongcheng/ Comput. Eng. 39(6), 12 (2013)

    Google Scholar 

  39. Nguyen, N.P., Dinh, T.N., Xuan, Y., Thai, M.T.: Adaptive algorithms for detecting community structure in dynamic social networks. In: Proceedings IEEE INFOCOM, 2011, pp. 2282–2290. IEEE (2011)

  40. Mucha, P.J., Richardson, T., Macon, K., Porter, M.A., Onnela, J.P.: Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980), 876–878 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  41. Ziegler, C.N., Lausen, G.: Analyzing correlation between trust and user similarity in online communities. In: ITrust, Vol. 2995, pp. 251–265 (2004)

Download references

Author information

Authors and Affiliations

  1. School of Electrical and Information Engineering, Tianjin University, Tianjin, China

    Rui Zhang, Zhigang Jin & Peixuan Xu

  2. Tianjin Sino-German University of Applied Sciences, Tianjin, China

    Rui Zhang

  3. The National Computer Network Emergency Response, Technical Team/Coordination Center of China, Beijing, China

    Xiaohui Liu

Authors
  1. Rui Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhigang Jin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peixuan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiaohui Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhigang Jin.

Additional information

This article has been retracted. Please see the retraction notice for more detail:https://doi.org/10.1007/s10586-022-03860-4

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, R., Jin, Z., Xu, P. et al. RETRACTED ARTICLE: A dynamic clustering based method in community detection. Cluster Comput 22 (Suppl 3), 5703–5717 (2019). https://doi.org/10.1007/s10586-017-1472-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-017-1472-5

Keywords

Search

Navigation