nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2023 | Original Article

Fast local community discovery relying on the strength of links

verfasst von: Mohammadmahdi Zafarmand, Yashar Talebirad, Eric Austin, Christine Largeron, Osmar R. Zaïane

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2023

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Community detection methods aim to find nodes connected to each other more than other nodes in a graph. As they explore the entire network, global methods suffer from severe limitations when handling large networks due to their time and space complexity. Local community detection methods are based on an egocentric function aiming to find only the community containing a query node (or set of query nodes). However, existing local methods are often sensitive to which query node(s) is used to discover a particular community. Our proposed approach, called SIWO “Strong In, Weak Out,” is a novel community detection method, which can locally discover densely-connected communities precisely, deterministically, and quickly. Moreover, our experimental evaluation shows that the detected community is not dependent on the initial query node within a community. This method works in a one-node-expansion way based on the notions of strong and weak links in a graph. In short, SIWO starts with a community consisting only of the query node(s). Then it checks the set of nodes in the community’s neighborhood in each step to add the “best” node and finally returns the desired community around the given query node. It can also be used iteratively to detect the entire partitioning of a network with or without considering overlapping communities, and concurrently identify outliers that may not belong in any community. Moreover, as it does not store the entire graph into main memory, it can also be used to find the core of a community on very large networks, while there is limited time and memory available. Finally, SIWO is also able to handle weighted graphs, making SIWO a general framework for community discovery and detection in various type of social networks.

Vorheriger Artikel A satin optimized dynamic learning model (SODLM) for sentiment analysis using opinion mining

Nächster Artikel Effectiveness of data augmentation to predict students at risk using deep learning algorithms

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 "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

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

https://networkit.github.io/.

Code available via request to authors.

https://snap.stanford.edu/mappr/code.html.

https://github.com/kit-algo/LCD-cliques-experiments.

https://sites.psu.edu/yuchenbian/files/2019/08/MWC_release.zip.

https://github.com/talebirad/SIWO

https://github.com/GiulioRossetti/cdlib.

https://github.com/benedekrozemberczki/EdMot.

https://bit.ly/3q1QBJj.

Adamic LA, Glance N (2005) The political blogosphere and the 2004 U.S. Election: divided they blog. In: Proceedings of the 3rd international workshop on link discovery. LinkKDD ’05. Association for Computing Machinery, New York, NY, USA, pp 36–43. https://doi.org/10.1145/1134271.1134277

Akbas E, Zhao P (2017) Truss-based community search. Proc VLDB Endow 10(11):1298–1309. https://doi.org/10.14778/3137628.3137640CrossRef

Andersen R, Chung F, Lang K (2006) Local graph partitioning using pagerank vectors. In: 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06), pp 475–486. https://doi.org/10.1109/FOCS.2006.44

Bagrow JP, Bollt EM (2005) Local method for detecting communities. Phys Rev E 72:046108. https://doi.org/10.1103/PhysRevE.72.046108CrossRef

Baltsou G, Christopoulos K, Tsichlas K (2022) Local community detection: a survey. IEEE Access 10:110701–110726CrossRef

Barbieri N, Bonchi F, Galimberti E, Gullo F (2015) Efficient and effective community search. Data Min Knowl Disc 29(5):1406–1433. https://doi.org/10.1007/s10618-015-0422-1MathSciNetCrossRef

Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A (2004) The architecture of complex weighted networks. Proc Natl Acad Sci 101(11):3747–3752. https://doi.org/10.1073/pnas.0400087101CrossRef

Bian Y, Ni J, Cheng W, Zhang X (2017) Many heads are better than one: local community detection by the multi-walker chain. In: 2017 IEEE international conference on data mining (ICDM), pp 21–30. https://doi.org/10.1109/ICDM.2017.11

Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 2008(10):10008. https://doi.org/10.1088/1742-5468/2008/10/p10008CrossRef

Brunato M, Hoos HH, Battiti R (2008) On effectively finding maximal quasi-cliques in graphs. In: Maniezzo V, Battiti R, Watson J-P (eds) Learning and Intelligent Optimization. Springer, Berlin, pp 41–55CrossRef

Chen J, Zaïane OR, Goebel R (2010) In: Memon N, Alhajj R (eds) Detecting communities in social networks using local information. Springer, Vienna, pp 197–214. https://doi.org/10.1007/978-3-7091-0294-7_11

Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132. https://doi.org/10.1103/physreve.72.026132CrossRef

Cui W, Xiao Y, Wang H, Lu Y, Wang W (2013) Online search of overlapping communities. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data. SIGMOD ’13. Association for Computing Machinery, New York, NY, USA, pp 277–288. https://doi.org/10.1145/2463676.2463722

Cui W, Xiao Y, Wang H, Wang W (2014) Local search of communities in large graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data. SIGMOD ’14. Association for Computing Machinery, New York, NY, USA, pp 991–1002. https://doi.org/10.1145/2588555.2612179

Danon L, Díaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech Theory Exp 2005(09):09008–09008. https://doi.org/10.1088/1742-5468/2005/09/p09008CrossRef

Dao VL, Bothorel C, Lenca P (2020) Community structure: a comparative evaluation of community detection methods. Netw Sci 8(1):1–41. https://doi.org/10.1017/nws.2019.59CrossRef

De Meo P, Ferrara E, Fiumara G, Provetti A (2014) Mixing local and global information for community detection in large networks. J Comput Syst Sci 1:72–87MathSciNetCrossRef

Dilmaghani S, Brust MR, Danoy G, Bouvry P (2021) Community detection in complex networks: a survey on local approaches. In: Asian conference intelligent information and database systems, pp 757–767

Fagnan J, Zaïane O, Barbosa D (2014) Using triads to identify local community structure in social networks. In: IEEE/ACM international conference on advances in social networks analysis and mining, pp 108–112. https://doi.org/10.1109/ASONAM.2014.6921568

Fang Y, Huang X, Qin L, Zhang Y, Zhang W, Cheng R, Lin X (2019) A survey of community search over big graphs. VLDB J 29(1):353–392. https://doi.org/10.1007/s00778-019-00556-xCrossRef

Fang Y, Yang Y, Zhang W, Lin X, Cao X (2020) Effective and efficient community search over large heterogeneous information networks. Proc VLDB Endow 13(6):854–867. https://doi.org/10.14778/3380750.3380756CrossRef

Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174. https://doi.org/10.1016/j.physrep.2009.11.002MathSciNetCrossRef

Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1–44. https://doi.org/10.1016/j.physrep.2016.09.002MathSciNetCrossRef

Gharaghooshi SZ, Zaiane OR, Largeron C, Zafarmand M, Liu C (2020) Addressing the resolution limit and the field of view limit in community mining. In: Symposium on intelligent data analysis (IDA’20)

Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826. https://doi.org/10.1073/pnas.122653799MathSciNetCrossRef

Granovetter M (1983) The strength of weak ties: a network theory revisited. Sociol Theory 1:201–233. https://doi.org/10.2307/202051CrossRef

Hamann M, Röhrs E, Wagner D (2017) Local community detection based on small cliques. Algorithms 10(3):90. https://doi.org/10.3390/a10030090MathSciNetCrossRef

Huang J, Sun H, Liu Y, Song Q, Weninger T (2011) Towards online multiresolution community detection in large-scale networks. PLOS ONE 6(8):1–11. https://doi.org/10.1371/journal.pone.0023829CrossRef

Huang X, Lakshmanan LVS, Yu JX, Cheng H (2015) Approximate closest community search in networks. Proc VLDB Endow 9(4):276–287. https://doi.org/10.14778/2856318.2856323CrossRef

Huang X, Lakshmanan LVS, Xu J (2019) Community search over big graphs. Synth Lect Data Manag 14(6):1–206. https://doi.org/10.2200/s00928ed1v01y201906dtm061CrossRef

Huang X, Cheng H, Qin L, Tian W, Yu JX (2014) Querying k-truss community in large and dynamic graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data. SIGMOD ’14. Association for Computing Machinery, New York, NY, USA, pp 1311–1322. https://doi.org/10.1145/2588555.2610495

Kwak H, Lee C, Park H, Moon S (2010) What is twitter, a social network or a news media? In: Proceedings of the 19th international conference on world wide web, New York, NY, USA, pp 591–600 . https://doi.org/10.1145/1772690.1772751

Lancichinetti A, Fortunato S (2009) Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E 80(1):016118. https://doi.org/10.1103/physreve.80.016118CrossRef

Lancichinetti A, Fortunato S (2011) Limits of modularity maximization in community detection. Phys Rev E 84(6):066122. https://doi.org/10.1103/physreve.84.066122CrossRef

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110. https://doi.org/10.1103/physreve.78.046110CrossRef

Li P-Z, Huang L, Wang C-D, Lai J-H (2019) Edmot: an edge enhancement approach for motif-aware community detection. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’19. Association for Computing Machinery, New York, NY, USA, pp 479–487. https://doi.org/10.1145/3292500.3330882

Luo W, Zhang D, Jiang H, Ni L, Hu Y (2018) Local community detection with the dynamic membership function. IEEE Trans Fuzzy Syst 26(5):3136–3150. https://doi.org/10.1109/tfuzz.2018.2812148CrossRef

Luo D, Bian Y, Yan Y, Liu X, Huan J, Zhang X (2020) Local community detection in multiple networks. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’20. Association for Computing Machinery, New York, NY, USA, pp 266–274. https://doi.org/10.1145/3394486.3403069

Luo F, Wang JZ, Promislow E (2006) Exploring local community structures in large networks. In: 2006 IEEE/WIC/ACM international conference on web intelligence (WI 2006 main conference proceedings)(WI’06), pp 233–239. https://doi.org/10.1109/WI.2006.72

Lusseau D (2003) The emergent properties of a dolphin social network. Proc R Soc Lond Ser B Biol Sci 270:S186–S188. https://doi.org/10.1098/rsbl.2003.0057CrossRef

Milo R (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824–827. https://doi.org/10.1126/science.298.5594.824CrossRef

Onnela J-P, Saramäki J, Kertész J, Kaski K (2005) Intensity and coherence of motifs in weighted complex networks. Phys Rev E 71(6):065103. https://doi.org/10.1103/physreve.71.065103CrossRef

Opsahl T, Panzarasa P (2009) Clustering in weighted networks. Soc Netw 31(2):155–163. https://doi.org/10.1016/j.socnet.2009.02.002CrossRef

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

Peel L, Larremore DB, Clauset A (2017) The ground truth about metadata and community detection in networks. Sci Adv 3(5):1602548. https://doi.org/10.1126/sciadv.1602548CrossRef

Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: Yolum P, Güngör T, Gürgen F, Özturan C (eds) Computer and information sciences—ISCIS 2005. Springer, Berlin, pp 284–293

Rabbany R, Zaiane OR (2015) Evaluation of community mining algorithms in the presence of attributes. In: Li X-L, Cao T, Lim E-P, Zhou Z-H, Ho T-B, Cheung D (eds) Trends and applications in knowledge discovery and data mining. Lecture Notes in Computer Science. Springer, pp 152–163. https://doi.org/10.1007/978-3-319-25660-3_13

Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106. https://doi.org/10.1103/physreve.76.036106CrossRef

Rossetti G, Milli L, Cazabet R (2019) CDLIB: a python library to extract, compare and evaluate communities from complex networks. Appl Netw Sci 4:1–26. https://doi.org/10.1007/s41109-019-0165-9CrossRef

Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105(4):1118–1123. https://doi.org/10.1073/pnas.0706851105CrossRef

Rozemberczki B, Kiss O, Sarkar R (2020) Karate club: An API oriented open-source python framework for unsupervised learning on graphs. In: Proceedings of the 29th ACM international conference on information and knowledge management. https://doi.org/10.1145/3340531.3412757

Sakr S, Bonifati A, Voigt H, Iosup A, Ammar K, Angles R, Aref W, Arenas M, Besta M, Boncz PA, Daudjee K, Valle ED, Dumbrava S, Hartig O, Haslhofer B, Hegeman T, Hidders J, Hose K, Iamnitchi A, Kalavri V, Kapp H, Martens W, Özsu MT, Peukert E, Plantikow S, Ragab M, Ripeanu MR, Salihoglu S, Schulz C, Selmer P, Sequeda JF, Shinavier J, Szárnyas G, Tommasini R, Tumeo A, Uta A, Varbanescu AL, Wu H-Y, Yakovets N, Yan D, Yoneki E (2021) The future is big graphs: a community view on graph processing systems. Commun ACM 64(9):62–71. https://doi.org/10.1145/3434642CrossRef

Saramäki J, Kivelä M, Onnela J-P, Kaski K, Kertesz J (2007) Generalizations of the clustering coefficient to weighted complex networks. Phys Rev E 75(2):027105. https://doi.org/10.1103/physreve.75.027105CrossRef

Schaeffer SE (2007) Graph clustering. Comput Sci Rev 1(1):27–64. https://doi.org/10.1016/j.cosrev.2007.05.001CrossRef

Slater N, Itzchack R, Louzoun Y (2014) Mid size cliques are more common in real world networks than triangles. Netw Sci 2(3):387–402. https://doi.org/10.1017/nws.2014.22CrossRef

Souravlas S, Sifaleras A, Tsintogianni M, Katsavounis S (2021) A classification of community detection methods in social networks: a survey. Int J Gen Syst 50(1):63–91MathSciNetCrossRef

Sozio M, Gionis A (2010) The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’10. Association for Computing Machinery, New York, NY, USA, pp 939–948. https://doi.org/10.1145/1835804.1835923

Su X, Xue S, Liu F, Wu J, Yang J, Zhou C, Hu W, Paris C, Nepal S, Jin D, Sheng QZ, Yu PS (2022) A comprehensive survey on community detection with deep learning. IEEE Trans Neural Netw Learn Syst 1–21 (2022)

Su X, Xue S, Liu F, Wu J, Yang J, Zhou C, Hu W, Paris C, Nepal S, Jin D, Sheng Q, Yu P (2022) A comprehensive survey on community detection with deep learning. IEEE Trans Neural Netw Learn Syst 1–21. https://doi.org/10.1109/TNNLS.2021.3137396

Takaffoli M, Rabbany R, Zaiane OR (2013) Incremental local community identification in dynamic social networks. In: IEEE/ACM international conference on social networks analysis and mining

Traag VA, Waltman L, van Eck NJ (2019) From Louvain to Leiden: guaranteeing well-connected communities. Sci Rep 9(1):5233. https://doi.org/10.1038/s41598-019-41695-zCrossRef

Xu X, Yuruk N, Feng Z, Schweiger TAJ (2007) SCAN: A structural clustering algorithm for networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’07. Association for Computing Machinery, New York, NY, USA, pp 824–833. https://doi.org/10.1145/1281192.1281280

Yang J, Leskovec J (2013) Defining and evaluating network communities based on ground-truth. Knowl Inf Syst 42(1):181–213. https://doi.org/10.1007/s10115-013-0693-zCrossRef

Yang Z, Algesheimer R, Tessone CJ (2016) A comparative analysis of community detection algorithms on artificial networks. Sci Rep 6(1):1–18. https://doi.org/10.1038/srep30750CrossRef

Yin H, Benson AR, Leskovec J, Gleich DF (2017) Local higher-order graph clustering. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’17. Association for Computing Machinery, New York, NY, USA, pp 555–564. https://doi.org/10.1145/3097983.3098069

Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473. https://doi.org/10.1086/jar.33.4.3629752CrossRef

Zheng Z, Ye F, Li R-H, Ling G, Jin T (2017) Finding weighted k-truss communities in large networks. Inf Sci 417:344–360. https://doi.org/10.1016/j.ins.2017.07.012CrossRef

Titel: Fast local community discovery relying on the strength of links
verfasst von: Mohammadmahdi Zafarmand
Yashar Talebirad
Eric Austin
Christine Largeron
Osmar R. Zaïane
Publikationsdatum: 01.12.2023
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2023
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-023-01115-7

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2023

Sentiment analysis and emotion detection of post-COVID educational Tweets: Jordan case

Network-based control of epidemic via flattening the infection curve: high-clustered vs. low-clustered social networks

Machine learning algorithm-based spam detection in social networks

Assessment of text-generated supply chain risks considering news and social media during disruptive events

HatEmoTweet: low-level emotion classifications and spatiotemporal trends of hate and offensive COVID-19 tweets

Hashtag recommendation for enhancing the popularity of social media posts

Premium Partner