现代电子技术
Modern Electronics Technique
Jun.2022Vol.45No.12
2022年6月15日第45卷第12期
0引言
目前社交网络进入飞速发展阶段，与此同时商业活动也逐渐进入这个领域，如何更快、更好地分析和识别社交网络中的关键用户，对广告传播、市场营销都有着极其重要的作用。在社交网络中挖掘关键用户，不仅可以挖掘出当下的热点信息，也可以预测未来信息的传播，对舆情监测有着极为重要的意义。由于社交平台是开放式的，用户信息不断发生变化，因而采用传统的机器学习分类算法，如SVM 、随机森林等难以在动态信息
更新的情况下进行准确预测[1]。慕鑫提出了一种适应用户描述变化的跨平台用户身份匹配算法AD⁃Link⁃f ，通过建立已有描述和新描述间的联系使模型更快地适应新环境，讨论了一些用户数据可变的问题，但是对特征和用户数同时改变、用户数据分布变化、用户的类别和用户特征同时改变等复杂情况下的问题没有做相关研究[2]。周楚风采用WeiboLeaderRank 算法实现了对并行化Louvain 算法所划分社区的意见
领袖挖掘，但是面对更加复杂的社交网络构成，算法结果的准确性和运行效率难以同时保证[3]。赵翠镕等人提出一种新的用户相似度算法，并结合基于机器学习的用户分类算法构建社交网络的网络空间安全用户挖掘模型，但没有深入研究用
DOI ：10.16652/j.issn.1004⁃373x.2022.12.017
引用格式：石立新.改进PageRank 算法挖掘社交网络关键用户[J].现代电子技术，2022，45（12）：95⁃99.
改进PageRank 算法挖掘社交网络关键用户
石立新
（河南省市场监督管理局信息中心，河南郑州
450000）
摘
要：为了准确而快速地挖掘社交网络中的隐藏关键用户，文中在分析经典PageRank 算法平均分配权值缺点的基
础上，为社交网络中的每个用户节点设置各自的权威度，并结合用户浏览网页的现实情况，模拟用户可以根据主观意向选择节点对应的链接操作，提出一种Au⁃2S⁃PageRank （Authority⁃2Step⁃PageRank ）算法。该算法在程序设计上融合传统Au⁃PageRank 和2S⁃PageRank 算法的优点，可解决权值分配和用户主观意向难以确定这两方面的问题。另外，使用推特数据集对Au⁃2S⁃PageRank 算法、经典PageRank 算法、MBUI⁃SFIM 算法进行测试仿真。实验结果表明，相比另外两种数据挖掘算法，
Au⁃2S⁃PageRank 算法可以更加高效且准确地挖掘有向社交网络中的关键用户。
关键词：PageRank 算法；社交网络；关键用户挖掘；权值分配；主观意向；仿真测试
中图分类号：TN915⁃34；TP391
文献标识码：A
文章编号：1004⁃373X （2022）12⁃0095⁃05
Improved PageRank algorithm for mining key users in social network
SHI Lixin
（Information Center ，Henan Provincial Administration for Market Regulation ，Zhengzhou 450000，China ）
Abstract ：On the basis of analysis on the drawback about weight average allocation of the classical PageRank algorithm ，each user′s authority is set for his own node in the social network ，the link operation corresponding to the node can be selected according to the subjective intention to simulate the user in combination with the actual situation of the web page browse of the user ，and an Au ⁃2S ⁃PageRank （Authority ⁃2Step ⁃PageRank ）algorithm is proposed to mine the hidden key users in social networks quickly and accurately.The algorithm can deal with the difficulties for determining the weight allocation and user ′s subjective intention because it has fused the advantages of traditional Au⁃PageRank and 2S⁃PageRank algorithms in the program
design.The Twitter dataset is used to conduct the testing simulation for Au ⁃2S ⁃PageRank algorithm ，classical PageRank algorithm and MBUI ⁃SFIM algorithm.The experimental results show that Au ⁃2S ⁃PageRank algorithm can mine key users in directed social networks more accurately and efficiently than other two data mining algorithms.Keywords ：PageRank algorithm ；social network ；key user mining ；weight distribution ；subjective intention ；simulation
testing
收稿日期：2021⁃11⁃10
修回日期：2021⁃12⁃15
95
现代电子技术
2022年第45卷
户分类的特征工程，缺乏对特征组合的进一步优化[4]。随着对排序算法研究的不断加深，产生了许多对PageRank 算法[1]的改进算法。Eliacik 等人通过构造基于链接的用户⁃内容图进行用户排序提出TU⁃Rank 算法，该算法在图论基础上挖掘关键用户[5]。Cai 等将TrustRank 算法和角方法引入到社交网络体决策
（SN⁃GDM ）中，基于不同社会影响确定关键用户的权重[6]。和志强等人针对PageRank 平均分配权值的问题进行了改进，根据“网页质量”对权值进行分配，提高了信息获取的准确性，但是算法的复杂度明显增加[7]。
本文重点针对传统PageRank 算法平均分配权值的缺点，在进行权值分配时为每个节点赋予相应的权威度，并且参照用户实际操作情况，模拟用户浏览网页时根据主观意向进行选择下一步操作，从而对网络
中的噪声信息进行有效过滤。在此基础上，参考N ⁃StepPageRank 算法提出一种Au⁃2S⁃PageRank 算法，解决传统PageRank 算法因平均分配权值对结果造成的影响。
1
相关理论
1.1
网络表示
通常来说，一个具体网络有很多种表示形式，在本文
中将其抽象为一个由点集P 和边集E 组成的图F =（P ，E ）。顶点数记为T =||P ，边数[8]
记为N =||E ，用N ij 表示顶点T i 与顶点T j 之间的边数，可能取值为0，1，2，…，称所得矩阵A （F ）=（N ij ）n ×n 为图F 的邻接矩阵，邻接矩阵通常可以用来构成有向图和无向图的概念描述，其定义如下：
a ij =ìí
î1,
顶点V i 和顶点V j 有边0,
顶点V i 和顶点V j 无边
网络有向图如图1所示。有向网络中节点i 的度D i
包括出度D out i 和入度D in
i ，
以点A 为例子，在所有与A 关联的边中，以A 为起点的边的条数称为出度，以A 为终点的边的条数则称为入度，即：
D
out
i
=∑j =1
N
a ij ,D in
i
=∑j =1
N
a ji
式中A 的度由其入度和出度构成，记作：
D i =D out i +D in i
=∑j =1
N
a ij +∑j =1
N
a ji
在图1中节点A 有一个自环，起点和终点都是自身，此时其出度为3，入度为2，故节点A 的度为5。1.2
PageRank 算法的基本原理
PageRank 算法是一种针对链接进行分析并计算网页在互联网中的等级和重要性的排序算法，一个网页的
等级与重要性越高，在搜索引擎中就会越靠前地被展现在网友眼前。PageRank 算法在使用过程中要遵守两个基本前提：第一个前提是如果一个网页被指向的超链接数量越多，就表明这个网页在搜索引擎中的排名越靠前；另一个前提是指向页面的入链质量不同，质量更高
的页面会通过链接向其他页面传递更多的权重。
图1网络有向图
经典的PageRank 算法认为，用户能够通过网页之间的链接来访问整个互联网，但是由于实际的互联网
中会有一组彼此互相连接的没有对组外网页链接的网页，因此其PR 值就一直在这组网页内部，不能传递出去，该现象被称为PR 值沉淀。为了避免这种现象出现，引入阻尼系数d ，则PageRank 公式为：
PR (u i )=(1-d )+d ∑
i =1n
PR (u j )
C (u k )
（1）
式中：
PR (u i )表示网站节点u i 的PR 值；C (u k )表示由网站页面u j 链接出的页面总数u k ；阻尼系数[9]d 一般取0.85。
PageRank 算法的优点是其属于一种静态算法，且
与查询无关，所有的PR 值都可以在离线状态下进行计算来获得，在这种情况下也不影响其响应速度。
当前Google 搜索引擎的巨大成功就是在PageRank 算法的基础上实现的，这也证明了该算法的高效和合理性。
由于PageRank 算法仅仅利用网络连接结构，因而存在的缺陷也不断凸显出来：该算法将当前网页上的权值进行平均化来分配给其全部链接，但是在互联网中各个网页的质量与作用是参差不齐的，就算是在相同的页面中，不同的链接也有着不同的质量与作用，可能存在很大的优劣差别。
实际上，网络中有很多的广告或者注释信息，这些信息相当于噪声信息，经典PageRank 算法在平均分配权值时将这些信息也分配到了和其他链接相同的权值，导致算法在迭代过程中出现平均分配权值不够合理的问题[10⁃11]。如果一个噪声信息链接存在于一个比较重要的页面中，则它有可能会得到比正常页面链接还要靠前的排名，从而会对最终的排名准确性造成影响。
96
第12期
2
Au⁃2S⁃PageRank 算法的提出
2.1
Au⁃PageRank （Authority⁃PageRank ）算法
在经典PageRank 算法中，页面的转移概率平均分配到链出页面，由于新网页的链接较少，其PR 值普遍较低。经典PageRank 算法通过链接计算PR 值，未考虑到网页的内容，存在主题漂移、网页权值均分等问题[12⁃13]。因此，引入网站的权威度p (v i )，该权威度由网页被指向链接与指向链接的比值来确定：
p (v i )=Q
(
)
LinkOut LinkIn
（2）
式中：
LinkOut 为引用网页i 的链接数目；LinkIn 为该网页引用其他网页的链接数目；
Q 是一个与阻尼系数d 相关的常数。在此基础上对经典PageRank 算法即式（1）引入网站权威度分析后，可以提高对网络中节点排名的准确性，得到的Au⁃PageRank （Authority⁃PageRank ）计算公式为：
PR (u i )=(1-d )+d ∑i =1
n
PR (u j )·p (v i )
C (u k )（3）
2.2
2S⁃PageRank （2Step⁃PageRank ）算法
在现实中，用户在浏览网页时，通常可以根据链接
显示的文本信息和自己的主观意向去判断哪个网页更为重要或者更加符合自己的需求。因此假设用户在进行网页的链接选择时，可以看到链接的网页中的内容，即用户可以多看到一层网页内容[14]
。
2Step⁃PageRank 算法示例如图2
所示。
图22Step⁃PageRank 算法图示
经典的PageRank 算法中，用户处于a 页面时，可以看到b ，c ，d 三个页面，此时用户将会以相同的概
率选择这三个页面，即P ab =P ac =P ad =13；现在假设用户可以多看一层，即看到e⁃k 链接，那么此时用户选择b ，c ，d 的概率与他们的出度成正比，即P ab =27，P ac =27，P ad =37。根据以上条件并结合式（1），本文提出一种
改进算法2S⁃PageRank ，公式为：
PR (u i )=(1-d )+d ∑
i =1
n PR (u j )·C (u k )
∑z =1
C (u k )
C (u z )
（4）
式中，
C (u z )表示当前页面中第z 个链接到的页面中的连接数。2.3
Au⁃2S⁃PageRank （Authority⁃2Step⁃PageRank ）算法
结合以上两种算法的思想，即将网络中节点的权威
度和现实情况结合及用户可以在上网时多看一步的前提条件，根据式（2）~式（4），本文提出Au⁃2S⁃PageRank 改进算法，公式如下：
PR (u i )=(1-d )+d ∑
i =1
n PR (u j )·p (v i )·C (u k )
∑z =1
C (u k )
C (u z
)
（5）
该算法综合考虑了有向网络中节点的权威度和现实情况中存在的用户主观意向，对PageRank 算法进行改进，所得到的Au⁃2S⁃PageRank 算法融合了本文提出的Au⁃PageRank 和2S⁃PageRank 两种新型改进算法，实现了针对节点的PR 值进行不平均分配，不仅可以较好地区分网页的重要性程度，并且在计算时可以加快收敛速度。
3
实验及结果
3.1
实验环境及数据
实验环境为联想G470笔记本1台（Windows 7系
统、Intel
Ⓡ
Core i3⁃2350M ********GHz 、2GB RAM ）。
实验数据使用SNAP （Stanford Network Analysis Platform ）提供的推特数据集。SNAP 是一个很常用且能高效率对大型网络进行分析处理的系统，它同时支持图和网两种不同的数据结构[15]。其中，图描述的是拓扑结构，即每个节点都有且只有一个整数ID ，节点之间的边可以是有向的和无向的，并且两个节点之间边的数量是不限的；网可以看成是一种特殊结构的图，是一种节点或者边上赋有具体数据的图。为了验证改进算法的效果，使用SNAP 提供的推特ID 数据模拟网页之间的有向图进行试验。所使用的数据集基本情况如表1所示。
表1实验数据统计基本情况
节点数81306边数
1768149平均聚类系数0.5653最大弱
连通分
量的节
点数
81306最大弱连通分量的边数1768159最大连通分量的节点数68413最大连通分量的边数1685163
最短
路径
长度
7
3.2
算法执行时间
经过对数据的预处理，选取部分具有代表性的节点
分别对经典PageRank 算法、融合用户自身因素与行为
来解决用户主观意向问题的MBUI⁃SFIM 算法[16]，以及本文所提出的Au⁃2S⁃PageRank 算法进行测试。首先分别测试三种算法的运行时间，选取节点数为1000，2000，3000，4000，结果如图3所示。
石立新：改进PageRank 算法挖掘社交网络关键用户
97
现代电子技术2022年第45
卷
图3三种算法的运行时间折线图
由图3可知，三种算法的运行时间都会随着节点数
目的增加而增加，但是它们的运行时间的增长幅度不是
完全一致的。Au⁃2S⁃PageRank算法在节点个数变化时，
运行时间始终优于经典PageRank算法，而MBUI⁃SFIM
和Au⁃2S⁃PageRank算法的运行时间相差无几且随着节
点数的增加，两种算法在运行时间上会慢慢无限靠近，
而经典PageRank的运行时间随着节点数的增加大大延
长；此外，由于改进的Au⁃2S⁃PageRank算法中引入了Au⁃PageRank算法的思想，导致后续随着节点的继续增加，运行时间会慢慢接近于MBUI⁃SFIM算法。这是因
为引入网站权威度分析后虽然能在一定程度上提高对
网络中节点排名的准确性，但会在一定程度上增加网络
节点性能的复杂度，导致算法结果达到收敛的时间
变长。
3.3算法执行结果与比较分析
分别执行经典PageRank、MBUI⁃SFIM和Au⁃2S⁃PageRank算法，得出前20排名情况，如表2所示。关键用户前20名的具体信息表如表3所示。
由表2中的数据可以发现，经典PageRank、MBUI⁃SFIM和Au⁃2S⁃PageRank算法得到的排序结果都有所差异。
1）PageRank。该算法对于一个网页链出的链接是平均分配权重的，没有考虑到现实中的噪声链接，并把权值分配给了这些噪声链接，从而导致排序的准确性降低。例如表1中的ID：813286和ID：1183041虽然排名在第1位和第6位。根据ID具体信息可知，该ID用户在现实当中是公众ID号，含有大量的广告或资讯信息，因此被其他节点大量引用，从而造成排名靠前，但是其自身的重要程度并不明显。
2）MBUI⁃SFIM。该算法考虑到经典PageRank算法的平均分配权值的缺陷，为网络中的部分节点赋有一
个权威度，但权威度主要根据用户主观和互动大小进行权值分配，使得最终排序结果的准确性在一定范围内有所提高。并且考虑到现实中用户的主观因素，融合了用户自身因素与互动行为特征之后，结果与改进的Au⁃2S⁃PageRank算法结果几乎相近。
表2三种算法ID排名结果
排名序号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PageRank
813286
7861312
40981798
3359851
43003845
1183041
11348282
22462180
34428380
31353077
笔记本 热点10671602
48485771
18927441
17093617
90420314
63485337
10350
15439395
30313925
783214
MBUI⁃SFIM
22462180
34428380
783214
40981798
428333
43003845
17868918
19725644
52442002
813286
17868918
96483973
25680767
8088112
31353077
18927441
11348282
90420314
7861312
30313925
Au⁃2S⁃PageRank
783214
133055665
428333
90420314
34428380
22462180
31331740
19725644
21111883
117674417
17868918
63485337
25680767
8088112
31353077
40981798
27633075
43003845
7861312
14120151表2中与经典PageRank算法的结果相比较，由于ID为22462180和34428380的用户主要推送的内容和话题与社会、生活趣味相关，其较易受到推特上广大体的青睐，因此排名分别上升至第1、第2，但是在Au⁃2S⁃PageRank算法结果中两者分别排第5和第4，根据具体信息显示其后者排序结果的准
确性更高。
3）Au⁃2S⁃PageRank。综合考虑之前两种方法，为了弥补经典PageRank算法的平均权值缺陷，Au⁃2S⁃PageRank将分别从两个角度对PageRank算法进行优化，得到Au⁃PageRank算法与2S⁃PageRank算法的思想结合，不仅为网络中的节点赋予不同的权值，同时还考虑到用户的主观意向，使得收敛速度更快，排序结果更加准确。由表2可得出，ID：783214在经典PageRank中排名第20，在MBUI⁃SFIM中排名第3，而在本文算法中排名第1。经过分析可知，该节点的权威度较大，并且用户可以明确得到节点的链接情况，该用户发布的文章内容大多关于游戏、电影和前端科技等资讯，故其在具体信息表中该用户的互动量、评论数以及发帖数也都是
98
第12期
最高的。同样ID：90420314节点排名也有所提高，而ID：40981798和ID：43003845节点在前两种算法中排名都比较靠前，在此算法中排名有一定程度的下降，这是由于两种ID用户内容包含大量的舆论引导内容。在一段时间内获取到的关注度比较高，但从长远看主要以舆论价值为主，因此其关键程度会有所下降。
表3关键用户前20名的具体信息表
ID 783214 133055665 22462180 90420314 19725644 428333 31331740 63485337 21111883 117674417 17868918 25680767 18996905 8088112 31353077 40981798 27633075 43003845 7861312 14120151互动量
16540
13600
12800
12437
11487
10538
96537
85479
81566
77492
54657
53280
38520
34578
31850
29540
28479
21599
19865
18683
评论数
1500
1370
1340
1308
1250
1170
1099
978
962
765
709
658
469
466
379
362
318
307
299
268
发帖数
13500
12000
11475
10582
10562
9873
9544
8679
8451
7749
7145
5438
4736
4179
3875
3689
3470
3185
3049
2987
4结论
本文在分析经典PageRank算法缺点的基础上，考虑有向网络中节点的权威度，并结合现实情况存在的
用户主观意向对PageRank算法进行改进，针对节点的PR 值实现不平均分配，可以较好地区分节点的重要性程度。实验结果表明，改进后的Au⁃2S⁃PageRank算法在运行时间和准确性两方面均优于经典PageRank算法。此外，改进后Au⁃2S⁃PageRank算法与MBUI⁃SFIM算法相比在运行时间上没有明显优势，且随着节点数大量增加，运行时间有可能比MBUI⁃SFIM还要稍长，但是在准确率上要高于MBUI⁃SFIM算法。本文所提出的改进Au⁃2S⁃PageRank算法主要是针对经典PageRank算法在分配权值时平均分配的缺点进行改进，对于PageRank其他方面的缺点并未详细涉及，因此后续有待于研究改进。
参考文献
[1]TORTOSA L，VICENT J F，YEGHIKYAN G.An algorithm for ranking the nodes of multiplex networks with data based on the PageRank concept[J].Applied mathematics and computation，2021（2）：392.
[2]慕鑫.社交网络平台用户身份挖掘的研究[D].南京：南京大学，2018.
[3]周楚风.基于网络爬虫的社区发现及意见领袖挖掘方法研究
[D].北京：北京印刷学院，2020.
[4]赵翠镕，黄建军，孙鹏，等.社交网络中网络空间安全用户挖掘
模型研究[J].现代计算机，2020（12）：4⁃8.
[5]ELIACIK A B，ERDOGAN N.User⁃weighted sentiment analysis for financial community on Twitter[C]//201511th International Conference on Innovations in Information Technology.Dubai：IEEE，2016：36⁃45.
[6]CAI Mei，WANG Yiming，GONG Zaiwu.An extension of social network group decision⁃making based on TrustRank and personas[J].International journal of computational intelligence systems，2020，13（1）：10⁃15.
[7]和志强，陈萌，王梦雪.基于PageRank改进算法的核心专利发
现研究[J].信息与电脑（理论版），2020，32（18）：52⁃55. [8]宁阳，武志峰，宁晴.面向有向网络关键节点识别算法研究[J].
天津职业技术师范大学学报，2020，30（2）：35⁃40.
[9]JIA Chen，DU Yunyan，WANG Siying，et al.Measuring the vibrancy of urban neighborhoods using
mobile phone data with an improved PageRank algorithm[J].Transactions in GIS，2019，23（2）：25⁃30.
[10]臧思思，李秀霞，孔月.基于改进PageRank算法的作者影响
力评价研究[J].情报理论与实践，2019，42（11）：123⁃127.
[11]徐文涛.社交网络中用户影响力及个性化排名相关技术研究
[D].合肥：安徽大学，2017.
[12]王旭阳，任国盛.基于用户行为与页面分析的改进PageRank
算法[J].计算机工程，2016，42（2）：164⁃168.
[13]马宇光.微博营销中融合行为分析的重要用户发现方法研究
[D].沈阳：辽宁大学，2019.
[14]代金龙.社交网络中的影响力模型构建及链接预测算法[D].
青岛：山东科技大学，2018.
[15]BERRY J W，PHILLIPS C A，SAIA J.Making social networks more human：A topological approach[EB/OL].[2019⁃07⁃24]. http：//linelibrary.wiley/doi/ab.
[16]王新胜，马树章.融合用户自身因素与互动行为的微博用户
影响力计算方法[J].计算机科学，2020，47（1）：96⁃101.
作者简介：石立新（1966—），男，山东淄博人，高级工程师，主要从事社交网络方面的研究工作。
石立新：改进PageRank算法挖掘社交网络关键用户99