Please wait a minute...
Data Analysis and Knowledge Discovery  2017, Vol. 1 Issue (8): 68-75    DOI: 10.11925/infotech.2096-3467.2017.08.08
Orginal Article Current Issue | Archive | Adv Search |
Identifying Key Nodes in Social Network with Improved PageRank Algorithm
Chen Xiaowei, Shi Yutian()
School of Information Management, Nanjing University, Nanjing 210023, China
Download: PDF (471 KB)   HTML ( 5
Export: BibTeX | EndNote (RIS)      
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     
Received: 12 June 2017      Published: 28 September 2017
ZTFLH:  TP301.6  

Cite this article:

Chen Xiaowei,Shi Yutian. Identifying Key Nodes in Social Network with Improved PageRank Algorithm. Data Analysis and Knowledge Discovery, 2017, 1(8): 68-75.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2017.08.08     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/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
$\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
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
[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.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn