有向图中基于结构的综合相似性度量

在有向图中计算两个节点之间的相似性在包括聚类，协作过滤和社区挖掘在内的各种研究领域中起着越来越重要的作用。 近年来，已经采取了许多相似性措施，例如SimRank，PSimRank和SimFusion。 但是，这些措施仅考虑路径长度相等的预期满足概率，这可能会省略一些潜在的相似节点。 此外，没有区分每个边缘的链接重要性，这可能导致在搜索相似节点时排名不合理。 在本文中，我们提出了一种有效的基于结构的相似性度量ESimRank，用于有效计算有向图中的相似性。 我们首先定义有效关系强度（ERS），以通过利用节点活动，节点吸引力和链接频率来区分链接重要性。 然后，我们通过组合ERS和任何路径长度的预期满足概率来形式化ESimRank方程。 与现有的相似性度量相比，ESimRank可以找到更多潜在的相似节点，并给出质量更高的排名。 为了支持快速相似度计算，我们开发了一种扩展的基于部分和的算法，该算法大大降低了时间复杂度。 通过与最新的相似性度量进行比较，大量实验证明了ESimRank的有效性和效率。