Game-Theoretic Centrality Measures for Weighted Graphs

Abstract : The betweenness centrality is one of the basic concepts in the analysis of the social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of the shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). Two approaches are used to determine the characteristic function. In the first approach the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. In the second approach the coalition is considered as an electric network and the characteristic function is determined as a total current in this network. We use the Kirchhoff's law. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network "VKontakte", as well as the comparing with the PageRank method are presented.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2016, Discrete Mathematics (RuFiDiM 14), 145 (3), pp.341-358. 〈http://content.iospress.com/articles/fundamenta-informaticae/fi1364〉. 〈10.3233/FI-2016-1364〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402858
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 25 novembre 2016 - 11:38:04
Dernière modification le : samedi 27 janvier 2018 - 01:31:41
Document(s) archivé(s) le : mardi 21 mars 2017 - 03:17:10

Fichier

CentralityENG2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vladimir Mazalov, Konstantin Avrachenkov, Liudmila Trukhina, Bulat Tsynguev. Game-Theoretic Centrality Measures for Weighted Graphs. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2016, Discrete Mathematics (RuFiDiM 14), 145 (3), pp.341-358. 〈http://content.iospress.com/articles/fundamenta-informaticae/fi1364〉. 〈10.3233/FI-2016-1364〉. 〈hal-01402858〉

Partager

Métriques

Consultations de la notice

252

Téléchargements de fichiers

71