A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection

Daniel Gómez, Javier Castro, Inmaculada Gutiérrez and Rosa Espínola
Additional contact information
Daniel Gómez: Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
Javier Castro: Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
Inmaculada Gutiérrez: Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
Rosa Espínola: Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain

Mathematics, 2021, vol. 9, issue 21, 1-29

Abstract: In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new hierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by the importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, ( the node-game shortest path betweenness measure ), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure , whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.

Keywords: game theory; graph theory; hierarchical clustering networks; community detection problems; divisive algorithms (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: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/21/2666/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/21/2666/ (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:21:p:2666-:d:661694

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 ().