社会网络中关键节点的识别——基于符号网络的PageRank算法改进

发布时间：2019-09-06 19:58

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

酵釻绲娜鄘滞仄颂匦?然而该算法忽略了网络中节点自身的属性[6,29]。从拓扑结构角度考虑,PageRank算法弱化了局部属性对节点的影响。点度中心度被定义为网络中该节点的邻居节点的数目,用于反映一个节点在网络中的“权力”[1],点度中心度越大说明节点在当前网络中的直接影响力越大,例如,被引次数较多的论文往往比较重要,微博中拥有较多粉丝数的用户影响力也往往较大。然而,PageRank算法在计算节点的重要性时,虽然同时考虑了外部链接的数量和质量,但也在一定程度上削弱了邻居节点数量这一局部属性对节点的影响。图1提取自某社交网络,根据PageRank算法,若阻尼系数0.85,则PR(1)0.2971,PR(2)0.1853,PR(1)PR(2),说明节点1比节点2重要;而根据节点入度的计算方法,InDegree(1)2,InDegree(2)5,InDegree(1)InDegree(2),说明节点2比节点1重要。可见,在该网络中,PageRank算法在一定程度上弱化了入链数对节点的影响。图1某社交网络图在符号网络中,节点的局部特性对识别该节点是否为关键节点具有重要意义。从内容特征角度考虑,用户更喜欢与朋友的朋友而不是朋友的敌人建立正向链接;积极的用户更容易获取社会的支持,更可能被正向链接指向[30];用户更容易同与他们相似的人建立正向链接[31];低地位等级用户更可能与高地位等级用户建立正向链接[32]。而在社会网络情境中,朋友和积极的、相似的、高地位的用户在网络中一般可以认为是重要的、有影响的关键节点。因此,符号网络中节点的入链数和入链性质等局部特性同样是识别关键节点的重要因素。3.2基于PageRank的改进算法——KeyRank算法地位理论认为链接的符号决定了节点地位的差异,一条由i到j的正向链接ijl表示i认为j具有较高的地位,而负向链接ijl表示i

酵釻绲娜鄘滞仄颂匦?然而该算法忽略了网络中节点自身的属性[6,29]。从拓扑结构角度考虑,PageRank算法弱化了局部属性对节点的影响。点度中心度被定义为网络中该节点的邻居节点的数目,用于反映一个节点在网络中的“权力”[1],点度中心度越大说明节点在当前网络中的直接影响力越大,例如,被引次数较多的论文往往比较重要,微博中拥有较多粉丝数的用户影响力也往往较大。然而,PageRank算法在计算节点的重要性时,虽然同时考虑了外部链接的数量和质量,但也在一定程度上削弱了邻居节点数量这一局部属性对节点的影响。图1提取自某社交网络,根据PageRank算法,若阻尼系数0.85,则PR(1)0.2971,PR(2)0.1853,PR(1)PR(2),说明节点1比节点2重要;而根据节点入度的计算方法,InDegree(1)2,InDegree(2)5,InDegree(1)InDegree(2),说明节点2比节点1重要。可见,在该网络中,PageRank算法在一定程度上弱化了入链数对节点的影响。图1某社交网络图在符号网络中,节点的局部特性对识别该节点是否为关键节点具有重要意义。从内容特征角度考虑,用户更喜欢与朋友的朋友而不是朋友的敌人建立正向链接;积极的用户更容易获取社会的支持,更可能被正向链接指向[30];用户更容易同与他们相似的人建立正向链接[31];低地位等级用户更可能与高地位等级用户建立正向链接[32]。而在社会网络情境中,朋友和积极的、相似的、高地位的用户在网络中一般可以认为是重要的、有影响的关键节点。因此,符号网络中节点的入链数和入链性质等局部特性同样是识别关键节点的重要因素。3.2基于PageRank的改进算法——KeyRank算法地位理论认为链接的符号决定了节点地位的差异,一条由i到j的正向链接ijl表示i认为j具有较高的地位,而负向链接ijl表示i
【作者单位】： 南京大学信息管理学院;
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 李村合;吕克强;;一种改进PageRank的新方法[J];计算机系统应用;2008年03期

2 LIU Gui-mei;;An adaptive improvement on PageRank algorithm[J];Applied Mathematics:A Journal of Chinese Universities(Series B);2013年01期

3 张丽;;PageRank算法的改进[J];科学技术与工程;2007年05期

4 孔娟;马亨冰;;PageRank算法的原理与解析[J];福建电脑;2007年01期

5 姜鑫维;赵岳松;;Topic PageRank——一种基于主题的搜索引擎[J];计算机技术与发展;2007年05期

6 刘松彬;都云程;施水才;;基于分解转移矩阵的PageRank迭代计算方法[J];中文信息学报;2007年05期

7 田甜;倪林;;基于PageRank算法的权威值不均衡分配问题[J];计算机工程;2007年18期

8 潘昊;谭龙远;;领域相关自适应的PageRank算法搜索策略[J];计算机应用;2008年09期

9 黄婵;刘发升;;PageRank外推插值法[J];计算机时代;2009年01期

10 林泓;刘朋;李晶晶;龙振海;;基于概率的PageRank改进算法[J];武汉理工大学学报;2009年03期

相关会议论文 前6条

1 ;Key Nodes Mining in Transport Networks Based on PageRank Algorithm[A];2009中国控制与决策会议论文集（3）[C];2009年

2 刘松彬;都云程;施水才;;基于分解转移矩阵的PageRank迭代计算方法[A];内容计算的研究与应用前沿——第九届全国计算语言学学术会议论文集[C];2007年

3 蔺继国;徐锡山;;一种基于用户点击数据的个性化PageRank算法[A];第六届全国信息检索学术会议论文集[C];2010年

4 刘菁菁;林鸿飞;杨志豪;;基于PageRank和锚文本的网页排序研究[A];第三届学生计算语言学研讨会论文集[C];2006年

5 李洋涛;李川;许超;雷晓;徐洪宇;唐常杰;杨宁;;空间评分:基于PageRank的信息网络可视化中节点重要性度量[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

6 刘建毅;王菁华;王枞;;基于语言网络的关键词抽取[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

相关硕士学位论文 前10条

1 李金圻;基于Hadoop的微博舆情分析[D];北京邮电大学;2015年

2 孙乐天;基于PageRank和对象关系的聚类算法研究[D];兰州大学;2016年

3 刘卓然;基于改进PageRank算法的舆情引导技术研究[D];昆明理工大学;2016年

4 王文文;深度重启的Arnoldi加速的PageRank方法[D];上海大学;2016年

5 孟德鑫;基于MapReduce计算模型的PageRank算法的优化与实现[D];南京邮电大学;2016年

6 吴恒超;基于PageRank算法的二分网络社区划分[D];沈阳航空航天大学;2016年

7 郑普亨;基于PageRank算法的Web数据挖掘的研究[D];天津理工大学;2017年

8 王磊;PageRank的算法改进[D];上海交通大学;2009年

9 姜sバ，

本文编号：2532808