發(fā)布時間：2017-08-16 09:16

  本文關鍵詞：一種基于Sketch的Top-k緊密中心性快速搜索算法

  更多相關文章： 緊密中心性 圖算法 近似算法 圖分析 社交網(wǎng)絡

【摘要】：在大數(shù)據(jù)的時代背景下,由于網(wǎng)絡數(shù)據(jù)(network data)能有效簡潔地描述社交網(wǎng)絡、電子商務、醫(yī)療記錄、在線教育等多種應用中各類復雜關系,越來越受到工業(yè)界和學術界的關注.在社交網(wǎng)絡分析任務中,一個基本操作是從網(wǎng)絡中發(fā)現(xiàn)重要程度前k大的節(jié)點.緊密中心性(closeness centrality)是一種常見的節(jié)點重要性刻畫指標,它用節(jié)點在網(wǎng)絡中心的程度來反映節(jié)點的重要性.用緊密中心性衡量節(jié)點重要性進行節(jié)點搜索的問題稱為top-k緊密中心性搜索問題.然而,傳統(tǒng)的精確算法由于其多項式級別的復雜度無法高效地擴展到大規(guī)模的網(wǎng)絡數(shù)據(jù)上.近來,研究人員提出了近似算法,通過犧牲結果精度來獲得性能提升.通過分析發(fā)現(xiàn),目前存在的近似算法雖然性能得到了有效提升,但是結果精度犧牲過大.為了解決這個問題,該文設計了一種新穎的近似算法,叫做基于Sketch的緊密中心性搜索算法.此近似算法應用了一個全新的計算方式,利用Sketch估計同一距離的鄰居數(shù)目,然后得到近似的最短距離之和,最終得到各個節(jié)點的緊密中心性的估計值.此算法的時間復雜度為O(mt Dmax),其中t是常數(shù),Dmax是網(wǎng)絡直徑,m是網(wǎng)絡邊數(shù).根據(jù)實際社交網(wǎng)絡的小世界現(xiàn)象的特性,此近似算法基本是個線性算法.最后,相比于目前存在的精確算法和近似算法,該文通過全面的實驗驗證了基于Sketch的緊密中心性搜索算法在時間性能和結果精度等兩方面的優(yōu)勢.
【作者單位】： 北京大學信息科學技術學院高可信軟件技術重點實驗室;昆士蘭大學信息技術和電子工程學院;
【關鍵詞】： 緊密中心性 圖算法 近似算法 圖分析 社交網(wǎng)絡
【基金】：國家自然科學基金(61272155,61572039) 國家“九七三”重點基礎研究發(fā)展規(guī)劃項目基金(2014CB340405) 深圳政府研究項目(JCYJ20151014093505032)資助~~
【分類號】：TP301.6
【正文快照】： 1引言 近年來,隨著萬維網(wǎng)、Web2.0、移動網(wǎng)絡、社交媒體以及電子商務等技術的迅速發(fā)展,大規(guī)模的網(wǎng)絡數(shù)據(jù)已經無處不在.截至2014年2月,Facebook擁有全球12億用戶,其中僅好友關系已多達2016億條(1).同時,根據(jù)CNNIC的統(tǒng)計(2)表明,截至2013年12月,國內社交網(wǎng)站用戶規(guī)模達2.78億.

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前3條

1 邵浩;陳東方;劉欣;;復雜網(wǎng)絡算法中K-shell與介數(shù)中心性算法的實現(xiàn)[J];現(xiàn)代計算機(專業(yè)版);2014年17期

2 劉建明;張德政;阿孜古麗;劉潔卉;;基于中醫(yī)網(wǎng)絡的中心性算法研究[J];計算機仿真;2008年05期

3 ;[J];;年期

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 付立東;復雜網(wǎng)絡中心性度量及社團檢測算法研究[D];西安電子科技大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前3條

1 馬夢瑤;基于證據(jù)理論的社會網(wǎng)絡中心性結點識別方法研究[D];吉林大學;2016年

2 李明雪;基于社會網(wǎng)絡的社區(qū)發(fā)現(xiàn)和中心性分析算法研究[D];吉林大學;2016年

3 武龍舉;基于復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學;2013年

，

本文編號：682461