运筹学学报 >
2024 , Vol. 28 >Issue 4: 123 - 134
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.04.012
图上粘合运算的Shapley指数
收稿日期: 2021-06-18
网络出版日期: 2024-12-20
基金资助
国家自然科学基金(61977016);国家自然科学基金(61572010);福建省自然科学基金(2023J01539);福建省自然科学基金(2020J01164);福建省高校数学学科联盟基金项目(2023SXLMMS04);国家留学基金委项目(202108350054)
版权
Shapley index of the bonding operation on graphs
Received date: 2021-06-18
Online published: 2024-12-20
Copyright
收益如何进行合理分配是合作博弈研究的重要问题。基于Shapley值的分配规则是合作博弈中应用最广泛的, 它是由诺贝尔经济学奖获得者Shapley提出。图上合作博弈极大地丰富了博弈论的研究方法, 而图上Shapley值被广泛应用于社交网络节点影响力、社团探测和链路预测等方面。图上Shapley距离是基于Shapley值提出的且可用来度量图中一个顶点访问另一个顶点的成本。类似于图论中Wiener指数和Kirchhoff指数, 我们提出一个新的图参数——Shapley指数。本文确定了三类粘合图(友谊图、书图和广义玫瑰图)的Shapley距离和Shapley指数的解析表达式。这些实例分析为其他更复杂的拓扑结构的Shapley指数的计算提供方法指引。
董清风, 辜振东, 周倩茹, 周书明 . 图上粘合运算的Shapley指数[J]. 运筹学学报, 2024 , 28(4) : 123 -134 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.012
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
| 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. |
/
| 〈 |
|
〉 |
