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

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

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

【相似文獻(xiàn)】

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

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

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

3 ;[J];;年期

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

1 付立東;復(fù)雜網(wǎng)絡(luò)中心性度量及社團(tuán)檢測(cè)算法研究[D];西安電子科技大學(xué);2012年

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

1 馬夢(mèng)瑤;基于證據(jù)理論的社會(huì)網(wǎng)絡(luò)中心性結(jié)點(diǎn)識(shí)別方法研究[D];吉林大學(xué);2016年

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

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

，

本文編號(hào)：682461