nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

A Stochastic Approach for Extracting Community-Based Backbones

verfasst von : Zakariya Ghalmane, Mohamed-El-Amine Brahmia, Mourad Zghal, Hocine Cherifi

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Large-scale dense networks are very parvasive in various fields such as communication, social analytics, architecture, bio-metrics, etc. Thus, the need to build a compact version of the networks allowing their analysis is a matter of great importance. One of the main solutions to reduce the size of the network while maintaining its characteristics is backbone extraction techniques. Two types of methods are distinguished in the literature: similar nodes are gathered and merged in coarse-graining techniques to compress the network, while filter-based methods discard edges and nodes according to some statistical properties. In this paper, we propose a filtering-based approach which is based on the community structure of the network. The so-called “Acquaintance-Overlapping Backbone (AOB)” is a stochastic method which select overlapping nodes and the most connected nodes of the network. Experimental results show that the AOB is more effective in preserving relevant information as compared to some alternative methods.

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 DC-RST: A Parallel Algorithm for Random Spanning Trees in Network Analytics

Nächstes Kapitel Correcting Output Degree Sequences in Chung-Lu Random Graph Generation

Sporns, O.: Graph theory methods: applications in brain networks. Dialogues in clinical neuroscience (2022)

Herrera, M., Pérez-Hernández, M., Kumar Parlikad, A., Izquierdo, J.: Multi-agent systems and complex networks: Review and applications in systems engineering. Processes 8(3), 312 (2020)CrossRef

Soloviev, V., Solovieva, V., Tuliakova, A., Hostryk, A., Pichl, L.: Complex networks theory and precursors of financial crashes. In: CEUR Workshop Proceedings (2020)

Gfeller, D., De Los Rios, P.: Spectral coarse graining of complex networks. Phys. Rev. Lett. 99(3), 038701 (2007)CrossRef

Chen, M., Li, L., Wang, B., Cheng, J., Pan, L., Chen, X.: Effectively clustering by finding density backbone based-on kNN. Pattern Recogn. 60, 486–498 (2016)CrossRef

Goh, K.I., Salvi, G., Kahng, B., Kim, D.: Skeleton and fractal scaling in complex networks. Phys. Rev. Lett. 96(1), 018701 (2006)CrossRef

Grady, D., Thiemann, C., Brockmann, D.: Robust classification of salient links in complex networks. Nat. Commun. 3(1), 1–10 (2012)CrossRef

Zhang, X., Zhu, J.: Skeleton of weighted social network. Phys. A Stat. Mechan. Appl. 392(6), 1547–1556 (2013)CrossRef

Simas, T., Correia, R.B., Rocha, L.M.: The distance backbone of complex networks. J. Complex Netw. 9(6), cnab021 (2021)

10.

Serrano, M.Á., Boguná, M., Vespignani, A.: Extracting the multiscale backbone of complex weighted networks. Proc. Nat. Acad. Sci. 106(16), 6483–6488 (2009)CrossRef

11.

Zhang, R.J., Stanley, H.E., Ye, F.Y.: Extracting h-backbone as a core structure in weighted networks. Sci. Rep. 8(1), 1–7 (2018)

12.

Ghalmane, Z., Cherifi, C., Cherifi, H., El Hassouni, M.: Extracting backbones in weighted modular complex networks. Sci. Rep. 10(1), 1–18 (2020)CrossRef

13.

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)

14.

Cherifi, H., Palla, G., Szymanski, B.K., Lu, X.: On community structure in complex networks: challenges and opportunities. Appl. Netw. Sci. 4(1), 1–35 (2019)CrossRef

15.

Fortunato, S., Hric, D.: Community detection in networks: a user guide. Phys. Rep. 659, 1–44 (2016)CrossRef

16.

Xu, Y.: A spectral method to detect community structure based on the communicability modularity. Phys. A Stat. Mech. Appl. 537, 122751 (2020)CrossRefMATH

17.

Guo, K., He, L., Chen, Y., Guo, W., Zheng, J.: A local community detection algorithm based on internal force between nodes. Appl. Intell. 50(2), 328–340 (2020)CrossRef

18.

Ghalmane, Z., El Hassouni, M., Cherifi, C., Cherifi, H.: Centrality in modular networks. EPJ Data Sci. 8(1), 15 (2019)CrossRef

19.

Tulu, M.M., Hou, R., Younas, T.: Identifying influential nodes based on community structure to speed up the dissemination of information in complex network. IEEE Access 6, 7390–7401 (2018)CrossRef

20.

Ghalmane, Z., El Hassouni, M., Cherifi, H.: Betweenness centrality for networks with non-overlapping community structure. In: 2018 IEEE Workshop on Complexity in Engineering (COMPENG), pp. 1–5. IEEE (2018)

21.

Xu, E.H., Hui, P.M.: Uncovering complex overlapping pattern of communities in large-scale social networks. Appl. Netw. Sci. 4(1), 1–16 (2019)CrossRef

22.

Jiang, H., Liu, Z., Liu, C., Su, Y., Zhang, X.: Community detection in complex networks with an ambiguous structure using central node based link prediction. Knowl.-Based Syst. 195, 105626 (2020)CrossRef

23.

Saxena, R., Kaur, S., Bhatnagar, V.: Social centrality using network hierarchy and community structure. Data Mining Knowl. Discovery 32(5), 1421–1443 (2018)CrossRefMATH

24.

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)

25.

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

26.

Ma, H., Yang, H., Zhou, K., Zhang, L., Zhang, X.: A local-to-global scheme-based multi-objective evolutionary algorithm for overlapping community detection on large-scale complex networks. Neural Comput. Appl. 33(10), 5135–5149 (2021)CrossRef

27.

Ghalmane, Z., Cherifi, C., Cherifi, H., Hassouni, M.E.: Centrality in complex networks with overlapping community structure. Sci. Rep. 9(1), 1–29 (2019)CrossRef

28.

Taghavian, F., Salehi, M., Teimouri, M.: A local immunization strategy for networks with overlapping community structure. Phys. A Stat. Mech. Appl. 467, 148–156 (2017)CrossRef

29.

Yang, J., Leskovec, J.: Structure and overlaps of ground-truth communities in networks. ACM Trans. Intell. Syst. Technol. (TIST) 5(2), 1–35 (2014)CrossRef

30.

Kudelka, M., Ochodkova, E., Zehnalova, S., Plesnik, J.: Ego-zones: non-symmetric dependencies reveal network groups with large and dense overlaps. Appl. Netw. Sci. 4(1), 1–49 (2019)CrossRef

31.

Tarkowski, M., Szczepański, P., Rahwan, T., Michalak, T., Wooldridge, M.: Closeness centrality for networks with overlapping community structure. Proc. AAAI Conf. Artif. Intell. 30(1) (2021)

32.

Wang, X.F., Chen, G.: Complex networks: small-world, scale-free and beyond. IEEE Circ. Syst. Mag. 3(1), 6–20 (2003)CrossRef

33.

Ghalmane, Z., Cherifi, C., Cherifi, H., El Hassouni, M.: Exploring hubs and overlapping nodes interactions in modular complex networks. IEEE Access 8, 79650–79683 (2020)CrossRef

Titel: A Stochastic Approach for Extracting Community-Based Backbones
verfasst von: Zakariya Ghalmane
Mohamed-El-Amine Brahmia
Mourad Zghal
Hocine Cherifi
Verlag: Springer International Publishing
Buch: Complex Networks and Their Applications XI
Print ISBN: 978-3-031-21130-0

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

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-21131-7_5

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