{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:32:29Z","timestamp":1767339149090,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,8,11]],"date-time":"2017-08-11T00:00:00Z","timestamp":1502409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA 654\/22-2"],"award-info":[{"award-number":["WA 654\/22-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Community detection aims to find dense subgraphs in a network. We consider the problem of finding a community locally around a seed node both in unweighted and weighted networks. This is a faster alternative to algorithms that detect communities that cover the whole network when actually only a single community is required. Further, many overlapping community detection algorithms use local community detection algorithms as basic building block. We provide a broad comparison of different existing strategies of expanding a seed node greedily into a community. For this, we conduct an extensive experimental evaluation both on synthetic benchmark graphs as well as real world networks. We show that results both on synthetic as well as real-world networks can be significantly improved by starting from the largest clique in the neighborhood of the seed node. Further, our experiments indicate that algorithms using scores based on triangles outperform other algorithms in most cases. We provide theoretical descriptions as well as open source implementations of all algorithms used.<\/jats:p>","DOI":"10.3390\/a10030090","type":"journal-article","created":{"date-parts":[[2017,8,11]],"date-time":"2017-08-11T10:07:40Z","timestamp":1502446060000},"page":"90","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Local Community Detection Based on Small Cliques"],"prefix":"10.3390","volume":"10","author":[{"given":"Michael","family":"Hamann","sequence":"first","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Kaiserstr. 12, 76131 Karlsruhe, Germany"}]},{"given":"Eike","family":"R\u00f6hrs","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Kaiserstr. 12, 76131 Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Kaiserstr. 12, 76131 Karlsruhe, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2017,8,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: A user guide","volume":"659","author":"Fortunato","year":"2016","journal-title":"Phys. Rep."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Staudt, C., Marrakchi, Y., and Meyerhenke, H. (2014, January 27\u201330). Detecting communities around seed nodes in complex networks. Proceedings of the IEEE International Conference on Big Data, Washington, DC, USA.","DOI":"10.1109\/BigData.2014.7004373"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lancichinetti, A., Fortunato, S., and Kert\u00e9sz, J. (2009). Detecting the overlapping and hierarchical community structure of complex networks. New J. Phys., 11.","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0018961","article-title":"Finding Statistically Significant Communities in Networks","volume":"6","author":"Lancichinetti","year":"2011","journal-title":"PLoS ONE"},{"key":"ref_7","unstructured":"McDaid, A., and Hurley, N. (2010). Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure. arXiv."},{"key":"ref_8","unstructured":"Lee, C., Reid, F., McDaid, A., and Hurley, N. (2010). Detecting highly overlapping community structure by greedy clique expansion. arXiv."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"653670","DOI":"10.1155\/2014\/653670","article-title":"Local Community Detection in Complex Networks Based on Maximum Cliques Extension","volume":"2014","author":"Fanrong","year":"2014","journal-title":"Mathe. Probl. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2658","DOI":"10.1073\/pnas.0400054101","article-title":"Defining and identifying communities in networks","volume":"101","author":"Radicchi","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"056117","DOI":"10.1103\/PhysRevE.80.056117","article-title":"Community detection algorithms: A comparative analysis","volume":"80","author":"Lancichinetti","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"016118","DOI":"10.1103\/PhysRevE.80.016118","article-title":"Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities","volume":"80","author":"Lancichinetti","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1017\/nws.2016.20","article-title":"NetworKit: A tool suite for large-scale complex network analysis","volume":"4","author":"Staudt","year":"2016","journal-title":"Netw. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hamann, M., R\u00f6hrs, E., and Wagner, D. (2017). Local Community Detection Based on Small Cliques: Implementation and Evaluation Scripts. GitHub, Available online: https:\/\/github.com\/kit-algo\/LCD-cliques-experiments.","DOI":"10.3390\/a10030090"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Huang, J., Sun, H., Liu, Y., Song, Q., and Weninger, T. (2011). Towards Online Multiresolution Community Detection in Large-Scale Networks. PLoS ONE, 6.","DOI":"10.1371\/journal.pone.0023829"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"026132","DOI":"10.1103\/PhysRevE.72.026132","article-title":"Finding local community structure in networks","volume":"72","author":"Clauset","year":"2005","journal-title":"Phys. Rev. E"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chen, J., Za\u00efane, O.R., and Goebel, R. (2009, January 20\u201322). Local Community Identification in Social Networks. Proceedings of the 2009 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Athens, Greece.","DOI":"10.1109\/ASONAM.2009.14"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"P05001","DOI":"10.1088\/1742-5468\/2008\/05\/P05001","article-title":"Evaluating local community methods in networks","volume":"2008","author":"Bagrow","year":"2008","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fagnan, J., Zaiane, O., and Barbosa, D. (2014, January 17\u201320). Using triads to identify local community structure in social networks. Proceedings of the 2014 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Beijing, China.","DOI":"10.1109\/ASONAM.2014.6921568"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1240004","DOI":"10.1142\/S012962641240004X","article-title":"Local Community Identification in Social Networks","volume":"22","author":"Ngonmang","year":"2012","journal-title":"Parallel Process. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s10844-014-0315-6","article-title":"Toward seed-insensitive solutions to local community detection","volume":"43","author":"Ma","year":"2014","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., and Lang, K. (2006, January 21\u201324). Local Graph Partitioning using PageRank Vectors. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2006.44"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Panagiotakis, C., Papadakis, H., and Fragopoulou, P. (2015, January 25\u201328). Local Community Detection via Flow Propagation. Proceedings of the 2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France.","DOI":"10.1145\/2808797.2808892"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Li, Y., He, K., Bindel, D., and Hopcroft, J.E. (2015, January 18\u201322). Uncovering the small community structure in large networks: A local spectral approach. Proceedings of the 24th International Conference on World Wide Web, Florence, Italy.","DOI":"10.1145\/2736277.2741676"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1504\/IJWBC.2013.054906","article-title":"Towards multi-ego-centred communities: A node similarity approach","volume":"9","author":"Danisch","year":"2013","journal-title":"Int. J. Web Based Communities"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1049\/iet-syb.2013.0039","article-title":"Anti-triangle centrality-based community detection in complex networks","volume":"8","author":"Jia","year":"2014","journal-title":"Syst. Biol. IET"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Easley, D., and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press.","DOI":"10.1017\/CBO9780511761942"},{"key":"ref_29","first-page":"387","article-title":"Exploring local community structures in large networks","volume":"6","author":"Luo","year":"2008","journal-title":"Web Intell. Agent Syst. An Int. J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","article-title":"Defining and evaluating network communities based on ground-truth","volume":"42","author":"Yang","year":"2015","journal-title":"Knowl. Inf. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2011.12.006","article-title":"Arboricity, h-index, and dynamic algorithms","volume":"426","author":"Lin","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., and Strash, D. (2013). Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM J. Exp. Algorithm., 18.","DOI":"10.1145\/2543629"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., and Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. International Symposium on Algorithms and Computation, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Traud, A.L., Mucha, P.J., and Porter, M.A. (2011). Social Structure of Facebook Networks. arXiv.","DOI":"10.2139\/ssrn.1470768"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1140\/epjst\/e2010-01179-1","article-title":"The map equation","volume":"178","author":"Rosvall","year":"2009","journal-title":"Eur. Phys. J. Spec. Top."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2594454","article-title":"Structure and overlaps of ground-truth communities in networks","volume":"5","author":"Yang","year":"2014","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_37","unstructured":"Lee, C., and Cunningham, P. (1302). Benchmarking community detection methods on social media data. arXiv."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zakrzewska, A., and Bader, D.A. (2015, January 25\u201328). A Dynamic Algorithm for Local Community Detection in Graphs. Proceedings of the 2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France.","DOI":"10.1145\/2808797.2809375"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/978-3-642-03367-4_25","article-title":"The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics","volume":"Volume 5664","author":"Dehne","year":"2009","journal-title":"Proceedings of the WADS\u201909 11th International Symposium on Algorithms and Data Structures"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/90\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:42:10Z","timestamp":1760208130000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,11]]},"references-count":39,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9]]}},"alternative-id":["a10030090"],"URL":"https:\/\/doi.org\/10.3390\/a10030090","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,8,11]]}}}