基于Motif的社交网络用户影响力排序方法研究

LeaderRank已被广泛地用于衡量社交网络中用户的影响力或重要性的排序算法，但传统的LeaderRank

近年来，网络在人们生活中的地位越加凸显，在线社交网络已成为大多数人日常交流和互动的平台。

社交网络中的用户影响力排序是意见领袖挖掘[1]、影响力分析[2] [3]、社会信任度[4]的普遍问题。

PageRank [5]算法被视为在社交网络中对用户影响力排序的通用算法，可将其用来衡量意见领袖挖掘以及影响力分析和社会信任度分析的一种措施。但该算法在应对悬挂节点(出度为0 的节点)、不连通子图或出现环形有向图时会出现排序结果不唯一的现象， 并且该算法用到的阻尼系数d 对每个用户都是统一的， 这点用在不同的用户身上存在着缺陷。Lv 等[6]针对相关的情况，提出了一种LeaderRank 算法，其是在网络中添加一个背景节点，并且将该背景节点与网络中的其他节点双向连接，得到一个G (N + 1, M + 2N)的新的强连通网络，如图1 所示，对网络的噪音有很好的容忍性，相比PageRank 算法收敛更快、准确性更高。

但是LeaderRank 在社交网络分析中有一些限制，在网络中，可能存在一些重要的结构，这些结构可能会对节点的影响力或可信度产生影响。如图1 所示，在LeaderRank 算法中边e12、边e13 和边e14 的权重设为相同的值，但是我们可以看到，相比节点4，节点1 更信任节点2 和节点3，是因为节点2 和节点3 存在相互关系，节点1、节点2 和节点3 构成三角形结构，因此将边e12、边e13 和边e14 的权重设为相同的值是不合理的。因此在社交网络中考虑涉及多个节点的高阶结构是非常重要的。

在本文中， 我们提出了一种基于Motif 的LeaderRank (Motif-based LeaderRank, MLR)算法， 我们捕获网络中Motif 的高阶关系，并将该高阶关系合并到LeaderRank 算法中，用于社交网络用户影响力排序。

文献[7]提到，由于在社交网络方面，许多工作着重于分析三重闭合作为社交网络的重要结构特征以及分析三元配置作为各种社交网络理论的基础，因此，在本文中，我们主要考虑社交网络的三角关系，在本文中我们主要考虑基于社交网络三角关系的3-节点简单Motif。

图2 显示了一些典型的基于社交网络三角关系的3-节点简单Motif，其中M6 表示图1 中节点1、节点2 和节点3 的3-节点简单Motif。我们在美国社交网络及微博客服务数据集Twitter 上进行实验，来提取有影响力用户，我们使用基线算法度中心性方法IND，原始LeaderRank 算法和加权LeaderRank 算法，结果表明我们提出的MLR 算法明显优于基线算法度中心性方法IND，原始LeaderRank 算法和加权LeaderRank 算法。在这项工作中，我们采用线性关系来对基于社交网络三角关系的3-节点简单Motif 的高阶关系和基于边的直接关系进行组合，通过对参数的调节，表明了基于社交网络三角关系的3-节点简单Motif 的高阶关系和基于边的直接关系在计算节点的权威性方面是相互补充的。