Please wait a minute...
Advanced Search
数据分析与知识发现  2017, Vol. 1 Issue (8): 68-75     https://doi.org/10.11925/infotech.2096-3467.2017.08.08
  首届"数据分析与知识发现"学术研讨会专辑(II) 本期目录 | 过刊浏览 | 高级检索 |
社会网络中关键节点的识别——基于符号网络的PageRank算法改进
陈晓威, 史昱天()
南京大学信息管理学院 南京 210023
Identifying Key Nodes in Social Network with Improved PageRank Algorithm
Chen Xiaowei, Shi Yutian()
School of Information Management, Nanjing University, Nanjing 210023, China
全文: PDF (471 KB)   HTML ( 4
输出: BibTeX | EndNote (RIS)      
摘要 

目的】针对PageRank算法在符号网络中的局限性, 提出其改进算法, 以识别社会网络中的关键节点。【方法】基于符号网络的相关理论, 将PageRank算法与点度中心性相结合, 提出KeyRank算法, 并对Slashdot网站的用户数据进行分析, 以获取用户的KeyRank算法排名。【结果】PageRank算法排名、入度排名、M-PR算法排名与KeyRank算法排名在统计学意义上呈中度正相关。【局限】KeyRank算法忽略了每次迭代时正、负链接的相互作用。【结论】传统算法与KeyRank算法在节点排序上存在差异, 说明链接的符号属性对排序结果产生了重要影响, 改进算法具有一定的理论和实践意义。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
陈晓威
史昱天
关键词 符号网络关键节点PageRank算法点度中心性    
Abstract

[Objective] This paper modifies the PageRank algorithm for signed network, aiming to identify the key nodes in social network. [Methods] Based on the theory of signed network, we proposed the KeyRank algorithm, which combined the PageRank algorithm with node centrality. We examined the new algorithm with user data from the Slashdot website to obtain every user’s ranking. [Results] The rankings of PageRank algorithm, in-degree and M-PR algorithm had significant medium level positive correlation with the rankings obtained with the KeyRank algorithm. [Limitations] The KeyRank algorithm ignored the interactions between the positive and negative links in each iteration. [Conclusions] There is difference between the rankings of nodes by traditional and KeyRank algorithms. The signed links poses important impacts on the rankings, which shows the improved algorithm’s theoretical and practical significance.

Key wordsSigned Network    Key Nodes    PageRank Algorithm    Node Centrality
收稿日期: 2017-06-12      出版日期: 2017-09-28
ZTFLH:  TP301.6  
引用本文:   
陈晓威, 史昱天. 社会网络中关键节点的识别——基于符号网络的PageRank算法改进[J]. 数据分析与知识发现, 2017, 1(8): 68-75.
Chen Xiaowei,Shi Yutian. Identifying Key Nodes in Social Network with Improved PageRank Algorithm. Data Analysis and Knowledge Discovery, 2017, 1(8): 68-75.
链接本文:  
http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2017.08.08      或      http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/Y2017/V1/I8/68
  某社交网络图
Rank $\beta =0$ $\beta =0.25$ $\beta =0.5$ $\beta =0.75$ $\beta =1$
1 937 937 937 90 90
2 1 935 1 935 90 937 937
3 90 90 1 935 1 935 1 935
4 531 531 1 485 1 485 1 485
5 1 485 1 485 531 1 930 1 930
6 1 930 433 1 930 1 930 531 1 635
7 2 208 2 208 1 635 198
8 2 208 1 635 1 635 2 208 2 208
9 179 179 179 59 531
10 5 128 59 59 179 59
11 928 7 821 7 821 198 179
12 1 802 1 802 1 802 7 821 7 821
13 7 821 433 928 1 802 1 050
14 1 635 928 686 1 050 1 802
15 686 686 2 023 176 176
16 534 5 363 678 686 686
17 5 363 2 023 433 928 2 023
18 59 678 5 363 2 023 928
19 9 835 5 128 176 678 678
20 10 762 534 198 5 363 1 953
  各节点的KeyRank排名结果(前20名)
$\beta $值 0 0.25 0.5 0.75 1
0 1 0.8763 0.7746 0.6486 0.5857
0.25 0.8763 1 0.9070 0.7918 0.7050
0.5 0.7746 0.9070 1 0.8847 0.7459
0.75 0.6486 0.7918 0.8847 1 0.7640
1 0.5857 0.7050 0.7459 0.7640 1
  各排名结果的相关系数矩阵
PageRank Indegree M-PR KeyRank
PageRank 1 0.5545 0.7607 0.5417
Indegree 0.5545 1 0.3562 0.4547
M-PR 0.7607 0.3562 1 0.7022
KeyRank 0.5417 0.4547 0.7022 1
  基于Network A的相关系数矩阵
PageRank Indegree M-PR KeyRank
PageRank 1 0.5709 0.5659 0.4401
Indegree 0.5709 1 0.2706 0.3234
M-PR 0.5659 0.2706 1 0.7459
KeyRank 0.4401 0.3234 0.7459 1
  基于Network B的相关系数矩阵
[1] 朱庆华, 李亮. 社会网络分析法及其在情报学中的应用[J]. 情报理论与实践, 2008, 31(2): 179-183.
[1] (Zhu Qinghua, Li Liang.Social Network Analysis Method & Its Application in Information Science[J]. Information Studies: Theory & Application, 2008, 31(2): 179-183.)
[2] 王曰芬, 杭伟梁, 丁洁. 微博舆情社会网络关键节点识别与应用研究[J]. 情报资料工作, 2016, 37(3): 6-11.
[2] (Wang Yuefen, Hang Weiliang, Ding Jie.Identification and Application of Microblog Public Opinion Social Network Critical Node[J]. Information and Documentation Services, 2016, 37(3): 6-11.)
[3] 王陆. 虚拟学习社区的社会网络分析[J]. 中国电化教育, 2009(2): 5-11.
doi: 10.3969/j.issn.1006-9860.2009.02.002
[3] (Wang Lu.Social Network Analysis in Virtual Learning Community[J]. China Educational Technology, 2009(2): 5-11.)
doi: 10.3969/j.issn.1006-9860.2009.02.002
[4] 程苏琦, 沈华伟, 张国清, 等. 符号网络研究综述[J]. 软件学报, 2014, 25(1): 1-15.
[4] (Cheng Suqi, Shen Huawei, Zhang Guoqing, et al.Survey of Signed Network Research[J]. Journal of Software, 2014, 25(1): 1-15.)
[5] Leskovec J, Huttenlocher D, Kleinberg J.Signed Networks in Social Media[C]////Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2010: 1361-1370.
[6] 韩忠明, 陈炎, 刘雯, 等. 社会网络节点影响力分析研究[J]. 软件学报, 2017, 28(1): 84-104.
doi: 10.13328/j.cnki.j0s.005115
[6] (Han Zhongming, Chen Yan, Liu Wen, et al.Research on Node Influence Analysis in Social Networks[J]. Journal of Software, 2017, 28(1): 84-104.)
doi: 10.13328/j.cnki.j0s.005115
[7] 康伟. 基于SNA的突发事件网络舆情关键节点识别——以“7·23动车事故”为例[J]. 公共管理学报, 2012, 9(3): 101-111.
doi: 10.3969/j.issn.1672-6162.2012.03.011
[7] (Kang Wei.Analysis of the Key Nodes in Public Opinion Spread During Emergencies Based on Social Network Theory——A Case Study of the 7·23 Wenzhou High-speed Train Collision[J]. Journal of Public Management, 2012, 9(3): 101-111.)
doi: 10.3969/j.issn.1672-6162.2012.03.011
[8] Zhou T, Wang B H.Catastrophes in Scale-free Networks[J]. Chinese Physics Letters, 2005, 22(5): 1072-1075.
doi: 10.1088/0256-307X/22/5/012
[9] 陈华珊. 业主论坛意见领袖——识别方法及其特点[J]. 青年研究, 2013(6): 65-72.
[9] (Chen Huashan.Measurement, Identification and Characteristics of Opinion Leaders in Real Estate Owner Online Forum[J]. Youth Studies, 2013(6): 65-72.)
[10] King C W, Summers J O.Overlap of Opinion Leadership across Consumer Product Categories[J]. Journal of Marketing Research, 1970, 7(1): 43-50.
doi: 10.2307/3149505
[11] Flynn L R, Goldsmith R E, Eastman J K.Opinion Leaders and Opinion Seekers: Two New Measurement Scales[J]. Journal of the Academy of Marketing Science, 1996, 24(2): 137-147.
doi: 10.1177/0092070396242004
[12] 梦非. 社会化商务环境下意见领袖对购买意愿的影响研究[D]. 南京: 南京大学, 2012.
[12] (Meng Fei.Research of Opinion Leaders’ Impact on Purchase Intention Under Social Commerce Context[D]. Nanjing: Nanjing University, 2012.)
[13] Dasgupta S, Momtaz N J, Aghaie A, et al.Identifying Opinion Leaders for Marketing by Analyzing Online Social Networks[J]. International Journal of Virtual Communities & Social Networking, 2011, 3(1): 43-59.
doi: 10.4018/jvcsn.2011010105
[14] 陈远, 刘欣宇. 基于社会网络分析的意见领袖识别研究[J]. 情报科学, 2015, 33(4): 13-19, 92.
[14] (Chen Yuan, Liu Xinyu.Research on Opinion Leaders Recognition Based on Social Network[J]. Information Science, 2015, 33(4): 13-19, 92.)
[15] 王珏, 曾剑平, 周葆华, 等. 基于聚类分析的网络论坛意见领袖发现方法[J]. 计算机工程, 2011, 37(5): 44-46.
doi: 10.3969/j.issn.1000-3428.2011.05.015
[15] (Wang Jue, Zeng Jianping, Zhou Baohua, et al.Online Forum Opinion Leaders Discovering Method Based on Clustering Analysis[J]. Computer Engineering, 2011, 37(5): 44-46.)
doi: 10.3969/j.issn.1000-3428.2011.05.015
[16] 熊涛, 何跃. 微博转发网络中意见领袖的识别与分析[J]. 现代图书情报技术, 2013(6): 55-62.
[16] (Xiong Tao, He Yue.The Identification and Analysis of Micro-blogging Opinion Leaders in the Network of Retweet Relationship[J]. New Technology of Library and Information Service, 2013(6): 55-62.)
[17] 肖宇, 许炜, 夏霖. 网络社区中的意见领袖特征分析[J]. 计算机工程与科学, 2011, 33(1): 150-156.
doi: 10.3969/j.issn.1007130X.2011.
[17] (Xiao Yu, Xu Wei, Xia Lin.A Feature Analysis of the Opinion Leader in On-Line Communities[J]. Computer Engineering and Science, 2011, 33(1): 150-156.)
doi: 10.3969/j.issn.1007130X.2011.
[18] Matsumura N, Ohsawa Y, Ishizuka M.Mining and Characterizing Opinion Leaders from Threaded Online Discussions[C]////Proceedings of the 6th International Conference on Knowledge-Based Intelligent Engineering Systems & Allied Technologies. 2002: 1267-1270.
[19] Chiang K Y, Hsieh C J, Natarajan N, et al.Prediction and Clustering in Signed Networks: A Local to Global Perspective[J]. The Journal of Machine Learning Research, 2014, 15(1): 1177-1213.
doi: 10.1016/j.datak.2013.07.003
[20] Getoor L, Diehl C P.Link Mining: A Survey[J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 3-12.
[21] Bonacich P, Lloyd P.Calculating Status with Negative Relations[J]. Social Networks, 2004, 26(4): 331-338.
doi: 10.1016/j.socnet.2004.08.007
[22] Li X, Chen H, Li S.Exploiting Emotions in Social Interactions to Detect Online Social Communities[C]//// Proceedings of Pacific Asia Conference on Information Systems, PACIS 2010, Taipei, Taiwan, China. 2010.
[23] Mishra A, Bhattacharya A.Finding the Bias and Prestige of Nodes in Networks Based on Trust Scores[C]////Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India. 2011: 567-576.
[24] Traag V A, Nesterov Y E, Van Dooren P.Exponential Ranking: Taking into Account Negative Links[C]// //Proceedings of the International Conference on Social Informatics.Springer Berlin Heidelberg, 2010.
[25] 顾洁, 胡安安, 刘旭, 等. 社交网络正、负影响力计算——基于符号网络的PageRank算法改进[J]. 情报学报, 2015, 34(7): 725-733.
doi: 10.3772/j.issn.1000-0135.2015.007.007
[25] (Gu Jie, Hu An’an, Liu Xu, et al.Analysis of Positive and Negative Influential Power in Social Networks——Improving PageRank in Signed Networks[J]. Journal of the China Society for Scientific and Technical Information, 2015, 34(7): 725-733.)
doi: 10.3772/j.issn.1000-0135.2015.007.007
[26] Page L, Brin S, Motwani R, et al.The PageRank Citation Ranking: Bringing Order to the Web[R]. Stanford InfoLab, 1999.
[27] 曹军. Google的PageRank技术剖析[J]. 情报杂志, 2002, 21(10): 15-18.
doi: 10.3969/j.issn.1002-1965.2002.10.007
[27] (Cao Jun.The Anatomy of Page Rank Technology of Google[J]. Journal of Intelligence, 2002, 21(10): 15-18.)
doi: 10.3969/j.issn.1002-1965.2002.10.007
[28] Shahriari M, Jalili M.Ranking Nodes in Signed Social Networks[J]. Social Network Analysis and Mining, 2014, 4(1): 1-12.
doi: 10.1007/s13278-014-0172-x
[29] 刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013, 62(17): 178901.
doi: 10.7498/aps.62.178901
[29] (Liu Jianguo, Ren Zhuoming, Guo Qiang, et al.Node Importance Ranking of Complex Networks[J]. Acta Physica Sinica, 2013, 62(17): 178901.)
doi: 10.7498/aps.62.178901
[30] Beigi G, Tang J, Liu H.Signed Link Analysis in Social Media Networks[C]////Proceedings of the 10th International AAAI Conference on Web and Social Media (ICWSM 2016), Cologne, Germany. 2016: 539-542.
[31] Tang J, Chang Y, Aggarwal C, et al. A Survey of Signed Network Mining in Social Media [J]. ACM Computing Surveys, 2014, 9(4): Article 39. DOI: 10.1145/0000000.0000000.
doi: 10.1145/2956185
[32] 王鑫, 王英, 左万利. 基于交互意见和地位理论的符号网络链接预测模型[J]. 计算机研究与发展, 2016, 53(4): 764-775.
doi: 10.7544/issn1000-1239.2016.20151079
[32] (Wang Xin, Wang Ying, Zuo Wanli.Exploring Interactional Opinions and Status Theory for Predicting Links in Signed Network[J]. Journal of Computer Research and Development, 2016, 53(4): 764-775.)
doi: 10.7544/issn1000-1239.2016.20151079
[33] Zheng X, Zeng D, Wang F Y.Social Balance in Signed Networks[J]. Information Systems Frontiers, 2015, 17(5): 1077-1095.
doi: 10.1007/s10796-014-9483-8
[34] Kunegis J, Lommatzsch A, Bauckhage C.The Slashdot Zoo: Mining a Social Network with Negative Edges[C]//// Proceedings of the 18th International Conference on World Wide Web, Madrid, Spain. ACM, 2009: 741-750.
[1] 张磊,马静,李丹丹,沈洋. 语义社会网络的超网络模型构建及关键节点自动化识别方法研究*[J]. 现代图书情报技术, 2016, 32(3): 8-17.
[2] 段晓丽, 王宇. 基于主题分割与PageRank算法的文本主题抽取[J]. 现代图书情报技术, 2010, 26(12): 34-39.
[3] 王建冬. 基于复杂网络方法的国内信息服务研究概念网络分析[J]. 现代图书情报技术, 2009, (10): 56-61.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn