Standard

Game-Theoretic Centrality Measures for Weighted Graphs. / Mazalov, V. V.; Avrachenkov, K. E.; Trukhina, L. I.; Tsynguev, B. T.

In: Fundamenta Informaticae, Vol. 145, No. 3, 2016, p. 341-358.

Research output: Contribution to journal › Article › peer-review

Harvard

Mazalov, VV, Avrachenkov, KE, Trukhina, LI & Tsynguev, BT 2016, 'Game-Theoretic Centrality Measures for Weighted Graphs', Fundamenta Informaticae, vol. 145, no. 3, pp. 341-358. https://doi.org/10.3233/FI-2016-1364, https://doi.org/10.3233/fi-2016-1364

APA

Mazalov, V. V., Avrachenkov, K. E., Trukhina, L. I., & Tsynguev, B. T. (2016). Game-Theoretic Centrality Measures for Weighted Graphs. Fundamenta Informaticae, 145(3), 341-358. https://doi.org/10.3233/FI-2016-1364, https://doi.org/10.3233/fi-2016-1364

Vancouver

Mazalov VV, Avrachenkov KE, Trukhina LI, Tsynguev BT. Game-Theoretic Centrality Measures for Weighted Graphs. Fundamenta Informaticae. 2016;145(3):341-358. https://doi.org/10.3233/FI-2016-1364, https://doi.org/10.3233/fi-2016-1364

Author

Mazalov, V. V. ; Avrachenkov, K. E. ; Trukhina, L. I. ; Tsynguev, B. T. / Game-Theoretic Centrality Measures for Weighted Graphs. In: Fundamenta Informaticae. 2016 ; Vol. 145, No. 3. pp. 341-358.

BibTeX

@article{a3879631b2354c9b83da95a92f0c9f79,
title = "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.",
author = "Mazalov, {V. V.} and Avrachenkov, {K. E.} and Trukhina, {L. I.} and Tsynguev, {B. T.}",
note = "doi: 10.3233/FI-2016-1364",
year = "2016",
doi = "10.3233/FI-2016-1364",
language = "English",
volume = "145",
pages = "341--358",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "3",

}

RIS

TY - JOUR

T1 - Game-Theoretic Centrality Measures for Weighted Graphs

AU - Mazalov, V. V.

AU - Avrachenkov, K. E.

AU - Trukhina, L. I.

AU - Tsynguev, B. T.

N1 - doi: 10.3233/FI-2016-1364

PY - 2016

Y1 - 2016

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

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

U2 - 10.3233/FI-2016-1364

DO - 10.3233/FI-2016-1364

M3 - Article

VL - 145

SP - 341

EP - 358

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 3

ER -

ID: 132705751