Geodesic
Game theoretic centrality of a directed graph vertices
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 3, pp. 64-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper considers a game theory approach to calculating the centrality value of the vertices in a directed graph, based on the number of vertex occurrences in fixed length paths. It is proposed to define vertex centrality as a solution of a cooperative game, where the characteristic function is given as the number of simple paths of fixed length in subgraphs corresponding to coalitions. The concept of integral centrality is introduced as the value of a definite integral of the payoff function. It is shown that this centrality measure satisfies the Boldi–Vigna axioms.
Keywords: graph theory, centrality, directed graph, cooperative game. 
@article{MGTA_2023_15_3_a3,
     author = {Vitalia A. Khitraya and Vladimir V. Mazalov},
     title = {Game theoretic centrality of a directed graph vertices},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {64--87},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a3/}
}
TY  - JOUR
AU  - Vitalia A. Khitraya
AU  - Vladimir V. Mazalov
TI  - Game theoretic centrality of a directed graph vertices
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2023
SP  - 64
EP  - 87
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a3/
LA  - ru
ID  - MGTA_2023_15_3_a3
ER  - 
%0 Journal Article
%A Vitalia A. Khitraya
%A Vladimir V. Mazalov
%T Game theoretic centrality of a directed graph vertices
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2023
%P 64-87
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a3/
%G ru
%F MGTA_2023_15_3_a3
Vitalia A. Khitraya; Vladimir V. Mazalov. Game theoretic centrality of a directed graph vertices. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 3, pp. 64-87. http://geodesic.mathdoc.fr/item/MGTA_2023_15_3_a3/

[1] Aleskerov F.T., Khabina E.L., Shvarts D.A., Binarnye otnosheniya, grafy i kollektivnye resheniya. Primery i zadachi, ucheb. posobie dlya vuzov, Iz-vo Yurait, M., 2023

[2] Mazalov V.V., Khitraya V.A., “Ranzhirovanie vershin grafa s ispolzovaniem absolyutnykh potentsialov uzlov elektricheskoi tsepi”, Vestnik Sankt-Peterburgskogo universiteta. Prikladnaya matematika. Informatika. Protsessy upravleniya, 19:2 (2023), 233–251 | MR

[3] Scherbakova N.G., “Aksiomatika tsentralnosti v kompleksnykh setyakh”, Problemy informatiki, 2015, no. 3, 3–14

[4] Avrachenkov K.E., Kondratev A.Y., Mazalov V.V. Rybanov D.G., “Network partitioning algorithms as cooperative games”, Computational Social Networks, 5:11 (2018)

[5] Bavelas A., “A mathematical model for group structures”, Human organization, 7:3 (1948), 16–30 | DOI

[6] Bavelas A., “Communication patterns in task-oriented groups”, The journal of the acoustical society of America, 22:6 (1950), 725–30 | DOI

[7] Beauchamp M.A., “An improved index of centrality”, Behavioral Science, 10:2 (1965), 161–163 | DOI

[8] Boldi P., Vigna S., “Axioms for Centrality”, Internet Mathematics, 10:3–4 (2014), 222–262 | DOI | MR | Zbl

[9] Ermolin N.A., Khitraya V.A., Khitryi A.V., Mazalov V.V. and Nikitina N.N., “Modeling of the City's Transport Network Using Game-Theoretic Methods on the Example of Petrozavodsk”, Contributions to Game Theory and Management, 15 (2022), 18–31 | DOI | MR

[10] Freeman L.C., “A set of measures of centrality based on betweenness”, Sociometry, 1 (1977), 35–41 | DOI

[11] Jackson M.O., Social and economic networks, Princeton University Press, 2008 | MR | Zbl

[12] Li Ju., Tur A., Zavrajnov M., “Importance of agents in networks: clique based game-theoretic approach”, Contributions to Game Theory and Management, 15 (2022), 189–199 | DOI | MR

[13] Mazalov V. Chirkova J., Networking Games, Academic Press, 2019 | Zbl

[14] Mazalov V.V., Khitraya V.A., “A modified Myerson value for determining the centrality of graph vertices”, Automation and Remote Control, 82:1 (2021), 145–159 | DOI | MR | Zbl

[15] Mazalov V.V., Trukhina L.I., “Generating functions and the myerson vector in communication networks”, Diskr. Mat., 26:3 (2014), 65–75 | DOI | MR | Zbl

[16] Michalak T.P., Aadithya K.V., Szczepanski P.L., Ravindran B., Jennings N.R., “Efficient computation of the Shapley value for game-theoretic network centrality”, J Artif. Intell. Res., 46 (2013), 607–650 | DOI | MR | Zbl

[17] Myerson R.B., “Graphs and cooperation in games”, Mathematics of Operations Research, 2:3 (1977), 225–229 | DOI | MR | Zbl

[18] Nieminen J., “On the centrality in a directed graph”, Social Science Research, 2:4 (1974), 371–378 | DOI

[19] Page L., Brin S., Motwani R., Winograd T., “The pagerank citation ranking: Bringing order to the Web”, Proceedings of the 7$^{\mathrm{th}}$ International World Wide Web Conference (Brisbane, Australia, 1998), 161–172 | MR

[20] Rochat Y., “Closeness centrality extended to unconnected graphs: The harmonic centrality index”, Proc. of the Applications of Social Network Analysis, ASNA 2009

[21] Sabidussi G., “The centrality index of a graph”, Psychometrika, 31 (1966), 581–603 | DOI | MR | Zbl

[22] Shaw M., “Communication networks”, Advances in Experimental Social Psychology, v. 1, 1954, 111–147

[23] Euler-Mascheroni Constant, Wolfram MathWorld, , 2023 https://mathworld.wolfram.com/Euler-MascheroniConstant.html