A greedy algorithm for neighborhood overlap-based community detection (Q1736758): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: GraphBase / rank | |||
Normal rank |
Revision as of 18:15, 28 February 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