A greedy algorithm for neighborhood overlap-based community detection (Q1736758): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.3390/a9010008 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2235644762 / rank | |||
Normal rank |
Latest revision as of 02:53, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A greedy algorithm for neighborhood overlap-based community detection |
scientific article |
Statements
A greedy algorithm for neighborhood overlap-based community detection (English)
0 references
26 March 2019
0 references
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.
0 references
community detection
0 references
edge betweenness
0 references
modularity score
0 references
neighborhood overlap
0 references
real-world network
0 references