Geodesic
Modified Mayerson value for determining the centrality of graph vertices
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 2, pp. 19-39.

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

To analyze the structure of social networks, we can use methods of cooperative game theory. One of such methods is based on the calculation of the Myerson values as a measure of the centrality of the vertices in the graph. In this case, the number of paths of a certain length in the subgraphs corresponding to the coalitions is used as the characteristic function. The paper proposes a modification of the Myerson value for the case when the paths in the graph containing cycles are included in the consideration. The effectiveness of this approach is shown on a number of examples.
Keywords: networks, paths with cycles, centrality measure, cooperative game, Myerson value. 
@article{MGTA_2019_11_2_a1,
     author = {Vladimir V. Mazalov and Vitaliya A. Khitraya},
     title = {Modified {Mayerson} value for determining the centrality of graph vertices},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {19--39},
     publisher = {mathdoc},
     volume = {11},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a1/}
}
TY  - JOUR
AU  - Vladimir V. Mazalov
AU  - Vitaliya A. Khitraya
TI  - Modified Mayerson value for determining the centrality of graph vertices
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2019
SP  - 19
EP  - 39
VL  - 11
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a1/
LA  - ru
ID  - MGTA_2019_11_2_a1
ER  - 
%0 Journal Article
%A Vladimir V. Mazalov
%A Vitaliya A. Khitraya
%T Modified Mayerson value for determining the centrality of graph vertices
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2019
%P 19-39
%V 11
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a1/
%G ru
%F MGTA_2019_11_2_a1
Vladimir V. Mazalov; Vitaliya A. Khitraya. Modified Mayerson value for determining the centrality of graph vertices. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 2, pp. 19-39. http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a1/

[1] Aumann R., Myerson R., “Endogenous formation of links between players and coalitions: an application of the Shapley value”, The Shapley value, Cambridge University Press, 1988, 175–191 | DOI | MR

[2] Avrachenkov K., Kondratev A. Yu., Mazalov V. V., Rubanov D. G., “Network partitioning as cooperative games”, Computational social networks, 5:11 (2018), 1–28

[3] Avrachenkov K. E., Mazalov V. V., Tsynguev B. T., “Beta Current Flow Centrality for Weighted Networks”, Proceedings of CSoNET, LNCS, 9197, 2015, 216–227

[4] Brandes U., Fleischer D., “Centrality measures based on current flow”, Proceedings of the 22nd annual conference on Theoretical Aspects of Computer Science, 2005, 533–544 | MR | Zbl

[5] Brin S., Page L., “The anatomy of a large-scale hypertextual Web search engine”, Computer Networks and ISDN Systems, 30:17 (1998), 107–117 | DOI

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

[7] Mazalov V., Chirkova J., Networking games, Academic Press, 2019 | Zbl

[8] Mazalov V. V., Trukhina L. I., “Generating functions and the Myerson vector in communication networks”, Disc. Math. and Appl., 24:5 (2014), 295–303 | MR | Zbl

[9] 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

[10] Myerson R. B., “Graphs and cooperation in games”, Math. Oper. Res., 2 (1977), 225–229 | DOI | MR | Zbl

[11] Stroeymeyt N., Grasse A. V., Crespi A., Mersch D. P., Cremer S., Keller L., “Social network plasticity decreases disease transmission in a eusocial insect”, Science, 362 (2006), 941–945 | DOI