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

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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李村合;呂克強(qiáng);;一種改進(jìn)PageRank的新方法[J];計算機(jī)系統(tǒng)應(yī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ìn)[J];科學(xué)技術(shù)與工程;2007年05期

4 孔娟;馬亨冰;;PageRank算法的原理與解析[J];福建電腦;2007年01期

5 姜鑫維;趙岳松;;Topic PageRank——一種基于主題的搜索引擎[J];計算機(jī)技術(shù)與發(fā)展;2007年05期

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

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

8 潘昊;譚龍遠(yuǎn);;領(lǐng)域相關(guān)自適應(yīng)的PageRank算法搜索策略[J];計算機(jī)應(yīng)用;2008年09期

9 黃嬋;劉發(fā)升;;PageRank外推插值法[J];計算機(jī)時代;2009年01期

10 林泓;劉朋;李晶晶;龍振海;;基于概率的PageRank改進(jìn)算法[J];武漢理工大學(xué)學(xué)報;2009年03期

相關(guān)會議論文 前6條

1 ;Key Nodes Mining in Transport Networks Based on PageRank Algorithm[A];2009中國控制與決策會議論文集（3）[C];2009年

2 劉松彬;都云程;施水才;;基于分解轉(zhuǎn)移矩陣的PageRank迭代計算方法[A];內(nèi)容計算的研究與應(yīng)用前沿——第九屆全國計算語言學(xué)學(xué)術(shù)會議論文集[C];2007年

3 藺繼國;徐錫山;;一種基于用戶點擊數(shù)據(jù)的個性化PageRank算法[A];第六屆全國信息檢索學(xué)術(shù)會議論文集[C];2010年

4 劉菁菁;林鴻飛;楊志豪;;基于PageRank和錨文本的網(wǎng)頁排序研究[A];第三屆學(xué)生計算語言學(xué)研討會論文集[C];2006年

5 李洋濤;李川;許超;雷曉;徐洪宇;唐常杰;楊寧;;空間評分:基于PageRank的信息網(wǎng)絡(luò)可視化中節(jié)點重要性度量[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

6 劉建毅;王菁華;王樅;;基于語言網(wǎng)絡(luò)的關(guān)鍵詞抽取[A];第三屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議論文集[C];2007年

相關(guān)碩士學(xué)位論文 前10條

1 李金圻;基于Hadoop的微博輿情分析[D];北京郵電大學(xué);2015年

2 孫樂天;基于PageRank和對象關(guān)系的聚類算法研究[D];蘭州大學(xué);2016年

3 劉卓然;基于改進(jìn)PageRank算法的輿情引導(dǎo)技術(shù)研究[D];昆明理工大學(xué);2016年

4 王文文;深度重啟的Arnoldi加速的PageRank方法[D];上海大學(xué);2016年

5 孟德鑫;基于MapReduce計算模型的PageRank算法的優(yōu)化與實現(xiàn)[D];南京郵電大學(xué);2016年

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

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

8 王磊;PageRank的算法改進(jìn)[D];上海交通大學(xué);2009年

9 姜sバ，

本文編號：2532808