發(fā)布時間：2018-12-27 16:46

【摘要】：針對傳統(tǒng)相似度算法無法預測給定頂點存在的鏈接問題,以抽樣方法為基礎(chǔ),提出一種對復雜網(wǎng)絡進行鏈接預測的方法,找出用戶感興趣節(jié)點的相關(guān)鏈接.根據(jù)用戶感興趣的節(jié)點,使用隨機游走的方法,構(gòu)造一個子圖.設(shè)定該子圖的大小使相似度估計值的誤差小于給定的容錯閾值.該方法僅在一個小的包含全局信息的子圖上進行相似度計算,可以使計算時間大大減少.實驗結(jié)果表明,算法的時間復雜度與數(shù)據(jù)集大小呈線性關(guān)系,基于局部指標的常見鄰居(CN)算法、Jaccard以及PA指標算法的時間復雜度與數(shù)據(jù)集大小呈平方關(guān)系,以全局拓撲路徑為基礎(chǔ)的Katz算法的時間復雜度與數(shù)據(jù)集大小呈立方關(guān)系.
[Abstract]:In view of the fact that the traditional similarity algorithm can not predict the link problem of a given vertex, based on the sampling method, a link prediction method for complex networks is proposed to find the relevant links of the nodes of interest to users. According to the nodes of interest to the user, a subgraph is constructed by using the random walk method. The size of the subgraph is set so that the error of similarity estimation is less than the given fault tolerance threshold. This method only computes the similarity on a small subgraph containing global information, which can greatly reduce the computation time. The experimental results show that the time complexity of the algorithm is linearly related to the size of the dataset, and the time complexity of the common neighbor (CN) algorithm based on the local index, the time complexity of the Jaccard and PA index algorithm is square to the size of the data set. The time complexity of the Katz algorithm based on the global topological path is cubic to the size of the dataset.
【作者單位】： 南京航空航天大學計算機科學與技術(shù)學院;揚州大學信息工程學院;
【基金】：國家自然科學基金資助項目(61379066)
【分類號】：O157.5

【相似文獻】

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

1 吳迪;周利娟;林鴻飛;;基于隨機游走的就業(yè)推薦系統(tǒng)研究與實現(xiàn)[J];廣西師范大學學報(自然科學版);2011年01期

2 蘇浩航;張義門;張玉明;解敏;滿進財;;基于改進的壓縮式隨機游走算法對靜態(tài)電源/地網(wǎng)的模擬[J];計算物理;2007年06期

3 宋銳;湯建勛;周健;;工作電流對二頻機抖激光陀螺角隨機游走影響的研究[J];激光雜志;2010年02期

4 周持中;一類具有吸收點的平面隨機游走[J];岳陽大學學報;1996年02期

5 雷鈺麗;李陽;王崇駿;劉紅星;謝俊元;;基于權(quán)重的馬爾可夫隨機游走相似度度量的實體識別方法[J];河北師范大學學報(自然科學版);2010年01期

6 俞琰;邱廣華;;基于局部隨機游走的在線社交網(wǎng)絡朋友推薦算法[J];系統(tǒng)工程;2013年02期

7 何建軍;李仁發(fā);;改進的隨機游走模型節(jié)點排序方法[J];計算機工程與應用;2011年12期

8 鄧貴仕,賴寶全;反饋式隨機游走模型及其在股票投資中應用[J];大連理工大學學報;2004年06期

9 戴穎;;深圳股票市場的隨機游走檢驗[J];商業(yè)經(jīng)濟;2005年11期

10 周軍軍;王明文;何世柱;石松;;基于隨機游走和聚類平滑的協(xié)同過濾推薦算法[J];廣西師范大學學報(自然科學版);2011年01期

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

1 鄭偉;王朝坤;劉璋;王建民;;一種基于隨機游走模型的多標簽分類算法[A];NDBC2010第27屆中國數(shù)據(jù)庫學術(shù)會議論文集A輯一[C];2010年

2 朱松豪;羅青青;梁志偉;;一種改進圖像標注的新方法[A];第24屆中國控制與決策會議論文集[C];2012年

3 燕飛;張銘;譚裕韋;唐建;鄧志鴻;;綜合社會行動者興趣和網(wǎng)絡拓撲的社區(qū)發(fā)現(xiàn)方法[A];NDBC2010第27屆中國數(shù)據(jù)庫學術(shù)會議論文集(B輯)[C];2010年

相關(guān)重要報紙文章 前1條

1 長盛基金管理有限公司研究部副總監(jiān) 李驥;投資自己熟悉的股票[N];證券時報;2006年

相關(guān)博士學位論文 前6條

1 鄧凱英;復雜網(wǎng)絡搜索策略及相關(guān)模型的數(shù)值方法[D];東北師范大學;2015年

2 徐曉華;圖上的隨機游走學習[D];南京航空航天大學;2008年

3 孫甲申;基于主題模型和隨機游走的標簽技術(shù)研究[D];北京郵電大學;2013年

4 呂強;面向高性能和強表達力的自動規(guī)劃[D];中國科學技術(shù)大學;2013年

5 趙學華;統(tǒng)計網(wǎng)絡模型若干關(guān)鍵問題研究[D];吉林大學;2014年

6 廖振;基于查詢點擊核心圖的查詢推薦問題研究[D];南開大學;2013年

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

1 何岱洧;Z~d上使Schramm的上界達到的旋轉(zhuǎn)配置[D];復旦大學;2014年

2 田新春;回火老化效應及其擴散方程[D];蘭州大學;2015年

3 鞠薇;基于隨機游走和圖割算法的PET-CT肺腫瘤分割[D];蘇州大學;2015年

4 祝霖;基于隨機游走的動態(tài)社團劃分算法[D];上海交通大學;2015年

5 孫星;基于部分吸收隨機游走的協(xié)同顯著性檢測[D];大連理工大學;2015年

6 宋文靜;基于多條隨機游走的圖像檢索[D];河南大學;2015年

7 汪幫菊;基于隨機游走的復雜網(wǎng)絡聚類算法研究[D];安徽大學;2016年

8 蘭佳妮;基于分組—偏向隨機游走的閃存地址映射及磨損均衡算法研究[D];西南交通大學;2016年

9 金連寶;基于分層信息融合和隨機游走的顯著性檢測[D];南昌航空大學;2016年

10 馮維思;多屬性隨機游走在社會網(wǎng)絡中的應用[D];西南大學;2016年

，

本文編號：2393331