标题： 一种使用博弈论方法的新边介数度量：在分层社区检测中的应用 显示英文标题

标题： A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection

摘要： 在本文中，我们正式定义了分层聚类网络问题（HCNP），即寻找网络的良好分层划分的问题。这个新问题关注的是聚类的动态过程，而不是聚类过程的最终结果。为了解决这个问题，我们引入了一种新的网络分层聚类算法，该算法基于一种新的最短路径介数度量。为了计算它，每对节点之间的通信是根据建立该通信的节点的重要性来加权的。与每对节点相关联的权重或重要性是通过一个称为线性模块化博弈的游戏的Shapley值来计算的。这种新的度量（节点博弈最短路径介数度量）用于通过消除具有最高值的链接来获得网络的分层划分。为了评估我们算法的性能，我们引入了几种标准，使我们能够从两个观点对网络的不同树状图进行比较：模块化和同质性。最后，我们提出了一种更快的算法，该算法基于节点博弈最短路径介数度量的简化，其在稀疏网络上的复杂度是二次的。从计算角度来看，这种快速版本与其他分层快速算法具有竞争力，并且通常能提供更好的结果。 显示英文摘要

摘要： In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new ierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by he importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, (the node-game shortest path betweenness measure), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure, whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.