【摘要】：【目的】針對PageRank算法在符號網絡中的局限性,提出其改進算法,以識別社會網絡中的關鍵節(jié)點。【方法】基于符號網絡的相關理論,將PageRank算法與點度中心性相結合,提出KeyRank算法,并對Slashdot網站的用戶數據進行分析,以獲取用戶的KeyRank算法排名。【結果】PageRank算法排名、入度排名、M-PR算法排名與KeyRank算法排名在統(tǒng)計學意義上呈中度正相關�！揪窒蕖縆eyRank算法忽略了每次迭代時正、負鏈接的相互作用。【結論】傳統(tǒng)算法與KeyRank算法在節(jié)點排序上存在差異,說明鏈接的符號屬性對排序結果產生了重要影響,改進算法具有一定的理論和實踐意義。
【圖文】：

酵釻緄娜鄘滯仄頌匭?然而該算法忽略了網絡中節(jié)點自身的屬性[6,29]。從拓撲結構角度考慮,PageRank算法弱化了局部屬性對節(jié)點的影響。點度中心度被定義為網絡中該節(jié)點的鄰居節(jié)點的數目,用于反映一個節(jié)點在網絡中的“權力”[1],點度中心度越大說明節(jié)點在當前網絡中的直接影響力越大,例如,被引次數較多的論文往往比較重要,微博中擁有較多粉絲數的用戶影響力也往往較大。然而,PageRank算法在計算節(jié)點的重要性時,雖然同時考慮了外部鏈接的數量和質量,但也在一定程度上削弱了鄰居節(jié)點數量這一局部屬性對節(jié)點的影響。圖1提取自某社交網絡,根據PageRank算法,若阻尼系數0.85,則PR(1)0.2971,PR(2)0.1853,PR(1)PR(2),說明節(jié)點1比節(jié)點2重要;而根據節(jié)點入度的計算方法,InDegree(1)2,InDegree(2)5,InDegree(1)InDegree(2),說明節(jié)點2比節(jié)點1重要�？梢�,在該網絡中,PageRank算法在一定程度上弱化了入鏈數對節(jié)點的影響。圖1某社交網絡圖在符號網絡中,節(jié)點的局部特性對識別該節(jié)點是否為關鍵節(jié)點具有重要意義。從內容特征角度考慮,用戶更喜歡與朋友的朋友而不是朋友的敵人建立正向鏈接;積極的用戶更容易獲取社會的支持,更可能被正向鏈接指向[30];用戶更容易同與他們相似的人建立正向鏈接[31];低地位等級用戶更可能與高地位等級用戶建立正向鏈接[32]。而在社會網絡情境中,朋友和積極的、相似的、高地位的用戶在網絡中一般可以認為是重要的、有影響的關鍵節(jié)點。因此,符號網絡中節(jié)點的入鏈數和入鏈性質等局部特性同樣是識別關鍵節(jié)點的重要因素。3.2基于PageRank的改進算法——KeyRank算法地位理論認為鏈接的符號決定了節(jié)點地位的差異,一條由i到j的正向鏈接ijl表示i認為j具有較高的地位,而負向鏈接ijl表示i

酵釻緄娜鄘滯仄頌匭?然而該算法忽略了網絡中節(jié)點自身的屬性[6,29]。從拓撲結構角度考慮,PageRank算法弱化了局部屬性對節(jié)點的影響。點度中心度被定義為網絡中該節(jié)點的鄰居節(jié)點的數目,用于反映一個節(jié)點在網絡中的“權力”[1],點度中心度越大說明節(jié)點在當前網絡中的直接影響力越大,例如,被引次數較多的論文往往比較重要,微博中擁有較多粉絲數的用戶影響力也往往較大。然而,PageRank算法在計算節(jié)點的重要性時,雖然同時考慮了外部鏈接的數量和質量,但也在一定程度上削弱了鄰居節(jié)點數量這一局部屬性對節(jié)點的影響。圖1提取自某社交網絡,根據PageRank算法,若阻尼系數0.85,則PR(1)0.2971,PR(2)0.1853,PR(1)PR(2),說明節(jié)點1比節(jié)點2重要;而根據節(jié)點入度的計算方法,InDegree(1)2,InDegree(2)5,InDegree(1)InDegree(2),說明節(jié)點2比節(jié)點1重要�？梢�,在該網絡中,PageRank算法在一定程度上弱化了入鏈數對節(jié)點的影響。圖1某社交網絡圖在符號網絡中,節(jié)點的局部特性對識別該節(jié)點是否為關鍵節(jié)點具有重要意義。從內容特征角度考慮,用戶更喜歡與朋友的朋友而不是朋友的敵人建立正向鏈接;積極的用戶更容易獲取社會的支持,更可能被正向鏈接指向[30];用戶更容易同與他們相似的人建立正向鏈接[31];低地位等級用戶更可能與高地位等級用戶建立正向鏈接[32]。而在社會網絡情境中,朋友和積極的、相似的、高地位的用戶在網絡中一般可以認為是重要的、有影響的關鍵節(jié)點。因此,符號網絡中節(jié)點的入鏈數和入鏈性質等局部特性同樣是識別關鍵節(jié)點的重要因素。3.2基于PageRank的改進算法——KeyRank算法地位理論認為鏈接的符號決定了節(jié)點地位的差異,一條由i到j的正向鏈接ijl表示i認為j具有較高的地位,而負向鏈接ijl表示i
【作者單位】： 南京大學信息管理學院;
【分類號】：TP301.6

【相似文獻】

相關期刊論文 前10條

1 李村合;呂克強;;一種改進PageRank的新方法[J];計算機系統(tǒng)應用;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];計算機技術與發(fā)展;2007年05期

6 劉松彬;都云程;施水才;;基于分解轉移矩陣的PageRank迭代計算方法[J];中文信息學報;2007年05期

7 田甜;倪林;;基于PageRank算法的權威值不均衡分配問題[J];計算機工程;2007年18期

8 潘昊;譚龍遠;;領域相關自適應的PageRank算法搜索策略[J];計算機應用;2008年09期

9 黃嬋;劉發(fā)升;;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的信息網絡可視化中節(jié)點重要性度量[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算法的優(yōu)化與實現[D];南京郵電大學;2016年

6 吳恒超;基于PageRank算法的二分網絡社區(qū)劃分[D];沈陽航空航天大學;2016年

7 鄭普亨;基于PageRank算法的Web數據挖掘的研究[D];天津理工大學;2017年

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

9 姜sバ，

本文編號：2532808