图上粘合运算的Shapley指数

doi:10.15960/j.cnki.issn.1007-6093.2024.04.012

Abstract

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

CLC Number:

O157.5

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.

Figures/Tables 6

References 25

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. doi: 10.1016/j.ins.2016.08.025
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. doi: 10.1007/s10726-020-09671-5
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. doi: 10.1287/moor.2.3.225
8	李理, 单而芳. 图上合作博弈和图的边密度[J]. 运筹学学报, 2018, 22 (4): 99- 107.
9	李理, 单而芳. 图上博弈的Page-Shapley值[J]. 系统工程理论与实践, 2019, 39 (11): 2771- 2783. doi: 10.12011/1000-6788-2018-0607-13
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. doi: 10.1016/j.socnet.2011.04.001
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. doi: 10.1109/TASE.2010.2052042
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. doi: 10.1016/j.trb.2017.08.029
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.

Shapley距离	$ d_{FR_{n}}^{Sh}=1 $	$ d_{FR_{n}}^{Sh}=2 $
顶点对个数	$ 3n $	$ 4\binom{n}{2} $

Shapley距离	$ d_{B_n}^{Sh}=1 $	$ d_{B_n}^{Sh}=\frac{3}{2} $	$ d_{B_n}^{Sh}=\frac{20}{11} $	$ d_{B_n}^{Sh}=\frac{15}{7} $
顶点对个数	$ 3n+1 $	$ 2n $	$ n^2-n $	$ n^2-n $

Shapley距离	$ 1 $	$ 1+\frac{1}{m} $	$ \frac{3}{2} $	$ 2 $	$ 2+\frac{4}{m^{2}+3m} $	$ 2+\frac{14m+4}{2m^{3}+7m^{2}} $
顶点对个数	$ 2mn $	$ n $	$ n\binom{m}{2} $	$ \binom{n}{2}\binom{m}{1}\binom{m}{1} $	$ \binom{n}{2}\binom{1}{1}\binom{m}{1} $	$ \binom{n}{2} $

[1]	Zhigang CAO, Jin SONG, Sijie WANG, Feng ZHU. Interpretations of the nonexistence of equilibrium in game theory and economics [J]. Operations Research Transactions, 2024, 28(3): 132-142.
[2]	Hongwei GAO, Binbin MENG, Jian LIU, Zhaopeng DAI. Group pursuit-evasion differential games [J]. Operations Research Transactions, 2024, 28(3): 46-62.
[3]	Lele LIU, Bo NING. Unsolved problems in spectral graph theory [J]. Operations Research Transactions, 2023, 27(4): 33-60.
[4]	Hu SHAO, Yue ZHUO, Pengjie LIU, Feng SHAO. Operational research methods for urban traffic flow estimation [J]. Operations Research Transactions, 2023, 27(2): 27-48.
[5]	Zerong CHEN, Han XIAO. Population monotonic allocation schemes for shortest path games [J]. Operations Research Transactions, 2022, 26(2): 101-110.
[6]	YU Jian, JIA Wensheng. Fixed points and equilibrium points [J]. Operations Research Transactions, 2020, 24(2): 14-22.
[7]	CHENG Yukun, MEI Lili. A survey on approximation mechanism design without money for facility location games [J]. Operations Research Transactions, 2018, 22(2): 93-104.
[8]	ZHANG Jiapu, CHATTERJEE Subhojyoti, WANG Feng. Using graph theory and optimization theory to do data mining the large scale buffalo prion protein structure database [J]. Operations Research Transactions, 2017, 21(2): 73-83.
[9]	YANG Dianqing, LI Dengfeng. Properties and solving method of tau-value for fuzzy cooperative games with multilinear extension form [J]. Operations Research Transactions, 2015, 19(2): 61-71.
[10]	XU Yisong, WANG Yingming. A ranking method for the assignment problem with mutiple optimal solutions [J]. Operations Research Transactions, 2014, 18(2): 96-102.
[11]	SU Yingsheng, WANG Xinhui, WANG Xianyu. Incentive policy of retailer to supplier based on investment input [J]. Operations Research Transactions, 2012, 16(4): 21-30.
[12]	LIU Xuwang, WANG Dingwei. Study of bid evaluation behaviors for multi-attribute reverse auction based on game theory [J]. Operations Research Transactions, 2012, 16(4): 11-20.
[13]	WANG Wei, ZHENG Jie. Multi-period complete-information games with self control: a dual-self approach [J]. Operations Research Transactions, 2012, 16(4): 95-104.

Shapley index of the bonding operation on graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 25

Related Articles 13

Recommended Articles

Metrics

Comments