社交网络中的关注者，以delicious网站为例外文翻译资料

社交网络中的关注者，以delicious网站为例

摘要：查找相关信息时不仅限于搜索引擎。为了其他所有用户的利益，网络社区能够放大一小部分的超级用户的影响力。通过选择合适的关注者能够增强用户信息的深度和广度。例如在delicious.com中，用户订阅了关注者的收藏集，这些收藏集导致了不需要搜索引擎就能够达到更深入，更广泛的范围。为了巩固这种群体搜索，必须利用关注者拓扑并挖掘出有影响力的用户。谷歌的PageRank，在万维网中作为世界上成功的搜索算法，被证明在人际网络中效果较差。因此，我们设计了一种自适应、无参数的算法—LeaderRank用来量化用户影响力。结果表明，LeaderRank在用户排序方面优于PageRank，在对抗干扰数据时具有更强的鲁棒性。同时也说明了关注者的意识、影响力可能会加快社交网络的发展，从而增强群体搜索的能力。

引言：

许多社交网络，如twitter.com和delicious.com允许数百万用户进行互动，其中一些成员比其他成员拥有更大的影响力。识别这些有影响力的人用户并不容易，但识别它们至关重要：在同一个在线社区内实现增强个人在深度和广度上发现新信息的能力，这是难以想象的，而一种有效的方法便是利用有影响力的用户。以万维网为例，尽管有许多有用的页面，但万维网的庞大规模为综合信息探索带来了巨大的障碍。除了搜索引擎之外，还有另一种信息获取模式，是利用网络能力，从不同的专家那里获得有用的网页。这种群体搜索[1,2]在某一天可能会补充当前的基于孤立查询的搜索范例，其成功的关键是识别社交社区中有影响力的用户。

为了识别有影响力的用户，我们检查了一个代表性的在线社交网络delicious.com。的主要功能delicious.com对于个人来说就是收集有用的书签，那么特定的书签就可以很容易地在成千上万的书签中被调用。但对很多用户来说，它的新功能——人脉联网——更有意思。输入delicious.com用户可以选择其他用户作为他们的关注者，也就是说，关注者的书签通常是有用的，对这些书签的订阅将是自动的。我们称之为粉丝的用户可以反过来成为其他用户的关注者。这些关注者与粉丝之间的关系连接了大约50万美味用户，形成了一个关注者网络。为了量化个体影响力，关注者网络的复杂结构和拓扑结构体现了非平凡却又必不可少的信息。

虽然这个关注者网络对于确定关注者有很大的信息量，但是要利用好这个网络是很有挑战性的[3-7]。首先，关注者结构是复杂的，通过无限地爬上关注者的阶梯并逆流而上并不具有启发性。此外，仅仅考虑关注者本身并不能提供绝对的影响力，因为作为信息源和对用户影响力贡献的是整个上游连接。同样，正如我们在实验中看到的，仅仅计算粉丝的数量并不能很好地量化关注者的重要性。然而，一个复杂的模型可以揭示内在结构，并确定有价值的关注者。

为了更好地利用关注者网络，我们将设计一种类似于PageRank的方法，该方法基于超链接网络对网页进行有效的排序。然而，随着人际关系的快速发展，关注者网络有了根本的不同，这使得适应性对于用户排序是必不可少的。例如，当用户添加或删除前导序列时，描述随机信息获取的概率应该自我调整。当这个概率由PageRank[8,9]中的一个外部参数控制时，我们设计了我们的LeaderRank算法，其中这个概率是自适应和个性化的，从而产生了一个容易适用于任何类型图的无参数算法。这种优势消除了在快速发展的网络上对参数测试和PageRank校准的频繁需求。仿真结果表明，我们的LeaderRank算法在识别那些导致有用信息快速、广泛传播的用户方面的性能优于PageRank。此外，LeaderRank对噪声数据的容忍度更高，并且对操作具有稳健性。

除了排名，本研究可能会揭示未来的设计社区规则和在线社交网络。关注者认同强化了处于有利地位的个人在信息探索中的深度和广度，在信息探索中，整个社会受益于群体产出。一个强大的排名算法也劝阻人们的操纵[10]。在本文中，我们将比较基于关注者网络的排名与基于粉丝数量的简单排名。通过模拟和实验，我们将看到排序算法如何识别社交网络中的有影响力的用户。有兴趣的读者可以试试网页http:rank.sesamr.com在这里我们实现LeaderRank来对用户进行排序delicious.com.

数据与方法：

在许多在线应用程序中，用户能够选择其他用户作为他们的信息源。我们用一个从粉丝到他们领袖的有方向链接的网络来代表这些用户关系。链接方向对应的是来自粉丝对其领袖的投票，而大众领袖会有大量的链接。我们使用这个约定，因为它匹配我们的算法中的随机游走的方向，但可以注意到，网络中的信息流的方向是相反的，即从关注者到粉丝。我们的目标是基于此网络拓扑对所有用户进行排序。

LeaderRank

我们考虑一个由个节点和个有向链路组成的网络。节点与用户相对应，并根据关注者和粉丝之间的关系建立链接。为了对用户进行排序，我们引入了一个通过双向链接连接到每个用户的节点（参见图1）。网络因此变得紧密相连，并由节点和链路组成。

图1.节点和LeaderRank算法的示意图

为了开始排序过程，我们给每个节点（除了节点）分配一个资源单元，然后通过有向链接平均分配给节点的邻居。该过程持续进行，直至达到稳定状态。在数学上，这个过程等价于有向网络上的随机游动，它由随机矩阵来描述，其中元素代表下一步随机游动的概率。如果节点指向和，则，而表示的出度，即关注者的数量。因此，此概率流对应粉丝对关注者的投票，设

(1)

对于所有节点（节点除外），初始评分由给出，对于节点，由给出。

节点的存在使得不可约，因为网络是强连接的。节点还确保来自任意节点的号和号回路共存，这意味着为正，即的所有元素均大于零。当自然数的为正时，非负为原语。根据定理，具有唯一特征向量的最大特征值1。我们在支持信息的文本中概述了原始性和收敛性的证明。所有的评分因此收敛到表示为的唯一稳态，其中是收敛时间。在稳定状态下，我们将节点的分数均匀分布到所有其他节点，以保存感兴趣节点上的分数。因此我们定义用户的最终评分为关注者评分，即

(2)

其中是稳态时节点的评分。基于上述性质，在排序中应用LeaderRank有几个优点，包括：(i)无参数，(ii)广泛适用于任何类型的图，(iii)收敛于唯一的排序，以及(iv)初始条件的独立性。对于感兴趣的读者，我们在的文本的最后一节中附了LeaderRank的源代码。为了说明排序过程，我们在图1中提供了一个简单的排序示例，收敛后，6个用户的最终得分分别为。因此，用户被LeaderRank算法评为最高。

PageRank

我们简要地描述了PageRank算法，并与我们的排名结果进行了比较。PageRank是Google搜索引擎的基础，代表了超链接网络上的一次随机漫步。参数是指网页冲浪者跳转到随机网站的概率，是指网页冲浪者继续浏览超链接的概率。因此被称为返回概率，即网络冲浪者返回并开始新的随机游走的概率。在这种情况下，网页在时间的由

其中当时，否则为0。第一学期和第二学期分别对应于随机冲浪者和通过超链接到达的冲浪者的贡献。

在比较排名结果之前，将PageRank应用于社交网络有几个缺点。首先，PageRank[8,9]中的返回概率是必需的，因为算法的收敛性只在强连通网络上得到保证。该算法引入了一个参数，导致了对参数和评价指标的大量测试，使得PageRank对快速进化的社交网络的适应性变差。此外，所有用户的返回概率相同，无论其意义如何。对于悬挂用户（没有关注者的用户），需要特定治疗将其所有概率统一分配回网络[8]。所有这些缺点都限制了应用PageRank对社交网络中的用户进行排名以及其他排名任务的潜力。

LeaderRank与PageRank的差别

LeaderRank和PageRank的一个明显区别在于公式，LeaderRank中的节点在调节概率流中起着重要作用，使得LeaderRank参数不存在。一个本质区别在于动态的核心，如在LeaderRank中，流向节点的分数流与选择的关注者数成反比，而在PageRank中没有这样的关系。我们在图中展示了到节点的评分流与到PageRank中随机节点的评分流之间的比较。这些评分流程的可能经验类比如图所示。在数学上，到节点的分数流类似于PageRank中的返回概率，而分数流与前导序列数目的依赖关系使得LeaderRank能够适应快速演化的网络。相反的比例是合理的，因为具有少数先导节点的节点接收到的信息较少，因此从节点（对应于到节点的较大评分流）获取的信息较多。同样的情况也发生在互联网上，因为上网的人选择超链接的机会有限，跳转到另一个随机网站的机会更高。文本的第一部分给出了更详细的讨论。

数据分析

我们在从全球最大的在线书签网站获得的关注者网络上应用LeaderRank算法，delicious.com根据重要性对用户进行排序。用户在delicious.com允许以书签形式收集URL，并鼓励选择前导序列列表作为信息来源。我们将要测试的数据集是在2008年5月收集的，由582377个用户和1686131个定向链接组成。其中571686用户属于巨型组件，而其他组件中的用户总数均小于巨型组件的0：1。实际上，第二到第五大组件中的用户数量分别为58、53、44和35。因此我们只研究最大的组分。最大分量中的有向链路数为1675008，其中338756个链路（169378对）是相互的。若将网络视为无向网络，聚类系数[11]和分类系数[12]分别为0.241和20.012，而用户间的平均最短距离约为5.104。

结论

我们首先显示了获得的排名之间的差异LeaderRank，PageRank和粉丝数量。表1显示按这三种方法排名前20位的用户。有一个初步评估这些排名结果，我们进行比较具有独立于用户的内在品质的排名排名算法。具体来说，我们比较数量保存的书签可能代表用户的活动。在特别是，用户blackbelfjones，regine，zephoria和djakes谁出现在LeaderRank的前20名，但没有出现在PageRank中活动分别为5925,6711,1486和5082小型活动3,377,1516和242用户thetechguy，cffcoach，samoore和kevinrose出现在PageRank的前20名但没有在LeaderRank中。这表明LeaderRank表现优异PageRank用于识别活跃用户。

的文本中给出了更详细的结果和相应的讨论。例如，SI的表S1中给出了前100名用户的表格。我们还检查了所有方法的分数和等级之间的关系，其中观察到Zipf定律，并在的图中显示。LeaderRank、PageRank和粉丝数量获得的排名重叠如的图所示。通过比较排名和关注者数之间的关系（如的图所示），我们发现PageRank倾向于将高排名分配给具有较少关注者数的节点。对关注者人数多的节点是不公平的，因为关注者人数少的用户不一定有影响力，操纵者可能会故意去掉一些关注者来提升自己的排名。在下面我们通过仿真和实验，比较了LeaderRank、PageRank和按粉丝数排名。

表1.三种方法排名前20位的用户

按粉丝数量与排名的比较

基于网络拓扑结构的排行算法，其排行效果优于仅考虑粉丝数量的排行算法。我们再次比较了用户与内在质量的等级，内在质量独立于算法。一个很好地表征用户影响的数量是他们收集的书签被其他人保存的次数。虽然关注者并不是书签的唯一来源，但有影响力的用户仍然应该导致其收藏书签的广泛传播。我们将用户收集的书签数量表示为，将其他用户保存这些书签的次数表示为。只推荐高质量书签的用户应该具有较大的值。

我们在图2中按LeaderRank以他/她的排列降序显示用户的粉丝数量。圆圈的大小与的值成正比。正如我们所看到的，有一些用户被LeaderRank排到了很高的位置，但是他们的粉丝数量很少。如果按球迷的多少来排名，他们的排名会大大下降。但是，用红色圆圈突出显示的用户具有相对较大的，这表明他们确实是高质量用户。这些用户是通过LeaderRank而不是通过粉丝的数量来识别的。相反，有用户的排名低，但有大量的球迷。以蓝色圆圈突出显示的用户具有较小的，但拥有大量的粉丝。根据LeaderRank，它们的排名正确偏低。

图2.按LeaderRank降序排列的用户粉丝数

为了更好地理解这些用户，我们在图3中绘制了一些特殊的例子，其中的用户拥有少量的粉丝但排名很高，而用户拥有大量的粉丝但排名相对较低。如图3(A)和(b)所示，用户cffcoach和pedersoj后面跟着具有较大值的粉丝，用较大的圈表示。尽管用户kanter和britta拥有更多的粉丝，我们从图3(c)和(d)中可以看到它们被更小的圈包围。LeaderRank正确地给他们一个较低的排名，与排名相比，仅仅是球迷的数量。

同样，仅仅关注者本身并不能提供绝对的影响力，因为它是关注者的全部上游连接，而关注者作为信息源并对用户的影响力起作用。我们在的图中显示，删除所有的关注者可能会对用户的社会影响产生负面影响。所有这些结果表明，关注者网络比简单的排序标准，如球迷或关注者的数量，因此算法，很好地利用拓扑可以提供

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20760]，资料为PDF文档或Word文档，PDF文档可免费转换为Word