{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:17:27Z","timestamp":1760242647108,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T00:00:00Z","timestamp":1452470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The neighborhood overlap (NOVER) of an edge u-v is defined as the ratio of the number of nodes who are neighbors for both u and v to that of the number of nodes who are neighbors of at least u or v. In this paper, we hypothesize that an edge u-v with a lower NOVER score bridges two or more sets of vertices, with very few edges (other than u-v) connecting vertices from one set to another set. Accordingly, we propose a greedy algorithm of iteratively removing the edges of a network in the increasing order of their neighborhood overlap and calculating the modularity score of the resulting network component(s) after the removal of each edge. The network component(s) that have the largest cumulative modularity score are identified as the different communities of the network. We evaluate the performance of the proposed NOVER-based community detection algorithm on nine real-world network graphs and compare the performance against the multi-level aggregation-based Louvain algorithm, as well as the original and time-efficient versions of the edge betweenness-based Girvan-Newman (GN) community detection algorithm.<\/jats:p>","DOI":"10.3390\/a9010008","type":"journal-article","created":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T10:09:38Z","timestamp":1452506978000},"page":"8","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["A Greedy Algorithm for Neighborhood Overlap-Based Community Detection"],"prefix":"10.3390","volume":"9","author":[{"given":"Natarajan","family":"Meghanathan","sequence":"first","affiliation":[{"name":"Computer Science, Jackson State University, Jackson, MS 39217, USA"}]}],"member":"1968","published-online":{"date-parts":[[2016,1,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","first-page":"8557","article-title":"Modularity and Community Structure in Networks","volume":"103","author":"Newman","year":"2006","journal-title":"J. Natl. Acad. Sci. USA"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","article-title":"On Modularity Clustering","volume":"20","author":"Brandes","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community Structure in Social and Biological Networks","volume":"99","author":"Girvan","year":"2002","journal-title":"J. Natl. Acad. Sci. USA"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1140\/epjb\/e2004-00124-y","article-title":"Detecting Community Structure in Networks","volume":"38","author":"Newman","year":"2004","journal-title":"Eur. Phys. J. B Condens. Matter Complex Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution Limit in Community Detection","volume":"104","author":"Fortunato","year":"2007","journal-title":"J. Natl. Acad. Sci. USA"},{"key":"ref_7","first-page":"1","article-title":"Fast Unfolding of Communities in Large Networks","volume":"P10008","author":"Blondel","year":"2008","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/01972240590925348","article-title":"Email as Spectroscopy: Automated Discovery of Community Structure within Organizations","volume":"21","author":"Tyler","year":"2007","journal-title":"Inform. Soc. Int. J."},{"key":"ref_9","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":"J. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Luo, T., Zhong, C., Ying, X., and Fu, J. (2011, January 26\u201328). Detecting Community Structure based on Edge Betweenness. Proceedings of the 8th International Conference on Fuzzy Systems and Knowledge Discovery, Shanghai, China.","DOI":"10.1109\/FSKD.2011.6019678"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Easley, D., and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press. [1st ed.].","DOI":"10.1017\/CBO9780511761942"},{"key":"ref_12","unstructured":"Ana, L.N.F., and Jain, A.K. (2003, January 16\u201322). Robust Data Clustering. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Madison, WI, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/2629438","article-title":"On Facebook, Most Ties Are Weak","volume":"57","author":"Ferrara","year":"2014","journal-title":"Commun. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"066122","DOI":"10.1103\/PhysRevE.84.066122","article-title":"Limits of Modularity Maximization in Community Detection","volume":"84","author":"Lancichinetti","year":"2011","journal-title":"Phys. Rev. E"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Erciyes, K. (2014). Complex Networks: An Algorithmic Perspective, CRC Press. [1st ed.].","DOI":"10.1201\/b17409"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","article-title":"The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations","volume":"54","author":"Lusseau","year":"2003","journal-title":"Behav. Ecol. Sociobiol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An Information Flow Model for Conflict and Fission in Small Groups","volume":"33","author":"Zachary","year":"1977","journal-title":"J. Anthropol. Res."},{"key":"ref_18","first-page":"87","article-title":"Book Networks","volume":"4","author":"Krebs","year":"2000","journal-title":"Int. Assoc. Hum. Resour. Inform. Manag. J."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.physa.2014.06.067","article-title":"An Exploratory Analysis on the Evolution of the US AIrport Network","volume":"413","author":"Jia","year":"2014","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0378-8733(00)00023-X","article-title":"Some Analyses of Erdos Collaboration Graph","volume":"22","author":"Batagelj","year":"2000","journal-title":"Soc. Netw."},{"key":"ref_21","unstructured":"Knuth, D.E. (1993). The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley. [1st ed.]."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1023\/A:1009615807222","article-title":"A Neural Network Model of Caenorhabditis Elegans: The Circuit of Touch Sensitivity","volume":"6","author":"Cangelosi","year":"1997","journal-title":"Neural Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Biedl, T., and Brandenburg, F. (2001, January 23\u201326). Graph-Drawing Contest Report. Proceedings of the 9th International Symposium on Graph Drawing, Vienna, Austria.","DOI":"10.1007\/3-540-44541-2_39"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ross, S.M. (2014). Introduction to Probability Models, Academic Press. [11th ed.].","DOI":"10.1016\/B978-0-12-407948-9.00001-3"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Meghanathan, N. (2014, January 20\u201323). Spectral Radius as a Measure of Variation in Node Degree for Complex Network Graphs. Proceedings of the 7th International Conference on u- and e-Service, Science and Technology, Haikou, China.","DOI":"10.1109\/UNESST.2014.8"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of Scaling in Random Networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.1086\/225469","article-title":"The Strength of Weak Ties","volume":"78","author":"Granovetter","year":"1973","journal-title":"Am. J. Sociol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"7332","DOI":"10.1073\/pnas.0610245104","article-title":"Structure and Tie Strengths in Mobile Communication Networks","volume":"104","author":"Onnela","year":"2007","journal-title":"J. Natl. Acad. Sci. USA"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1788","DOI":"10.1016\/j.physa.2011.09.027","article-title":"Efficient Algorithm Based on Neighborhood Overlap for Community Identification in Complex Networks","volume":"391","author":"Li","year":"2012","journal-title":"Phys. A Stat. Mech. Appl."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/8\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:17:31Z","timestamp":1760210251000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,11]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,3]]}},"alternative-id":["a9010008"],"URL":"https:\/\/doi.org\/10.3390\/a9010008","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,1,11]]}}}