图上粘合运算的Shapley指数

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

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (4): 123-134.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.012

图上粘合运算的Shapley指数

董清风¹, 辜振东², 周倩茹², 周书明²^,*()

1. 福建师范大学经济学院, 福建福州 350117
2. 福建师范大学数学与统计学院, 福建福州 350117

收稿日期:2021-06-18 出版日期:2024-12-15 发布日期:2024-12-20
通讯作者: 周书明 E-mail:zhoushuming@fjnu.edu.cn
基金资助:
国家自然科学基金(61977016);国家自然科学基金(61572010);福建省自然科学基金(2023J01539);福建省自然科学基金(2020J01164);福建省高校数学学科联盟基金项目(2023SXLMMS04);国家留学基金委项目(202108350054)

Shapley index of the bonding operation on graphs

Qingfeng DONG¹, Zhendong GU², Qianru ZHOU², Shuming ZHOU²^,*()

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:2021-06-18 Online:2024-12-15 Published:2024-12-20
Contact: Shuming ZHOU E-mail:zhoushuming@fjnu.edu.cn

摘要/Abstract

摘要：

收益如何进行合理分配是合作博弈研究的重要问题。基于Shapley值的分配规则是合作博弈中应用最广泛的, 它是由诺贝尔经济学奖获得者Shapley提出。图上合作博弈极大地丰富了博弈论的研究方法, 而图上Shapley值被广泛应用于社交网络节点影响力、社团探测和链路预测等方面。图上Shapley距离是基于Shapley值提出的且可用来度量图中一个顶点访问另一个顶点的成本。类似于图论中Wiener指数和Kirchhoff指数, 我们提出一个新的图参数——Shapley指数。本文确定了三类粘合图(友谊图、书图和广义玫瑰图)的Shapley距离和Shapley指数的解析表达式。这些实例分析为其他更复杂的拓扑结构的Shapley指数的计算提供方法指引。

关键词: 图论, 博弈论, 粘合运算, Shapley距离, Shapley指数

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

中图分类号:

O157.5

董清风, 辜振东, 周倩茹, 周书明. 图上粘合运算的Shapley指数[J]. 运筹学学报（中英文）, 2024, 28(4): 123-134.

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.

图/表 6

图1

图2

图3

表1

表2

表3

参考文献 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]	曹志刚, 宋瑾, 王思杰, 朱峰. 博弈论和经济学中均衡不存在的解读[J]. 运筹学学报（中英文）, 2024, 28(3): 132-142.
[2]	邵虎, 卓越, 刘鹏杰, 邵枫. 城市交通流量估计的运筹学方法[J]. 运筹学学报, 2023, 27(2): 27-48.
[3]	俞建, 贾文生. 不动点与平衡点[J]. 运筹学学报, 2020, 24(2): 14-22.
[4]	程郁琨, 梅丽丽. 设施选址博弈问题的无支付机制设计研究[J]. 运筹学学报, 2018, 22(2): 93-104.
[5]	张家普, CHATTERJEE Subhojyoti, 王凤. 应用图论分析与最优化理论来数据挖掘大规模水牛普里昂蛋白结构数据[J]. 运筹学学报, 2017, 21(2): 73-83.
[6]	徐屹嵩, 王应明. 指派问题的多重最优解的择优方法[J]. 运筹学学报, 2014, 18(2): 96-102.
[7]	刘旭旺, 汪定伟. 博弈论视角的多属性逆向拍卖评标行为研究[J]. 运筹学学报, 2012, 16(4): 11-20.
[8]	王薇，郑捷. 多期完全信息博弈中的自我控制现象：一个基于双重自我模型的分析框架[J]. 运筹学学报, 2012, 16(4): 95-104.

图上粘合运算的Shapley指数

Shapley index of the bonding operation on graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 25

相关文章 8

编辑推荐

Metrics

本文评价