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

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Daniel Gómez, Javier Castro, Inmaculada Gutiérrez, Rosa Espínola
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	game theory graph theory hierarchical clustering networks community detection problems divisive algorithms Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/fd0e65f934ed4ea6b21152a459e216aa
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:fd0e65f934ed4ea6b21152a459e216aa
record_format	dspace
spelling	oai:doaj.org-article:fd0e65f934ed4ea6b21152a459e216aa2021-11-11T18:14:24ZA New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection10.3390/math92126662227-7390https://doaj.org/article/fd0e65f934ed4ea6b21152a459e216aa2021-10-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/21/2666https://doaj.org/toc/2227-7390In this paper we formally define the <i>hierarchical clustering network problem</i> (HCNP) as the problem to find a <i>good</i> hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final <i>picture</i> 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 <i>the linear modularity game.</i> This new measure, (<i>the node-game shortest path betweenness measure</i>), 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 <i>the node-game shortest path betweenness measure</i>, 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.Daniel GómezJavier CastroInmaculada GutiérrezRosa EspínolaMDPI AGarticlegame theorygraph theoryhierarchical clustering networkscommunity detection problemsdivisive algorithmsMathematicsQA1-939ENMathematics, Vol 9, Iss 2666, p 2666 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	game theory graph theory hierarchical clustering networks community detection problems divisive algorithms Mathematics QA1-939
spellingShingle	game theory graph theory hierarchical clustering networks community detection problems divisive algorithms Mathematics QA1-939 Daniel Gómez Javier Castro Inmaculada Gutiérrez Rosa Espínola A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
description	In this paper we formally define the <i>hierarchical clustering network problem</i> (HCNP) as the problem to find a <i>good</i> hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final <i>picture</i> 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 <i>the linear modularity game.</i> This new measure, (<i>the node-game shortest path betweenness measure</i>), 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 <i>the node-game shortest path betweenness measure</i>, 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.
format	article
author	Daniel Gómez Javier Castro Inmaculada Gutiérrez Rosa Espínola
author_facet	Daniel Gómez Javier Castro Inmaculada Gutiérrez Rosa Espínola
author_sort	Daniel Gómez
title	A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
title_short	A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
title_full	A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
title_fullStr	A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
title_full_unstemmed	A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection
title_sort	new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/fd0e65f934ed4ea6b21152a459e216aa
work_keys_str_mv	AT danielgomez anewedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT javiercastro anewedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT inmaculadagutierrez anewedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT rosaespinola anewedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT danielgomez newedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT javiercastro newedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT inmaculadagutierrez newedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection AT rosaespinola newedgebetweennessmeasureusingagametheoreticalapproachanapplicationtohierarchicalcommunitydetection
_version_	1718431920947200000

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

Ejemplares similares