{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T05:30:18Z","timestamp":1790055018733,"version":"4.0.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1216028"],"award-info":[{"award-number":["1216028"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>Community discovery in complex networks is the task of organizing a network\u2019s structure by grouping together nodes related to each other. Traditional approaches are based on the assumption that there is a global-level organization in the network. However, in many scenarios, each node is the bearer of complex information and cannot be classified in disjoint clusters. The top-down global view of the partition approach is not designed for this. Here, we represent this complex information as multiple latent labels, and we postulate that edges in the networks are created among nodes carrying similar labels. The latent labels are the communities a node belongs to and we discover them with a simple local-first approach to community discovery. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, its ego neighborhood, using a label propagation algorithm, assuming that each node is aware of the label it shares with each of its connections. The local communities are merged hierarchically, unveiling the modular organization of the network at the global level and identifying overlapping groups and groups of groups. We tested this intuition against the state-of-the-art overlapping community discovery and found that our new method advances in the chosen scenarios in the quality of the obtained communities. We perform a test on benchmark and on real-world networks, evaluating the quality of the community coverage by using the extracted communities to predict the metadata attached to the nodes, which we consider external information about the latent labels. We also provide an explanation about why real-world networks contain overlapping communities and how our logic is able to capture them. Finally, we show how our method is deterministic, is incremental, and has a limited time complexity, so that it can be used on real-world scale networks.<\/jats:p>","DOI":"10.1145\/2629511","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T12:08:55Z","timestamp":1409054935000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Uncovering Hierarchical and Overlapping Communities with a Local-First Approach"],"prefix":"10.1145","volume":"9","author":[{"given":"Michele","family":"Coscia","sequence":"first","affiliation":[{"name":"CID - Harvard Kennedy School, Cambridge, MA, US"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giulio","family":"Rossetti","sequence":"additional","affiliation":[{"name":"KDDLab, ISTI-CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fosca","family":"Giannotti","sequence":"additional","affiliation":[{"name":"KDDLab, ISTI-CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dino","family":"Pedreschi","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Pisa, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.046108"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2011.104"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-012-0190-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033432"},{"key":"#cr-split#-e_1_2_1_6_1.1","doi-asserted-by":"crossref","unstructured":"Vincent D. Blondel Jean-Loup Guillaume Renaud Lambiotte and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics (2008) P10008. DOI: 10.1088\/1742-5468\/2008\/10\/P10008 10.1088\/1742-5468","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"#cr-split#-e_1_2_1_6_1.2","doi-asserted-by":"crossref","unstructured":"Vincent D. Blondel Jean-Loup Guillaume Renaud Lambiotte and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics (2008) P10008. DOI: 10.1088\/1742-5468\/2008\/10\/P10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.10133"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339630"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI&rsquo;\u201904)","author":"Dean Jeffrey","year":"2004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.160202"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016105"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"S. Fortunato. 2010. Community detection in graphs. Physics Reports 486 (Feb. 2010) 75--174. DOI: http:\/\/dx.doi.org\/10.1016\/j.physrep.2009.11.002  S. Fortunato. 2010. Community detection in graphs. Physics Reports 486 (Feb. 2010) 75--174. DOI: http:\/\/dx.doi.org\/10.1016\/j.physrep.2009.11.002","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24775-3_5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.59"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.66"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201911)","author":"Kumar Abhishek","year":"2011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972788.74"},{"key":"e_1_2_1_28_1","unstructured":"Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In NIPS Peter L. Bartlett Fernando C. N. Pereira Christopher J. C. Burges L\u00e9on Bottou and Kilian Q. Weinberger (Eds.). 548--556. Available at http:\/\/dblp.uni-trier.de\/db\/conf\/nips\/nips2012.html&num; McAuleyL12.  Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In NIPS Peter L. Bartlett Fernando C. N. Pereira Christopher J. C. Burges L\u00e9on Bottou and Kilian Q. Weinberger (Eds.). 548--556. Available at http:\/\/dblp.uni-trier.de\/db\/conf\/nips\/nips2012.html&num; McAuleyL12."},{"key":"e_1_2_1_29_1","unstructured":"Aaron F. McDaid Derek Greene and Neil Hurley. 2011. Normalized mutual information to evaluate overlapping community finding algorithms. ArXiv. (Oct. 2011). http:\/\/arxiv.org\/abs\/1110.2515  Aaron F. McDaid Derek Greene and Neil Hurley. 2011. Normalized mutual information to evaluate overlapping community finding algorithms. ArXiv. (Oct. 2011). http:\/\/arxiv.org\/abs\/1110.2515"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Peter J. Mucha Thomas Richardson Kevin Macon Mason A. Porter and J.-P. Onnela. 2010. Community structure in time-dependent multiscale and multiplex networks. Science 328 5980 (2010) 876--878. http:\/\/dx.doi.org\/10.1126\/science.1184819  Peter J. Mucha Thomas Richardson Kevin Macon Mason A. Porter and J.-P. Onnela. 2010. Community structure in time-dependent multiscale and multiplex networks. Science 328 5980 (2010) 876--878. http:\/\/dx.doi.org\/10.1126\/science.1184819","DOI":"10.1126\/science.1184819"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121525.3121538"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00124"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.72"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4018\/jdwm.2007070101"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963508"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30220-6_3"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2011.154"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273642"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2629511"],"URL":"https:\/\/doi.org\/10.1145\/2629511","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}