A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances
A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances
复制标题
DOI：
10.1145/1401890.1401984
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
Luh Yen;M. Saerens;Amin Mantrach;M. Shimbo
中科院分区：
文献类型：
--
作者：
Luh Yen;M. Saerens;Amin Mantrach;M. Shimbo
这项工作介绍了一个新的家庭的链接为基础的加权有向图的节点之间的相异性措施。这种度量称为随机最短路径（RSP）相异度，它依赖于一个参数θ，并且有一个有趣的特性，当θ很大时，它会在一端减少到标准最短路径距离，而当θ很小（接近零）时，它会在另一端减少到通勤时间（或阻力）距离。直观地说，它对应于随机步行者为了从起始节点到达目的地节点而在图中保持恒定的熵（与θ相关）扩展所引起的预期成本。因此，参数θ使图上的简单随机游走逐渐偏向最短路径策略。通过采用统计物理的方法和计算所有可能的路径（离散路径积分）的总和，它表明，RSP相异性从每个节点到一个特定的感兴趣的节点可以有效地计算通过求解两个线性系统的n个方程，其中n是节点的数量。另一方面，每对节点之间的相异度通过对n × n矩阵求逆来获得。所提出的度量可以用于各种图挖掘任务，例如计算介数中心性，发现密集社区等，如实验部分所示。
This work introduces a new family of link-based dissimilarity measures between nodes of a weighted directed graph. This measure, called the randomized shortest-path (RSP) dissimilarity, depends on a parameter θ and has the interesting property of reducing, on one end, to the standard shortest-path distance when θ is large and, on the other end, to the commute-time (or resistance) distance when θ is small (near zero). Intuitively, it corresponds to the expected cost incurred by a random walker in order to reach a destination node from a starting node while maintaining a constant entropy (related to θ) spread in the graph. The parameter θ is therefore biasing gradually the simple random walk on the graph towards the shortest-path policy. By adopting a statistical physics approach and computing a sum over all the possible paths (discrete path integral), it is shown that the RSP dissimilarity from every node to a particular node of interest can be computed efficiently by solving two linear systems of n equations, where n is the number of nodes. On the other hand, the dissimilarity between every couple of nodes is obtained by inverting an n x n matrix. The proposed measure can be used for various graph mining tasks such as computing betweenness centrality, finding dense communities, etc, as shown in the experimental section.