【摘要】：圖聚集技術(shù)將原圖中的頂點(diǎn)和邊集合抽象到一個(gè)更高的層次,從而獲得一個(gè)可以代表原圖的簡(jiǎn)潔超圖。相對(duì)于原圖,它能有效的節(jié)省存儲(chǔ)空間、解決社交網(wǎng)絡(luò)中的隱私保護(hù)以及實(shí)現(xiàn)模糊查詢等問(wèn)題。而現(xiàn)有的圖聚集算法是假設(shè)整個(gè)圖結(jié)構(gòu)數(shù)據(jù)能夠一次性全部加載到的內(nèi)存的,而對(duì)于無(wú)法一次性完整加載到內(nèi)存的大規(guī)模圖數(shù)據(jù)是無(wú)法處理的。隨著真實(shí)世界的實(shí)體擴(kuò)張和關(guān)系的復(fù)雜,圖數(shù)據(jù)急劇增長(zhǎng),這樣的規(guī)模巨大其結(jié)構(gòu)復(fù)雜的大圖越來(lái)越多,為圖挖掘工作帶來(lái)了巨大的挑戰(zhàn)。同樣,傳統(tǒng)的圖聚集算法也不適用有限內(nèi)存下大圖聚集。目前比較方便的解決方式是利用分布式圖計(jì)算系統(tǒng),例如如基于Spark框架的大規(guī)模的圖計(jì)算引擎GraphX,基于BSP框架(Bulk Synchronous Parallel),即整體同步并行模型的Pregel圖計(jì)算系統(tǒng),都是專門用來(lái)處理和優(yōu)化各類復(fù)雜的圖計(jì)算任務(wù),但其在成本花費(fèi)的控制、安全性、算法調(diào)試和管理方面都是比較難。針對(duì)這種問(wèn)題,學(xué)術(shù)界提出基于單機(jī)上的圖計(jì)算平臺(tái),例如GraphChi、TurboGraph等圖計(jì)算平臺(tái)。相對(duì)于分布式圖計(jì)算系統(tǒng),基于單機(jī)的圖計(jì)算平臺(tái)不但在圖計(jì)算效率上達(dá)到合理期望,其適用性更強(qiáng)。本文首先分析了圖聚集和圖聚類的區(qū)別和聯(lián)系,幫助研究者深入了解圖聚集的概念。針對(duì)目前圖聚集算法迭代次數(shù)過(guò)多問(wèn)題,提出新的圖聚集算法,通過(guò)實(shí)驗(yàn)證明,該算法能有效時(shí)間內(nèi)處理基于內(nèi)存中的大圖。并在單機(jī)圖計(jì)算系統(tǒng)GraphChi上實(shí)現(xiàn)該算法,實(shí)現(xiàn)基于有限內(nèi)存的大圖聚集。
[Abstract]:The graph aggregation technique abstracts the set of vertices and edges in the original graph to a higher level, thus obtaining a simple hypergraph that can represent the original graph. Compared with the original image, it can save storage space effectively, solve privacy protection and fuzzy query in social network. The existing graph aggregation algorithm assumes that the whole graph structure data can be loaded into memory at one time, but the large scale graph data that can not be loaded into memory at one time can not be processed. With the expansion of entities and the complexity of relationships in the real world, the graph data increases rapidly, and more large graphs with such large scale and complex structure bring great challenges to graph mining work. Similarly, the traditional graph aggregation algorithm is not suitable for large graph aggregation in limited memory. At present, a more convenient solution is to use distributed graph computing systems, such as GraphX, a large-scale graph computing engine based on Spark framework, and Pregel graph computing system based on bulk synchronous parallel model. All of them are specially used to deal with and optimize all kinds of complex graph computing tasks, but it is difficult to control cost, security, algorithm debugging and management. In order to solve this problem, a graph computing platform based on a single computer is proposed, such as graph computing platform such as Graph Chii Turbo Graph. Compared with the distributed graph computing system, the graph computing platform based on single machine not only achieves reasonable expectation in graph computing efficiency, but also has stronger applicability. In this paper, the difference and relation between graph aggregation and graph clustering are analyzed, which helps researchers to understand the concept of graph aggregation. A new graph aggregation algorithm is proposed to solve the problem of too many iterations of graph aggregation algorithm. Experiments show that the algorithm can deal with large graph based on memory effectively in time. The algorithm is implemented on the single computer graph computing system GraphChi, and the large graph aggregation based on limited memory is realized.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

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

1 胡寶麗;游進(jìn)國(guó);周翠蓮;王洋;崔紅波;;一種有效的加權(quán)圖聚集算法[J];中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào);2016年03期

2 張宇;劉燕兵;熊剛;賈焰;劉萍;郭莉;;圖數(shù)據(jù)表示與壓縮技術(shù)綜述[J];軟件學(xué)報(bào);2014年09期

3 潘秋萍;游進(jìn)國(guó);張志朋;董朋志;胡寶麗;;圖聚集技術(shù)的現(xiàn)狀與挑戰(zhàn)[J];軟件學(xué)報(bào);2015年01期

4 溫菊屏;鐘勇;;圖聚類的算法及其在社會(huì)關(guān)系網(wǎng)絡(luò)中的應(yīng)用[J];計(jì)算機(jī)應(yīng)用與軟件;2012年02期

5 李川;趙磊;唐常杰;陳瑜;李靚;趙小明;劉小玲;;Graph OLAPing的建模、設(shè)計(jì)與實(shí)現(xiàn)[J];軟件學(xué)報(bào);2011年02期

相關(guān)碩士學(xué)位論文 前2條

1 潘秋萍;基于條件熵的圖聚集算法研究[D];昆明理工大學(xué);2014年

2 江楠;一種多數(shù)據(jù)流聚類異常檢測(cè)算法[D];哈爾濱工程大學(xué);2011年

，

本文編號(hào)：2119507