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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2019},
     volume = {11},
     number = {2},
     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
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
%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