Game-Theoretic Centrality Measures for Weighted Graphs

• Autorzy: Mazalov V. V. , Trukhina L. I. , Avrachenkov K. E. , Tsynguev B. T.

Identyfikatory

DOI

10.3233/FI-2016-1364

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

betweenness centrality; cooperative game; social networks; weighted graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 341--358
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Mazalov V. V.

• Institute of Applied Mathematical Research of the Karelian Research Center RAS, Petrozavodsk, Russia

autor

Trukhina L. I.

• Chita Institute Baikal State, University of Economics and Law Chita, Russia

autor

Avrachenkov K. E.

• Inria Sophia Antipolis, France

autor

Tsynguev B. T.

• Transbaikal State University, Chita, Russia

Bibliografia

• [1] Freeman LC. A set of measures of centrality based on betweenness. Sociometry. 1977; 40:35–41.
• [2] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 2001; 25:163–177. doi: 10.1080/0022250X.2001.9990249.
• [3] Myerson RB. Graphs and cooperation in games. Math. Oper. Res. 2, 1977, 225–229.
• [4] Jackson MO. Wolinsky, J. A strategic model of social and economic networks. J. Econ. Theory. 1996; 71(1):44–74.
• [5] Borm P, Owen G, Tijs S. On the position value for communication situations. SIAM J. on Discrete Math. 1992; 5(3):305–320. doi: 10.1137/0405023.
• [6] Borm P, van den Nouweland A, Tijs S. Cooperation and communication restrictions: a survey. In: Imperfections and Behavior in Economic Organizations, Kluwer Acad. Publ., Boston; 1994.
• [7] Calvo E, Lasaga J, van den Nouweland A. Values of games with probabilistic graphs. Math. Social Sci. 1999; 37:79-95. doi:10.1016/S0165-4896(98)00013-4.
• [8] Jackson MO. Allocation rules for network games. Games and Econ. Behav. 2005; 51(1):128–154.
• [9] Slikker M. Link monotonic allocation schemes. Int. Game Theory Review. 2005; 7(4):473–489.
• [10] Slikker M, Gilles RP, Norde H, Tijs S. Directed networks, allocation properties and hierarchy formation. Math. Social Sci. 2005; 49(1):55–80. Available from: http://EconPapers.repec.org/RePEc:eee:matsoc:v:49:y:2005:i:1:p:55-80.
• [11] Talman D, Yamamoto Y. Average tree solutions and subcore for acyclic graph games. J. Oper. Res. Soc. Japan. 2008; 51(3):187–201.
• [12] Mazalov VV, Trukhina LI. Generating functions and the Myerson vector in communication networks. Discrete Mathematics and Applications. 2014; 24(5):295–303.
• [13] Brandes U, Fleischer D. Centrality measures based on current flow. In: Proceedings of the 22nd annual conference on Theoretical Aspects of Computer Science; 2005. p. 533–544. doi: 10.1007/978-3-540-31856-9 44.
• [14] Newman MEJ. A measure of betweenness centrality based on random walks. Social networks. 2005; 27:39–54. doi: 10.1016/j.socnet.2004.11.009.
• [15] Avrachenkov K, Litvak N, Medyanikov V, and Sokol M. Alpha current flow betweenness centrality. In: Proceedings of WAW 2013, (also LNCS v.8305); 2013. p. 106–117.
• [16] Jackson MO. Social and economic networks. Princeton University Press; 2008.
• [17] Jamison RE. Alternating Whitney sums and matchings in trees, part 1. Discrete Math. 1987; 67:177–189.
• [18] Opsahl T, Agneessens F, Skvoretz J. Node centrality in weighted networks: generalizing degree and shortest paths. Social Networks. 2010; 32:245–251. doi: 10.1016/j.socnet.2010.03.006.
• [19] Borgatti SP, Everett MG and Freeman LC. Ucinet for Windows: Software for Social Network Analysis. Harvard, MA: Analytic Technologies; 2002.
• [20] Aumann R, Myerson R. Endogenous formation of links between players and coalitions: an application of the Shapley value. In: The Shapley value, Cambridge University Press; 1988. p. 175-191.
• [21] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 2001; 25:163–177. doi: 10.1080/0022250X.2001.9990249.
• [22] Mazalov V. Mathematical Game Theory and Applications. Wiley; 2014. ISBN-13:978-1118899625, ISBN-10:1118899628.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).