Link prediction: the power of maximal entropy random walk
Link prediction: the power of maximal entropy random walk
复制标题
DOI：
10.1145/2063576.2063741
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Ronghua Li;J. Yu;Jianquan Liu
中科院分区：
文献类型：
--
作者：
Ronghua Li;J. Yu;Jianquan Liu
链接预测是社交网络分析中的一个基本问题。无监督的链接预测中的关键技术是在网络节点之间找到适当的相似性度量。一类疯狂使用的相似性度量基于图上的随机步行。传统的随机步行（TRW）通过等效地处理网络中的所有节点来考虑链接结构，而忽略网络节点的中心性。但是，在许多真实的网络中，网络的节点不仅更喜欢链接到类似的节点，而且更喜欢链接到网络的中心节点。为了解决此问题，我们使用最大熵随机步行（MERW）进行链接预测，该预测结合了网络节点的中心性。首先，我们通过构建特征加权的图G来研究merw在图$ g $上的某些重要特性。我们表明，G上Merw的过渡矩阵和固定分布与G. g。基于G，G，G。我们进一步给出了最大的熵图拉普拉斯人，并展示如何快速计算梅尔沃的命中时间和通勤时间。其次，我们根据MERW提出了四个新的图内核和两个相似性度量，以进行链接预测。最后，为了在链接预测中展示MERW的力量，我们比较了3个合成网络和8个真实网络的27种各种链接预测方法。结果表明，我们新提出的基于MERW的方法在大多数数据集上的最新方法优于最先进的方法。
Link prediction is a fundamental problem in social network analysis. The key technique in unsupervised link prediction is to find an appropriate similarity measure between nodes of a network. A class of wildly used similarity measures are based on random walk on graph. The traditional random walk (TRW) considers the link structures by treating all nodes in a network equivalently, and ignores the centrality of nodes of a network. However, in many real networks, nodes of a network not only prefer to link to the similar node, but also prefer to link to the central nodes of the network. To address this issue, we use maximal entropy random walk (MERW) for link prediction, which incorporates the centrality of nodes of the network. First, we study certain important properties of MERW on graph $G$ by constructing an eigen-weighted graph G. We show that the transition matrix and stationary distribution of MERW on G are identical to the ones of TRW on G. Based on G, we further give the maximal entropy graph Laplacians, and show how to fast compute the hitting time and commute time of MERW. Second, we propose four new graph kernels and two similarity measures based on MERW for link prediction. Finally, to exhibit the power of MERW in link prediction, we compare 27 various link prediction methods over 3 synthetic and 8 real networks. The results show that our newly proposed MERW based methods outperform the state-of-the-art method on most datasets.