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

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

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

【學位級別】：碩士

【部分圖文】：

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

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

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

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



本文編號：3454448