基于PageRank算法的社交网络意见领袖识别算法

◆马玉燃

基于PageRank算法的社交网络意见领袖识别算法

◆马玉燃

（贵州航天职业技术学院 贵州 553106）

PageRank算法[1]是目前被广泛应用的一种重要性的排序方法，它根据节点之间的链接结构来给每个节点打分。本文在分析经典PageRank算法平均分配权值缺点的基础上，为网络中的每个节点设置各自的权威度，并结合用户浏览网页的现实情况，使用户可以根据主观意向选择节点对应的链接，提出Au-2Step-PageRank（Authority-2Step-PageRank）算法。实验表明该算法可以更加准确高效地挖掘有向社交网络中的意见领袖。

PageRank算法；社交网络；搜索引擎；PR值

1 引言

社交网络是由个人以及群体构成的由一个或多个因素关联起来的一种社交结构。互联网空间为用户产生新的社交方式提供了极大的可行性。1960年，社交网络的概念第一次在美国伊利诺斯大学提出。之后，成立了第一个社交网站，即“Six Degrees.com”。如今，社交网络受到极大的欢迎，它给用户提供了大量的交流工具。无论是新成员的加入，还是成员之间建立新的联系，整个社交网络都会得到增长，社交网络数据也在急剧膨胀。

在分析这些社交网络的时候，在线社会网络不断发展，商业活动也逐渐进入这个领域，如何更快更好地分析和识别社交网络中的意见领袖，对广告传播、市场营销都有着极其重要的作用。在社交网络中挖掘意见领袖，不仅可以挖掘出当下的热点信息，也可以用来对未来信息传播的预测，对舆情监测有着极为重要的意义。

2 PageRank算法及其改进算法的研究

2.1 PageRank算法的研究现状

随着对排序算法的研究不断加深，产生了许多对PageRank算法的改进算法。受计算机象棋算法设计中一个很成功的策略：“多看几步”的启发，张丽[2]对PageRank算法进行改进并提出了N-StepPageRank算法，在计算网页的转移概率时利用了网页N 步的链接信息，从而提高排名的精确度，但是N-StepPageRank与经典PageRank之间的关系没有显示出来。

古文丽[3]等人对PageRank进行的改进同时解决了权威度和内容相关行两方面需求，更符合用户的需求；蒋永辉[4]提出的NPRO算法提出半模糊核聚类方法引入样本隶属度概念，有效提高了训练精度和分类速度，但是设计的参数较多且不同环境下需要设置不同参数，参数的设定过程较为烦琐。

赵亚娟[5]等人针对PageRank平均分配权值的问题对其进行了改进，根据“网页质量”对权值进行分配，提高了信息获取的准确性，但是算法的复杂度明显增加；王冬[6]等人同样针对经典PageRank平均分配权值的缺陷，提出了NDPagerank（Non-average distribution PageRank）算法，同时计算复杂度也有所增加。

本文重点针对经典PageRank算法平均分配权值的缺点，在进行权值分配时为每个节点赋予相应的权威度，并且参照用户实际操作情况，模拟用户浏览网页时可以根据主观意向进行选择下一步操作，从而对网络中的噪音信息进行了有效的过滤。在此基础上，参考N-StepPageRank算法提出了Au-2S-PageRank算法，解决了经典PageRank算法因平均分配权值对结果造成的影响。

3 Au-2S-PageRank算法的提出

3.1 Au-PageRank（Authority-PageRank）算法

在此基础上对经典PageRank改进后可以提高对网络中节点排名的准确性。

3.2 2S-PageRank（2Step-PageRank）算法

在现实中，用户在浏览网页时，通常可以根据链接显示的文本信息和自己的主观意向去判断那个网页更为重要或者更加符合自己的需求。因此假设用户在进行网页的链接选择时，可以看到链接到的网页中的内容，即用户可以多看到一层网页内容，从而进行选择。如图1所示。

图1 2Step-PageRank图示

在此基础上计算出的概率转移矩阵将会比经典PageRank的转移矩阵更加稀疏，在计算时可以加快收敛速度。

3.3 Au-2S-PageRank（Authority-2Step-PageRank）算法

结合以上两种算法的思想，将网络中节点的权威度和现实情况结合，使用户可以在上网时多看一步，根据公式（2）（3）（4）提出Au-2S- PageRank算法，公式如下：

该算法考虑有向网络中节点的权威度，并结合现实情况对pagerank算法进行改进，针对节点的PR值实现不平均分配，可以较好地区分网页的重要性程度，并且在计算时可以加快收敛速度。

4 实验及结果

4.1 实验数据

为了验证改进算法的效果，使用SNAP提供的推特ID数据模拟网页之间的有向图进行试验。所使用的数据集基本情况如表1所示。

表1 实验数据统计基本情况

4.2 算法执行结果

经过对数据的预处理，选取部分具有代表性的节点分别对经典PageRank算法，Au-PageRank算法，2S-PageRank算法以及Au-2S-PageRank算法进行测试。首先分别测试四种算法的运行时间，分别选取节点数为1000、2000、3000、4000，结果如图2所示。

由图可知，四种算法的运行时间都会随着节点数目的增加而增加，但是其各自的运行时间增加幅度不尽相同。其中PageRank、2S-PageRank和Au-2S-PageRank三种算法随着节点数的增加，其运行时间的增长情况较为接近，而Au-PageRank的运行时间随着节点数的增加大大延长；此外，改进后的Au-2S-PageRank算法在节点增加时，运行时间明显优于经典PageRank算法，但是由于其中含有了Au-PageRank算法的思想，导致后续随着节点的继续增加运行时间会高于2S-PageRank算法。

图2 四种算法的运行时间折线图

5 结论

本文在分析经典pagerank算法缺点的基础上，考虑有向网络中节点的权威度，并结合现实情况对pagerank算法进行改进，针对节点的PR值实现不平均分配，可以较好地区分节点的重要性程度。实验表明改进后的Au-2S-PageRank算法在运行时间和准确性两方面优于经典PageRank算法。Au-2S-PageRank是针对经典PageRank算法在分配权值时进行平均分配的缺点进行的改进，对于其PageRank他方面的缺点并未涉及，因此有待于日后进一步研究改进。

[1]Sergey Brin，Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.[J]. Computer Networks，1998（30）.

[2]张丽. PageRank算法的改进[J]. 科学技术与工程，2007（05）：673-677.

[3]古文丽，陈玮，陈娇，等. 一种改进的PageRank算法[J]. 计算机系统应用，2012（02）：214-217.

[4]蒋永辉，吴洪丽. 新的PageRank优化算法[J]. 计算机工程与应用，2012（06）：94-95+154.

[5]赵亚娟，闫娜. 一种基于网页质量的PageRank算法改进分析[J]. 电脑知识与技术，2014（27）：6365-6366+6368.

[6]王冬，雷景生. 一种基于PageRank的页面排序改进算法[J]. 微电子学与计算机，2009（04）：210-213.