A greedy algorithm for neighborhood overlap-based community detection
type: Item
instance of: scholarly article
title: A greedy algorithm for neighborhood overlap-based community detection
zbMATH Open document ID: 1461.05217
author: Natarajan Meghanathan
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 91D30
zbMATH DE Number: 7042317
zbMATH Keywords: community detection
zbMATH Keywords: edge betweenness
zbMATH Keywords: modularity score
zbMATH Keywords: neighborhood overlap
zbMATH Keywords: real-world network
describes a project that uses: GraphBase
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a9010008
OpenAlex ID: W2235644762
cites work: On Finding Graph Clusterings with Maximum Modularity
cites work: Community structure in social and biological networks
cites work: Fast unfolding of communities in large networks
cites work: Q4931752
cites work: Complex Networks
cites work: Q3140399
cites work: Q3043792
cites work: Q5403484
cites work: Emergence of Scaling in Random Networks
DOI: 10.3390/A9010008
description: scientific article; zbMATH DE number 7042317