图上粘合运算的Shapley指数  

Shapley index of the bonding operation on graphs

作　　者：董清风[1] 辜振东 周倩茹 周书明[2] DONG Qingfeng;GU Zhendong;ZHOU Qianru;ZHOU Shuming(School of Economics,Fujian NormalUniversity,Fuzhou 350117,Fujian,China;School of Mathematics and Statistics,Fujian Normal University,Fuzhou 350117,Fujian,China)

机构地区：[1]福建师范大学经济学院,福建福州350117 [2]福建师范大学数学与统计学院,福建福州350117

出　　处：《运筹学学报(中英文)》2024年第4期123-134,共12页Operations Research Transactions

基　　金：国家自然科学基金(Nos.61977016,61572010);福建省自然科学基金(Nos.2023J01539,2020J01164);福建省高校数学学科联盟基金项目(No.2023SXLMMS04);国家留学基金委项目(No.202108350054)。

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

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

分 类 号：O157.5[理学—数学]