近年來,社交網(wǎng)絡(luò)圖分析受到廣泛關(guān)注,然而由于內(nèi)存的限制,規(guī)模不斷增長(zhǎng)的社交網(wǎng)絡(luò)圖已經(jīng)無法完整放入內(nèi)存,這對(duì)其存儲(chǔ)和分析都帶來了挑戰(zhàn)。圖壓縮通過減少存儲(chǔ)空間需求為應(yīng)對(duì)這個(gè)挑戰(zhàn)提供了一種行之有效的解決方法�，F(xiàn)有面向社交網(wǎng)絡(luò)圖應(yīng)用的壓縮算法多種多樣,有的采用復(fù)雜編碼技術(shù)提升壓縮率但無法保證圖算法的運(yùn)行性能、有的采用簡(jiǎn)單編碼技術(shù)保證圖算法的運(yùn)行性能但犧牲了壓縮率,無法兼顧二者。為解決上述問題,社交網(wǎng)絡(luò)圖壓縮算法需要對(duì)節(jié)點(diǎn)排序以挖掘影響社交網(wǎng)絡(luò)圖壓縮率的關(guān)鍵屬性從而提升壓縮率,并采用簡(jiǎn)單編碼技術(shù)保證圖算法的運(yùn)行性能�，F(xiàn)有研究已經(jīng)證實(shí)社交網(wǎng)絡(luò)圖的壓縮率高度依賴于局部性,而目前挖掘局部性的節(jié)點(diǎn)排序算法未考慮到不同節(jié)點(diǎn)對(duì)局部性的不同影響,僅能挖掘出一部分局部性。本項(xiàng)研究提出了一種基于節(jié)點(diǎn)分類的混合排序算法,對(duì)高度節(jié)點(diǎn)、低度節(jié)點(diǎn)、零度節(jié)點(diǎn)分別采用不同排序策略,挖掘出更多區(qū)域的局部性,提升可壓縮范圍;采用上述算法提出了一種基于節(jié)點(diǎn)分類排序的社交網(wǎng)絡(luò)圖壓縮算法NCOGC,既能獲得良好的壓縮率又能保證圖算法在線有效運(yùn)行;實(shí)現(xiàn)了以廣度優(yōu)先搜索（BFS）、網(wǎng)頁(yè)排名（PageRank）為代表的典型圖處理算法,以驗(yàn)證... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：56 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

LogGap與壓縮率的關(guān)聯(lián)

華 中 科 技 大 學(xué) 碩 士 學(xué) 位 論 文關(guān)注很多的人，而多數(shù)普通人則只關(guān)注自己圈子里的人。本節(jié)以 Twitter 為例分析社交網(wǎng)絡(luò)中的無標(biāo)度性質(zhì)，Twitter1是一家著名的社交網(wǎng)絡(luò)及微博客服務(wù)的網(wǎng)站，網(wǎng)絡(luò)中的節(jié)點(diǎn)表示 Twitter 用戶，網(wǎng)絡(luò)中的邊表示 Twitter 用戶之間的友誼。圖 2-2 展示了Twitter 中節(jié)點(diǎn)的入度分布和出度分布，橫坐標(biāo)為節(jié)點(diǎn)的度大小，縱坐標(biāo)為具有該度大小的節(jié)點(diǎn)個(gè)數(shù)，橫坐標(biāo)和縱坐標(biāo)均為對(duì)數(shù)刻度。可以看到多數(shù)節(jié)點(diǎn)具有很低的度，少數(shù)節(jié)點(diǎn)具有很高的度，入度和出度都呈現(xiàn)冪律分布。社交網(wǎng)絡(luò)圖中也存在一些零度節(jié)點(diǎn)，零度節(jié)點(diǎn)不存在于其他節(jié)點(diǎn)的鄰居中，如果這些節(jié)點(diǎn)不連續(xù)，會(huì)分散圖節(jié)點(diǎn)的其他鄰居，降低局部性。

中 科 技 大 學(xué) 碩 士 學(xué) 位 用戶，網(wǎng)絡(luò)中的邊表示 Facebook 用戶之間的友誼etworkX 中的繪圖工具對(duì) Ego-Facebook 進(jìn)行可gold[33]力導(dǎo)向算法定位節(jié)點(diǎn)的布局方式 spring_la色部分表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，灰色部分表示網(wǎng)絡(luò)中多個(gè)社區(qū)，社區(qū)內(nèi)連接緊密，社區(qū)間連接微弱，區(qū)連接成了一個(gè)更大的組件，這和 Kang 描述的交網(wǎng)絡(luò)圖中社區(qū)內(nèi)的邊位于圖鄰接矩陣對(duì)角區(qū)域部性，社區(qū)內(nèi)聯(lián)系越緊密，圖鄰接矩陣對(duì)角區(qū)域數(shù)樞紐節(jié)點(diǎn)具有多數(shù)邊，這些邊位于圖鄰接矩陣部性。

【參考文獻(xiàn)】：
期刊論文
[1]圖數(shù)據(jù)表示與壓縮技術(shù)綜述[J]. 張宇,劉燕兵,熊剛,賈焰,劉萍,郭莉.  軟件學(xué)報(bào). 2014(09)
[2]在線社交網(wǎng)絡(luò)影響力分析[J]. 吳信東,李毅,李磊.  計(jì)算機(jī)學(xué)報(bào). 2014(04)



本文編號(hào)：3454448