發(fā)布時間：2020-05-20 11:51

【摘要】：近年來,隨著信息技術的快速發(fā)展,各個行業(yè)都形成了自身的海量數(shù)據(jù),在電信行業(yè)形成的海量通話數(shù)據(jù)、生物化學中分子之間的關系數(shù)據(jù)、交通網(wǎng)路的架構信息以及社交網(wǎng)絡中形成的數(shù)據(jù)信息。如何充分的挖掘這些數(shù)據(jù)的潛在價值是目前學術界和工業(yè)界探討的熱點問題。對于這些數(shù)據(jù)形成的巨大的復雜網(wǎng)絡系統(tǒng),可以用圖結構清晰地表示,而對圖中的數(shù)據(jù)進行聚類操作是挖掘圖數(shù)據(jù)信息的一個基本工具。然而,現(xiàn)實中的數(shù)據(jù)總是在不斷地動態(tài)更新,傳統(tǒng)的基于圖結構的聚類算法SCAN(A Structural Clustering Algorithm for Networks)并不能有效地處理和維護實時更新的數(shù)據(jù)信息。因此本文提出了一種基于廣度優(yōu)先樹BFS-tree(Breadth First Search-tree)的增量圖結構聚類算法ISCAN(Incremental Structural Clustering for Dynamic Networks)。當數(shù)據(jù)更新時,利用該算法無需重新計算整個圖,只需更新少量的邊,通過廣度優(yōu)先樹的斷裂以及合并來維護已有的聚類結果。此外,為了減少在計算圖中頂點之間相似性所消耗的時間,本文提出了如何利用多核進行結構相似性的計算,并且提出了兩種有效的負載均衡策略。傳統(tǒng)的結構聚類算法,對給定的閾值參數(shù)非常的敏感,細微的變化都會對聚類結果產(chǎn)生較大的影響,本文提出了一種基于三角形的結構聚類模型,相對于傳統(tǒng)的結構聚類算法,不僅能夠降低聚類結果對參數(shù)的敏感性,而且能夠得到更加緊密的社區(qū)。最后,以現(xiàn)實世界中形成的量圖數(shù)據(jù)為依據(jù)做了大量的對比試驗。實驗結果證明了提出的增量圖結構聚類算法和并行計算結構相似性的有效性、正確性,以此同時,通過實驗發(fā)現(xiàn),我們提出的基于三角形的結構聚類,不僅能夠得到更加緊密的社區(qū),而且當閾值發(fā)生改變時,聚類的結構更加的穩(wěn)定。
【圖文】：

22圖 3.6 不同負載均衡策略的運行效率對比觀察圖 3.6，發(fā)現(xiàn)隨著 CPU 核心數(shù)的線性升高，系統(tǒng)的運行時間幾乎是線性降低的；，根據(jù)實驗結果，，可以發(fā)現(xiàn)基于切片的負載均衡策略的運行效率普遍高于基于邊度行效率。這是由于計算有邊頂點之間的結構相似性的過程中，當且僅當在完全理想下時間復雜度是: d(u) d(v)，但是，由于硬件因素以及算法運行過程中的線程的同步問題，從而造成一些誤差，使得程序不能達到完全理想的理論運行時間。但

構聚類處理動態(tài)更新的數(shù)據(jù)。接下來，將在具體的實驗結果中分析傳統(tǒng)的結構聚類模型和本文提出的基于三角形的圖結構聚類模型的效果，更具實驗結果對數(shù)據(jù)集中的部分聚類結果進行對比分析。具體如下圖所示。(a)SCAN( 2, 0 4) (b)TSCAN( 2, 0 4)
【學位授予單位】：深圳大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP311.13

【參考文獻】

相關期刊論文 前3條

1 李桃陶;周斌;王忠振;;基于社交網(wǎng)絡的圖數(shù)據(jù)挖掘應用研究[J];計算機技術與發(fā)展;2014年10期

2 丁悅;張陽;李戰(zhàn)懷;王勇;;圖數(shù)據(jù)挖掘技術的研究與進展[J];計算機應用;2012年01期

3 王建新;蔡釗;李敏;;一種基于極大團的蛋白質相互作用預測方法[J];高技術通訊;2009年01期

本文編號：2672581