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

A novel robust memetic algorithm for dynamic community structures detection in complex networks

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

Networks in the real world are dynamic and evolving. The most critical process in networks is to determine the structure of the community, based on which we can detect hidden communities in a complex network. The design of strong network structures is of great importance, meaning that a system must maintain its function in the face of attacks and failures and have a strong community structure. In this paper, we proposed the robust memetic algorithm and used the idea to optimize the detection of dynamic communities in complex networks called RDMA_NET (Robust Dynamic Memetic Algorithm). In this method, we work on dynamic data that affects the two main parts of the initial population value and the calculation of the evaluation function of each population, and there is no need to determine the number of communities in advance. We used two sets of real-world networks and the LFR dataset. The results show that our proposed method, RDMA_Net, can find a better solution than modern approaches and provide near-optimal performance in search of network topologies with a strong community structure.

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

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Algorithm 1
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14

Similar content being viewed by others

Data availability

The datasets used in this paper are publicly available in the following links.

http://snap.stanford.edu/data.

https://west.uni-koblenz.de/konect.

https://networkrepository.com.

http://staff.icar.cnr.it/pizzuti/codes.html.

References

  1. Midoun, M., Wang, X., Talhaoui, M.Z.: A pyramidal community detection algorithm based on a generalization of the clustering coefficient. J. Ambient. Intell. Human. Comput. 12, 9111–9125 (2021)

    Article  Google Scholar 

  2. Zahiri, M., Mohammadzadeh, J., Hariri, S.: An improved Girvan–Newman community detection algorithm using trust-based centrality. J. Ambient Intell. Human Comput. 14, 3755–3766 (2021)

    Article  Google Scholar 

  3. Sathyakala, M., Sangeetha, M.: A weak clique-based multi-objective genetic algorithm for overlapping community detection in complex networks. J. Ambient. Intell. Humaniz. Comput. 12, 6761–6771 (2021)

    Article  Google Scholar 

  4. Al-Andoli, M., Cheah, W.P., Tan, S.C.: Deep learning-based community detection in complex networks with network partitioning and reduction of trainable parameters. J. Ambient Intell. Human. Comput. 12, 2527–2545 (2021)

    Article  Google Scholar 

  5. Shang, R., Zhang, W., Zhang, J., Feng, J., Jiao, L.: Local community detection based on higher-order structure and edge information. Physica A 587, 126513 (2022)

    Article  Google Scholar 

  6. Dong, Y., Ding, Z., Chiclana, F., Viedma, E.: Dynamics of public opinions in an online and offline social network. IEEE Trans. Big Data. 7, 610–618 (2018)

    Article  Google Scholar 

  7. Eustace, J., Wang, X., Cui, Y.: Community detection using local neighborhood in complex networks. Physica A 436, 665–677 (2015)

    Article  ADS  MathSciNet  Google Scholar 

  8. Wang, X., Qin, X.: Asymmetric intimacy and algorithm for detecting communities in bipartite networks. Physica A 462, 569–578 (2016)

    Article  ADS  Google Scholar 

  9. Cui, Y., Wang, X.: Detecting one-mode communities in bipartite networks by bipartite clustering triangular. Physica A 457, 307–315 (2016)

    Article  ADS  Google Scholar 

  10. Zarezadeh, M., Nourani, E., Bouyer, A.: DPNLP: distance-based peripheral nodes label propagation algorithm for community detection in social networks. World Wide Web 25, 73–98 (2022)

    Article  Google Scholar 

  11. Tang, Z., Tang, Y., Li, C., et al.: A fast local community detection algorithm in complex networks. World Wide Web 24, 1929–1955 (2021)

    Article  Google Scholar 

  12. Liu, F., Wu, J., Xue, S., et al.: Detecting the evolving community structure in dynamic social networks. World Wide Web 23, 715–733 (2020)

    Article  Google Scholar 

  13. Bhih, A., Johnson, P., Randles, M.: An optimization tool for robust community detection algorithms using content and topology information. J. Supercomput. 76, 226–254 (2020)

    Article  Google Scholar 

  14. He, Ch., Tang, Y., Liu, H., Fei, X., Li, H., Liu, Sh.: A robust multi-view clustering method for community detection combining link and content information. Physica A 514, 396–411 (2019)

    Article  ADS  MathSciNet  Google Scholar 

  15. Jose, T., Babu, S.S.: Detecting spammers on the social network through clustering technique. J. Ambient Intell. Human Comput. Published online. (2019). https://doi.org/10.1007/s12652-019-01541-6

  16. Tastan, A., Muma, M., Zoubir, A.: Sparsity-aware robust community detection (SPARCODE). Signal Process. 187, 108–147 (2021)

    Article  Google Scholar 

  17. Martinet, L., Kramer, M., Viles, W., Perkins, L., Spencer, E., Chu, C., Cash, S., Kolaczyk, E.: Robust dynamic community detection with applications to human brain functional networks. Nat. Commun. 11, 2785 (2020)

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  18. Xu, J., Yang, Y., Wang, C., Liu, Z., Zhang, J., Chen, L., Lu, J.: Robust network enhancement from flawed networks. IEEE Trans. Knowl. Data Eng. 34(7), 3507–3520 (2022)

    Google Scholar 

  19. Zhang, Y., Xia, X., Xu, X., Yu, F.: Robust Hierarchical overlapping community detection with personalized PageRank. IEEE Access. 8 (2020)

  20. Ding, X., Zhang, J., Yang, J.: A robust two-stage algorithm for local community detection. Knowl.-Based Syst. 152, 188–199 (2018)

    Article  Google Scholar 

  21. Jin, D., Wang, X., He, D., Dang, J., Zhang, W.: Robust detection of link communities with summary description in social networks. IEEE Trans. Knowl. Data Eng. 33, 2737–2749 (2021)

    Article  Google Scholar 

  22. Zhou, J., Chen, Z., Du, M., Chen, L.: Robust ECD: Enhancement of network structure for robust community detection. IEEE Trans. Knowl. Data Eng. 35, 842–856 (2023)

    Google Scholar 

  23. Al-Sharoa, E., Ababneh, B., Alkhassaweneh, M.: Robust community detection in graphs. IEEE Access 9, 118757–118770 (2021)

    Article  Google Scholar 

  24. Liua, W., Gonga, M., Wang, S., Maa, L.: A two-level learning strategy based memetic algorithm for enhancing community robustness of networks. Inf. Sci. 422, 290–304 (2018)

    Article  Google Scholar 

  25. He, Ch., Zhang, Q., Tang, Y., Liu, S., Zheng, J.: Community detection method based on robust semi-supervised nonnegative matrix factorization. Physica A 523, 279–291 (2019)

    Article  ADS  MathSciNet  Google Scholar 

  26. Morone, F., Makse, H.A.: Influence maximization in complex networks through optimal percolation. Nature. 524, 65–68 (2015)

    Article  ADS  CAS  PubMed  Google Scholar 

  27. Hao, Y., Han, J., Lin, Y., Liu, L.: Vulnerability of complex networks under three-level-tree attacks. Physica A 462, 674–683 (2016)

    Article  ADS  MathSciNet  Google Scholar 

  28. Wang, Z., Bauch, C.T., Bhattacharyya, S., d’Onofrio, A., Manfredi, P., Perc, M.: Statistical physics of vaccination. Phys. Rep. 664, 1–113 (2016)

    Article  ADS  MathSciNet  Google Scholar 

  29. Tsugawa, S., Kimura, K.: Identifying influencers from sampled social networks. Physica A 507, 294–303 (2018)

    Article  ADS  Google Scholar 

  30. Melchionna, A., Caloca, J., Squires, S., Antonsen, T.M., Ott, E., Girvan, M.: Impact of imperfect information on network attack. Phys. Rev. E 91(3), 032807 (2015)

    Article  ADS  Google Scholar 

  31. Wang, B., Gu, Y., Zheng, D.: Community detection in error-prone environments based on particle cooperation and competition with distance dynamics. Physica A 607, 128178 (2022)

    Article  MathSciNet  Google Scholar 

  32. Otsuka, M., Tsugawa, S.: Robustness of network attack strategies against node sampling and link errors. PLoS One. 14(9), e0221885 (2019). https://doi.org/10.1371/journal.pone.0221885

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  33. Lu, Z., Li, X.F.: Attack vulnerability of network controllability. PLoS One. 11(9), e0162289 (2016). https://doi.org/10.1371/journal.pone.0162289

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  34. Nasiri, E., Berahmand, K., Li, Y.: Robust graph regularization nonnegative matrix factorization for link prediction in attributed networks. Multimed. Tools Appl. 82(3), 3745–3768 (2023)

    Article  Google Scholar 

  35. Folino, F., Pizzuti, C.: An evolutionary multi-objective approach for community discovery in dynamic networks. IEEE Trans. Knowl. Data Eng. 3, 1838–1852 (2014)

    Article  Google Scholar 

  36. Zhan, W., Deng, L., Guan, J., Niu, J.: Revealing dynamic communities in networks using genetic algorithm with merging and splitting operators. Physica A 558, 124897 (2020)

    Article  Google Scholar 

  37. Traag, V.A., Aldecoa, R., Delvenne, J.C.: Detecting communities using asymptotical surprise. Phys. Rev. E 92, 022816 (2015)

    Article  ADS  CAS  Google Scholar 

  38. Zarayeneh, N., Kalyanaraman, N. A.: A fast and efficient incremental approach toward dynamic. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (2019)

  39. Yin, Y., Zhao, Y., Li, H., Dong, X.: Multi-objective evolutionary clustering for large-scale dynamic community detection. Inf. Sci. 549, 269–287 (2021)

    Article  MathSciNet  Google Scholar 

  40. Li, H., Chen, F., Zhang, J.: An incremental dynamic community detection algorithm based on node participation. IEEE 6th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA) (2021)

  41. Arasteh, M., Alizadeh, S., Lee, C.G.: Gravity algorithm for the community detection of a large-scale network. J. Ambient Intell. Human Comput. 14, 1217–1228 (2023)

    Article  Google Scholar 

  42. Chen, J., Liu, D., Hao, F.: Community detection in the dynamic signed network: an intimacy evolutionary clustering algorithm. J. Ambient Intell. Human. Comput. 11, 891–900 (2020)

    Article  Google Scholar 

  43. Berahmand, K., Bouyer, A., Vasighi, M.: Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes. IEEE Trans. Comput. Soc. Syst. 5(4), 1021–1033 (2018)

    Article  Google Scholar 

  44. Enugala, R., Rajamani, L., Kadampur, A., Kurapati, S.: Community detection in dynamic social networks. Int. J. Res. Appl. 2(6), 278–285 (2015)

    Google Scholar 

  45. Hassani, M., Behnamian, J.: A scenario-based robust optimization with a pessimistic approach for nurse rostering problem. J. Comb. Optim. 41, 143–169 (2021)

    Article  MathSciNet  Google Scholar 

  46. Schneider, C.M., Moreira, A.A., Andrade, J.S., Jr., Havlin, S., Herrmann, H.J.: Mitigation of malicious attacks on networks. Proc. Natl. Acad. Sci. U.S.A. 108, 3838 (2011)

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  47. Zeng, A., Liu, W.: Enhancing network robustness against malicious attacks. Phys. Rev. E 85(6), 06613 (2012)

    Article  MathSciNet  Google Scholar 

  48. Ma, L., Gong, M., Cai, Q., Jiao, L.: Enhancing community integrity of networks against multilevel targeted attacks. Phys. Rev. E 88, 022810 (2013)

    Article  ADS  Google Scholar 

  49. Handle, J., Knowles, J.: An evolutionary approach to multi-objective clustering. Trans. Evol. Comput. 11, 56–76 (2007)

    Article  Google Scholar 

  50. Kumar, S., Hanot, R.: Community detection algorithms in complex networks: a survey. Adv. Signal Process. Intell. Recognit. Syst. 1365, 202–215 (2021)

    Article  Google Scholar 

  51. Naeni, L.M., Berretta, R., Moscato, P.: MA-Net: A reliable memetic algorithm for community detection by modularity optimization. In: Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, 311–323 (2015)

  52. Rotta, R., Noack, A.: Multilevel local search algorithms for modularity clustering. J. Exp. Algorithmic 6(2), 1594–1605 (2011)

    Google Scholar 

  53. Wang, P., Gao, L., Ma, X.: Dynamic community detection based on network structural perturbation and topological similarity. J. Stat. Mech. 2017(1), 013401 (2017)

    Article  MathSciNet  Google Scholar 

  54. Zeng, X., Wang, W., Chen, C.: A consensus community-based particle swarm optimization for dynamic community detection. IEEE Trans. Cybern. 50(6), 2502–2513 (2019)

    Article  PubMed  Google Scholar 

  55. Wang, C.H., Deng, Y., Li, X., Chen, J., Gao, C.H.: Dynamic community detection based on a label-based swarm intelligence. IEEE Access. 7, 161641–161653 (2019)

    Article  Google Scholar 

  56. Greene, D., Doyle, D., Cunningham, P.: Tracking the evolution of communities in dynamic social networks. In International Conference on Advances in Social Networks Analysis and Mining (2010)

Download references

Funding

This paper received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

    Somayeh Ranjkesh & Seyyed Mohsen Hashemi

  2. Department of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

    Behrooz Masoumi

Authors
  1. Somayeh Ranjkesh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Behrooz Masoumi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Seyyed Mohsen Hashemi
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed equally in writing this paper. All authors reviewed the manuscript.

Corresponding author

Correspondence to Behrooz Masoumi.

Ethics declarations

Ethical approval

This paper has no human or animal sample.

Competing interests

The authors declare no competing interests.

Additional information

Publisher's Note

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

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ranjkesh, S., Masoumi, B. & Hashemi, S.M. A novel robust memetic algorithm for dynamic community structures detection in complex networks. World Wide Web 27, 3 (2024). https://doi.org/10.1007/s11280-024-01238-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11280-024-01238-7

Keywords

Search

Navigation