nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Hierarchical Overlapping Community Detection for Weighted Networks

verfasst von : Petr Prokop, Pavla Dráždilová, Jan Platoš

Erschienen in: Complex Networks & Their Applications XII

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Real-world networks often contain community structures, where nodes form tightly interconnected clusters. Recent research indicates hierarchical organization, where vertices split into groups that further subdivide across multiple scales. However, individuals in social networks typically belong to multiple communities due to their various affiliations, such as family, friends, and colleagues. These overlaps will emerge in the community structure of online social networks and other complex networks like in biology, where nodes have diverse functions. In this work, we propose an algorithm for hierarchical overlapping community detection in weighted networks. The overlap between clusters is realized via maximal cliques that are used as base elements for hierarchical agglomerative clustering on the graph (GHAC). The closed trail distance and the size of the maximal clique in overlap are used for the dissimilarity between clusters in agglomerative steps of the GHAC. The closed trail distance is designed for weighted networks.

Experiments on synthetic networks and different evaluations of the results of experiments show that the proposed algorithm is comparable with other widely used algorithms for overlapping community detection and is efficient for detecting hierarchy structure in weighted networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Signature-Based Community Detection for Time Series

Nächstes Kapitel Detecting Community Structures in Patients with Peripheral Nervous System Disorders

Adamcsek, B., Palla, G., Farkas, I.J., Derényi, I., Vicsek, T.: CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics 22(8), 1021–1023 (2006)CrossRef

Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466(7307), 761–764 (2010)

Altaf-Ul-Amin, M., Shinbo, Y., Mihara, K., Kurokawa, K., Kanaya, S.: Development and implementation of an algorithm for detection of protein complexes in large interaction networks. BMC Bioinform. 7, 1–13 (2006)CrossRef

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)CrossRef

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

Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRef

Brzozowski, Ł., Siudem, G., Gagolewski, M.: Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering (2023). arXiv preprint arXiv:2303.12212

Castrillo, E., León, E., Gómez, J.: Fast heuristic algorithm for multi-scale hierarchical community detection. In: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pp. 982–989 (2017)

Clauset, A., Moore, C., Newman, M.E.: Hierarchical structure and the prediction of missing links in networks. Nature 453(7191), 98–101 (2008)CrossRef

10.

Collins, L.M., Dent, C.W.: Omega: a general formulation of the rand index of cluster recovery suitable for non-disjoint solutions. Multivar. Behav. Res. 23(2), 231–242 (1988)CrossRef

11.

Dao, V., Bothorel, C., Lenca, P.: Community structure: a comparative evaluation of community detection methods. CoRR abs/1812.06598 (2018). http://arxiv.org/abs/1812.06598

12.

El Ayeb, S., Hemery, B., Jeanne, F., Cherrier, E., Charrier, C.: Evaluation metrics for overlapping community detection. In: 2022 IEEE 47th Conference on Local Computer Networks (LCN), pp. 355–358. IEEE (2022)

13.

Farkas, I., Ábel, D., Palla, G., Vicsek, T.: Weighted network modules. New J. Phys. 9(6), 180 (2007)CrossRef

14.

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

15.

Gupta, S.K., Singh, D.P., Choudhary, J.: A review of clique-based overlapping community detection algorithms. Knowl. Inf. Syst. 64(8), 2023–2058 (2022)CrossRef

16.

Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80(1), 016118 (2009)

17.

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

18.

Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PloS One 6(4), e18961 (2011)

19.

Lázár, A., Abel, D., Vicsek, T.: Modularity measure of networks with overlapping communities. EPL (Europhysics Letters) 90(1), 18001 (2010)

20.

Lee, C., Reid, F., McDaid, A., Hurley, N.: Detecting highly overlapping community structure by greedy clique expansion (2010). arXiv preprint arXiv:1002.1827

21.

Li, M., Chen, J.e., Wang, J.x., Hu, B., Chen, G.: Modifying the DPClus algorithm for identifying protein complexes based on new topological structures. BMC Bioinform. 9(1), 1–16 (2008)

22.

Li, T., et al.: Hierarchical community detection by recursive partitioning. J. Am. Stat. Assoc. pp. 1–18 (2020)

23.

Li, X.L., Foo, C.S., Tan, S.H., Ng, S.K.: Interaction graph mining for protein complexes using local clique merging. Genome Inform. 16(2), 260–269 (2005)

24.

Lu, H., Sang, X., Zhao, Q., Lu, J.: Community detection algorithm based on nonnegative matrix factorization and improved density peak clustering. IEEE Access 8, 5749–5759 (2020)CrossRef

25.

Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)

26.

Porter, M.A., Onnela, J.P., Mucha, P.J.: Communities in networks. Not. AMS 56(9), 1082–1097 (2009)MathSciNet

27.

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)

28.

Riolo, M.A., Cantwell, G.T., Reinert, G., Newman, M.E.J.: Efficient method for estimating the number of communities in a network. CoRR abs/1706.02324 (2017). http://arxiv.org/abs/1706.02324

29.

Rossetti, G.: graph benchmark handling community dynamics. J. Complex Netw. 5(6), 893–912 (2017)CrossRef

30.

Rossetti, G., Milli, L., Cazabet, R.: CDLIB: a python library to extract, compare and evaluate communities from complex networks. Appl. Netw. Sci. 4(1), 1–26 (2019)CrossRef

31.

Rossetti, G., Pappalardo, L., Rinzivillo, S.: A novel approach to evaluate community detection algorithms on ground truth. In: Cherifi, H., Gonçalves, B., Menezes, R., Sinatra, R. (eds.) Complex Networks VII. SCI, vol. 644, pp. 133–144. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30569-1_10CrossRef

32.

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

33.

Saoud, B., Moussaoui, A.: Node similarity and modularity for finding communities in networks. Phys. A 492, 1958–1966 (2018)CrossRef

34.

Schaub, M.T., Li, J., Peel, L.: Hierarchical community structure in networks. Phys. Rev. E 107(5), 054305 (2023)

35.

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

36.

Shen, H.W., Cheng, X.Q., Guo, J.F.: Quantifying and identifying the overlapping community structure in networks. J. Stat. Mech. Theor. Exp. 2009(07), P07042 (2009)

37.

Simon, H.A.: The architecture of complexity. Proc. Am. Philos. Soc. 106(6), 467–482 (1962)

38.

Snášel, V., Dráždilová, P., Platoš, J.: Closed trail distance in a biconnected graph. Plos One 13(8), e0202181 (2018)

39.

Snášel, V., Dráždilová, P., Platoš, J.: Cliques are bricks for k-CT graphs. Mathematics 9(11), 1160 (2021)CrossRef

40.

Suurballe, J.W., Tarjan, R.E.: A quick method for finding shortest pairs of disjoint paths. Networks 14(2), 325–336 (1984)MathSciNetCrossRef

41.

Vieira, V.D.F., Xavier, C.R., Evsukoff, A.G.: A comparative study of overlapping community detection methods from the perspective of the structural properties. Appl. Netw. Sci. 5, 51 (2020)

42.

Wasserman, S., Faust, K.: Social network analysis: Methods and applications, vol. 8. Cambridge University Press (1994)

43.

Xie, J., Szymanski, B.K., Liu, X.: SLPA: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th International Conference on Data Mining Workshops, pp. 344–349. IEEE (2011)

44.

Yang, J., Leskovec, J.: Overlapping community detection at scale: a nonnegative matrix factorization approach. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 587–596 (2013)

45.

Zhang, X., Wang, C., Su, Y., Pan, L., Zhang, H.F.: A fast overlapping community detection algorithm based on weak cliques for large-scale networks. IEEE Trans. Comput. Soc. Syst. 4(4), 218–230 (2017)CrossRef

46.

Zhang, Y., Levina, E., Zhu, J.: Detecting overlapping communities in networks using spectral methods. SIAM J. Math. Data Sci. 2(2), 265–283 (2020)MathSciNetCrossRef

47.

Zhao, Y., Li, S., Wang, S.: Agglomerative clustering based on label propagation for detecting overlapping and hierarchical communities in complex networks. Adv. Complex Syst. 17(06), 1450021 (2014)

Titel: Hierarchical Overlapping Community Detection for Weighted Networks
verfasst von: Petr Prokop
Pavla Dráždilová
Jan Platoš
Verlag: Springer Nature Switzerland
Buch: Complex Networks & Their Applications XII
Print ISBN: 978-3-031-53498-0

Electronic ISBN: 978-3-031-53499-7

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-53499-7_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner