ConvGraph: Community Detection of Homogeneous Relationships in Weighted Graphs

Héctor Muñoz, Eloy Vicente, Ignacio González, Alfonso Mateos and Antonio Jiménez-Martín
Additional contact information
Héctor Muñoz: Decision Analysis and Statistics Group, Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, 28040 Madrid, Spain
Eloy Vicente: Decision Analysis and Statistics Group, Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, 28040 Madrid, Spain
Ignacio González: Decision Analysis and Statistics Group, Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, 28040 Madrid, Spain
Alfonso Mateos: Decision Analysis and Statistics Group, Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, 28040 Madrid, Spain
Antonio Jiménez-Martín: Decision Analysis and Statistics Group, Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, 28040 Madrid, Spain

Mathematics, 2021, vol. 9, issue 4, 1-18

Abstract: This paper proposes a new method, ConvGraph, to detect communities in highly cohesive and isolated weighted graphs, where the sum of the weights is significantly higher inside than outside the communities. The method starts by transforming the original graph into a line graph to apply a convolution, a common technique in the computer vision field. Although this technique was originally conceived to detect the optimum edge in images, it is used here to detect the optimum edges in communities identified by their weights rather than by their topology. The method includes a final refinement step applied to communities with a high vertex density that could not be detected in the first phase. The proposed algorithm was tested on a series of highly cohesive and isolated synthetic graphs and on a real-world export graph, performing well in both cases.

Keywords: community detection; convolution; line graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/367/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/367/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:367-:d:498287

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().