中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 4: 123 - 134

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.04.012

Shapley index of the bonding operation on graphs

Expand
  • 1. School of Economics, Fujian Normal University, Fuzhou 350117, Fujian, China
    2. School of Mathematics and Statistics, Fujian Normal University, Fuzhou 350117, Fujian, China

Received date: 2021-06-18

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization
Fold

Abstract

How to allocate profit reasonablely is an important issue in cooperative game research. The distribution rule based on Shapley value, proposed by Shapley, the winner of the Nobel Prize in Economics, is the commonly used one in cooperative games. The cooperative game theory on graphs greatly enriches the research methods of game theory, and Shapley value on graphs has been widely applied in node influence, community detection and link prediction of social networks. Shapley distance on graphs is suggested based on Shapley value and it can be used to measure the cost of one vertex to access another one. Analogous to Wiener index and Kirchhoff index in graph theory, a new graph parameter, namely Shapley index, is proposed. In this paper, we establish the analytical expressions of Shapley distance and Shapley index of three kinds of conglutinate graphs, such as friendship graphs, book graphs and generalized rose graphs. These empirical examples provide methodological guidance for the computation of Shapley index of other complex topological structures.

Key words： graph theory; game theory; bonding operation; Shapley distance; Shapley index

Cite this article

Qingfeng DONG, Zhendong GU, Qianru ZHOU, Shuming ZHOU . Shapley index of the bonding operation on graphs[J]. Operations Research Transactions, 2024 , 28(4) : 123 -134 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.012

References

1 Shapley L S. A value for $n$-person games [M]//Kuhn H, Tucker W (Eds. ). Contributions to the Theory of Games II, Princeton: Princeton University Press, 1953.
2 Gallardo J M , Jiménez N , Jiménez-Losada A . A Shapley measure of power in hierarchies[J]. Information Sciences, 2016, 372, 98- 110.
3 Sharma S , Abhyankar A R . Loss allocation for weakly meshed distribution system using analytical formulation of Shapley value[J]. IEEE Transactions on Power Systems, 2017, 32 (2): 1369- 1377.
4 Skibski O , Rahwan T , Michalak T , et al. Enumerating connected subgraphs and computing the myerson and shapley values in graph-restricted games[J]. ACM Transactions on Intelligent Systems and Technology, 2019, 10 (2): 1- 25.
5 Manuel C M , Martín D . A monotonic weighted Shapley value[J]. Group Decision and Negotiation, 2020, 29, 627- 654.
6 于晓辉, 杜志平, 张强, 等. 基于$T$-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24 (4): 113- 127.
7 Myerson R B . Graphs and cooperation in games[J]. Mathematics of Operations Research, 1977, 2, 225- 229.
8 李理, 单而芳. 图上合作博弈和图的边密度[J]. 运筹学学报, 2018, 22 (4): 99- 107.
9 李理, 单而芳. 图上博弈的Page-Shapley值[J]. 系统工程理论与实践, 2019, 39 (11): 2771- 2783.
10 单而芳, 蔡蕾, 曾晗, 等. 超网络中心性度量的$\upsilon$-Position值方法[J]. 运筹与管理, 2020, 29 (5): 135- 142.
11 Pozo M , Manuel C , González-Arangüena E , et al. Centrality in directed social networks: A game theoretic approach[J]. Social Networks, 2011, 33, 191- 200.
12 Narayanam R , Narahari Y . A Shapley value-based approach to discover influential nodes in social networks[J]. IEEE Transactions on Automation Science and Engineering, 2011, 8 (1): 130- 147.
13 Hadas Y , Gnecco G , Sanguineti M . An approach to transportation network analysis via transferable utility games[J]. Transportation Research Part B Methodological, 2017, 105, 120- 143.
14 Jonnalagadda A , Kuppusamy L . A cooperative game framework for detecting overlapping communities in social networks[J]. Physica A$:$ Statistical Mechanics and Its Applications, 2018, 491, 498- 515.
15 Buckley F , Harary F . Distance in Graphs[M]. Redwood City: Addison-Wesley, 1990.
16 Jayanth S , Venkat A . Application of mahalanobis distance as a lean assessment metric[J]. International Journal of Advanced Manufacturing Technology, 2006, 29 (11-12): 1159- 1168.
17 Li T , Dong H , Shi Y , et al. A comparative analysis of new graph distance measures and graph edit distance[J]. Information Sciences, 2017, 403-404, 15- 21.
18 Senoussaoui M , Kenny P , Stafylakis T , et al. A study of the cosine distance-based mean shift for telephone speech diarization[J]. IEEE/ACM Transactions on Audio Speech and Language Processing, 2014, 22 (1): 217- 227.
19 Wiener H . Structural determination of paraffin boiling points[J]. Journal of the American Chemical Society, 1947, 69, 17- 20.
20 Asir T , Rabikka V . The Wiener index of the zero-divisor graph of $\mathbb{Z}_n$[J]. Discrete Applied Mathematics, 2022, 319, 461- 471.
21 Klein D J , Randi? M . Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12, 81- 95.
22 Sardar M S , Pan X , Xu S . Computation of resistance distance and Kirchhoff index of the two classes of silicate networks[J]. Applied Mathematics and Computation, 2020, 381, 125283.
23 Gallardo J M , Jiménez N , Jiménez-Losada A . A Shapley distance in graphs[J]. Information Sciences, 2018, 432, 269- 277.
24 Gu Z D , Zhou S M , Liu J F , et al. Shapley distance and Shapley index for some special graphs[J]. Parallel Processing Letters, 2020, 30 (4): 2050012.
25 Bondy J A , Murty U S R . Graph Theory[M]. Berlin: Springer, 2008.
Options
Outlines

/

〈 〉