{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T02:53:15Z","timestamp":1776394395574,"version":"3.51.2"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T00:00:00Z","timestamp":1479168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of Nebraska at Omaha, USA"},{"name":"Google India"},{"name":"UNO Graduate Research and Creative Activity"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,5,31]]},"abstract":"<jats:p>\n            The goal of community detection algorithms is to identify densely connected units within large networks. An implicit assumption is that all the constituent nodes belong equally to their associated community. However, some nodes are more important in the community than others. To date, efforts have been primarily made to identify communities as a whole, rather than understanding to what extent an individual node belongs to its community. Therefore, most metrics for evaluating communities, for example modularity, are global. These metrics produce a score for each community, not for each individual node. In this article, we argue that the belongingness of nodes in a community is not uniform. We quantify the degree of belongingness of a vertex within a community by a new vertex-based metric called\n            <jats:italic>permanence<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon two factors (i) the extent of connections of the vertex within its community versus outside its community, and (ii) how tightly the vertex is connected internally. We present the formulation of permanence based on these two quantities. We demonstrate that compared to other existing metrics (such as modularity, conductance, and cut-ratio), the change in permanence is more commensurate to the level of perturbation in ground-truth communities. We discuss how permanence can help us understand and utilize the structure and evolution of communities by demonstrating that it can be used to -- (i) measure the persistence of a vertex in a community, (ii) design strategies to strengthen the community structure, (iii) explore the core-periphery structure within a community, and (iv) select suitable initiators for message spreading.<\/jats:p>\n          <jats:p>\n            We further show that permanence is an excellent metric for identifying communities. We demonstrate that the process of maximizing permanence (abbreviated as\n            <jats:italic>MaxPerm<\/jats:italic>\n            ) produces meaningful communities that concur with the ground-truth community structure of the networks more accurately than eight other popular community detection algorithms. Finally, we provide mathematical proofs to demonstrate the correctness of finding communities by maximizing permanence. In particular, we show that the communities obtained by this method are (i) less affected by the changes in vertex ordering, and (ii) more resilient to resolution limit, degeneracy of solutions, and asymptotic growth of values.\n          <\/jats:p>","DOI":"10.1145\/2953883","type":"journal-article","created":{"date-parts":[[2016,11,15]],"date-time":"2016-11-15T13:35:02Z","timestamp":1479216902000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Permanence and Community Structure in Complex Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Tanmoy","family":"Chakraborty","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Kharagpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sriram","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Nebraska at Omaha, Omaha, NE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niloy","family":"Ganguly","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kharagpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Animesh","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kharagpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjukta","family":"Bhowmick","sequence":"additional","affiliation":[{"name":"University of Nebraska at Omaha, Omaha, NE"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,11,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Link communities reveal multiscale complexity in networks. Nature 466, (August","author":"Ahn Yong-Yeol","year":"2010","unstructured":"Yong-Yeol Ahn , James P. Bagrow , and Sune Lehmann . 2010. Link communities reveal multiscale complexity in networks. Nature 466, (August 2010 ), 761--764. Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. 2010. Link communities reveal multiscale complexity in networks. Nature 466, (August 2010), 761--764."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/10\/5\/053039"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/588"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427995_3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492536"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2015\/05\/P05017"},{"key":"e_1_2_1_9_1","volume-title":"Metrics for community analysis: A survey. CoRR abs\/1604.03512","author":"Chakraborty Tanmoy","year":"2016","unstructured":"Tanmoy Chakraborty , Ayushi Dalmia , Animesh Mukherjee , and Niloy Ganguly . 2016a. Metrics for community analysis: A survey. CoRR abs\/1604.03512 ( 2016 ). Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2016a. Metrics for community analysis: A survey. CoRR abs\/1604.03512 (2016)."},{"key":"e_1_2_1_10_1","volume-title":"GenPerm: A unified method for detecting non-overlapping and overlapping communities. CoRR abs\/1604.03454","author":"Chakraborty Tanmoy","year":"2016","unstructured":"Tanmoy Chakraborty , Suhansanu Kumar , Niloy Ganguly , Animesh Mukherjee , and Sanjukta Bhowmick . 2016b. GenPerm: A unified method for detecting non-overlapping and overlapping communities. CoRR abs\/1604.03454 ( 2016 ). Tanmoy Chakraborty, Suhansanu Kumar, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick. 2016b. GenPerm: A unified method for detecting non-overlapping and overlapping communities. CoRR abs\/1604.03454 (2016)."},{"key":"e_1_2_1_11_1","volume-title":"Constant communities in complex networks. Scientific Reports 3, (May","author":"Chakraborty Tanmoy","year":"2013","unstructured":"Tanmoy Chakraborty , Sriram Srinivasan , Niloy Ganguly , Sanjukta Bhowmick , and Animesh Mukherjee . 2013. Constant communities in complex networks. Scientific Reports 3, (May 2013 ). DOI:10.1038\/srep01825 10.1038\/srep01825 Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Sanjukta Bhowmick, and Animesh Mukherjee. 2013. Constant communities in complex networks. Scientific Reports 3, (May 2013). DOI:10.1038\/srep01825"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623707"},{"key":"e_1_2_1_13_1","first-page":"226","article-title":"A new metric for quality of network community structure","volume":"1","author":"Chen Mingming","year":"2013","unstructured":"Mingming Chen , Tommy Nguyen , and Boleslaw Szymanski . 2013 . A new metric for quality of network community structure . ASE Human Journal 1 , 4 (2013), 226 -- 240 . Mingming Chen, Tommy Nguyen, and Boleslaw Szymanski. 2013. A new metric for quality of network community structure. ASE Human Journal 1, 4 (2013), 226--240.","journal-title":"ASE Human Journal"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873736"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"L. Danon A. Diaz-Guilera J. Duch and A. Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 9 (2005) P09008.  L. Danon A. Diaz-Guilera J. Duch and A. Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 9 (2005) P09008.","DOI":"10.1088\/1742-5468\/2005\/09\/P09008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2012.08.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0903215107"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016105"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/180"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5506\/APhysPolBSupp.4.123"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.046106"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03288"},{"key":"e_1_2_1_28_1","volume-title":"Discovering link communities in complex networks by exploiting link dynamics. CoRR abs\/1303.4699","author":"He Dongxiao","year":"2013","unstructured":"Dongxiao He , Dayou Liu , Weixiong Zhang , Di Jin , and Bo Yang . 2013. Discovering link communities in complex networks by exploiting link dynamics. CoRR abs\/1303.4699 ( 2013 ). Dongxiao He, Dayou Liu, Weixiong Zhang, Di Jin, and Bo Yang. 2013. Discovering link communities in complex networks by exploiting link dynamics. CoRR abs\/1303.4699 (2013)."},{"key":"e_1_2_1_29_1","first-page":"107","article-title":"Transitivity in structural models of small groups","volume":"2","author":"Holland Paul W.","year":"1971","unstructured":"Paul W. Holland and Samuel Leinhardt . 1971 . Transitivity in structural models of small groups . Small Group Research 2 , 2 (1971), 107 -- 124 . Paul W. Holland and Samuel Leinhardt. 1971. Transitivity in structural models of small groups. Small Group Research 2, 2 (1971), 107--124.","journal-title":"Small Group Research"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796585"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt\u201910)","author":"Lambiotte Renaud","year":"2010","unstructured":"Renaud Lambiotte . 2010 . Multi-scale modularity in complex networks . In Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt\u201910) . IEEE, 546--553. Renaud Lambiotte. 2010. Multi-scale modularity in complex networks. In Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt\u201910). IEEE, 546--553."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066122"},{"key":"e_1_2_1_36_1","volume-title":"Consensus clustering in complex networks. Scientific Reports 2","author":"Lancichinetti Andrea","year":"2012","unstructured":"Andrea Lancichinetti and Santo Fortunato . 2012. Consensus clustering in complex networks. Scientific Reports 2 ( 2012 ). DOI:10.1038\/srep00336 10.1038\/srep00336 Andrea Lancichinetti and Santo Fortunato. 2012. Consensus clustering in complex networks. Scientific Reports 2 (2012). DOI:10.1038\/srep00336"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/11\/3\/033015"},{"key":"e_1_2_1_38_1","volume-title":"Finding statistically significant communities in networks. CoRR abs\/1012.2363","author":"Lancichinetti Andrea","year":"2010","unstructured":"Andrea Lancichinetti , Filippo Radicchi , Jose J. Ramasco , and Santo Fortunato . 2010. Finding statistically significant communities in networks. CoRR abs\/1012.2363 ( 2010 ). Andrea Lancichinetti, Filippo Radicchi, Jose J. Ramasco, and Santo Fortunato. 2010. Finding statistically significant communities in networks. CoRR abs\/1012.2363 (2010)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.118703"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_1_42_1","volume-title":"Introduction to Information Retrieval","author":"Manning Christopher D.","unstructured":"Christopher D. Manning , Prabhakar Raghavan , and Hinrich Sch\u00fctze . 2008. Introduction to Information Retrieval . Cambridge University Press , New York, NY . Christopher D. Manning, Prabhakar Raghavan, and Hinrich Sch\u00fctze. 2008. Introduction to Information Retrieval. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.026126"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.056131"},{"key":"e_1_2_1_46_1","first-page":"6","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman . 2004 b. Fast algorithm for detecting community structure in networks . Physical Review E 69 , 6 (June 2004), 066133. M. E. J. Newman. 2004b. Fast algorithm for detecting community structure in networks. Physical Review E 69, 6 (June 2004), 066133.","journal-title":"Physical Review E"},{"key":"e_1_2_1_47_1","volume-title":"Community detection and graph partitioning. CoRR abs\/1305.4974","author":"Newman M. E. J.","year":"2013","unstructured":"M. E. J. Newman . 2013. Community detection and graph partitioning. CoRR abs\/1305.4974 ( 2013 ). M. E. J. Newman. 2013. Community detection and graph partitioning. CoRR abs\/1305.4974 (2013)."},{"key":"e_1_2_1_48_1","volume-title":"Physical Review E 69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman and M. Girvan . 2004. Finding and evaluating community structure in networks . Physical Review E 69 , ( 2004 ) 026113. M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Physical Review E 69, (2004) 026113."},{"key":"e_1_2_1_49_1","volume-title":"Comparative evaluation of community detection algorithms: A topological approach. CoRR abs\/1206.4987","author":"Orman G\u00fcnce Keziban","year":"2012","unstructured":"G\u00fcnce Keziban Orman , Vincent Labatut , and Hocine Cherifi . 2012. Comparative evaluation of community detection algorithms: A topological approach. CoRR abs\/1206.4987 ( 2012 ). G\u00fcnce Keziban Orman, Vincent Labatut, and Hocine Cherifi. 2012. Comparative evaluation of community detection algorithms: A topological approach. CoRR abs\/1206.4987 (2012)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00124"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.066114"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.016110"},{"key":"e_1_2_1_55_1","volume-title":"Porter","author":"Richardson Thomas","year":"2009","unstructured":"Thomas Richardson , Peter J. Mucha , and Mason A . Porter . 2009 . Spectral tripartitioning of networks. Physical Review E 40, (2009), 027104. Thomas Richardson, Peter J. Mucha, and Mason A. Porter. 2009. Spectral tripartitioning of networks. Physical Review E 40, (2009), 027104."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0611034104"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_2_1_59_1","volume-title":"Studies in Computational Intelligence","author":"Seifi Massoud","unstructured":"Massoud Seifi , Ivan Junier , Jean-Baptiste Rouquier , Svilen Iskrov , and Jean-Loup Guillaume . 2013. Stable community cores in complex networks . In Complex Networks, Ronaldo Menezes, Alexandre Evsukoff, and Marta C. Gonzlez (Eds.), Studies in Computational Intelligence , vol. 424 . Springer , Berlin , 87--98. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-30287-9_10 10.1007\/978-3-642-30287-9_10 Massoud Seifi, Ivan Junier, Jean-Baptiste Rouquier, Svilen Iskrov, and Jean-Loup Guillaume. 2013. Stable community cores in complex networks. In Complex Networks, Ronaldo Menezes, Alexandre Evsukoff, and Marta C. Gonzlez (Eds.), Studies in Computational Intelligence, vol. 424. Springer, Berlin, 87--98. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-30287-9_10"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.11.022"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/NSW.2011.6004645"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30220-6_3"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2014.2364018"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2953883","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2953883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:22Z","timestamp":1750222582000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2953883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,15]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,5,31]]}},"alternative-id":["10.1145\/2953883"],"URL":"https:\/\/doi.org\/10.1145\/2953883","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,15]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}