發(fā)布時間：2020-04-21 07:22

【摘要】：復雜網(wǎng)絡是計算機學界比較經(jīng)典的研究領域之一,研究者們將現(xiàn)實生活中的一些具體現(xiàn)象抽象為復雜網(wǎng)絡,通過復雜網(wǎng)絡的拓撲結構、節(jié)點或邊包含的隱式或者顯式的信息,來抽取出人們感興趣并且能為社會帶來巨大價值的信息。例如,通過人群接觸的復雜網(wǎng)絡確定某些傳染病的傳染源以及傳播勢頭,利用知識圖譜獲取某一學科的發(fā)展趨勢以及與其它學科的交叉情況等。在復雜網(wǎng)絡領域中,社區(qū)發(fā)現(xiàn)是目前最基礎、最廣泛的研究。社區(qū)發(fā)現(xiàn),是根據(jù)已有的知識將復雜網(wǎng)絡劃分為若干個子模塊,一個模塊成為一個社區(qū),里面包含一些關系密切的節(jié)點與連接邊。社區(qū)發(fā)現(xiàn)可以理解成一種基于復雜網(wǎng)絡的無監(jiān)督的聚類算法。隨著模塊度概念、譜聚類算法的提出,社區(qū)發(fā)現(xiàn)算法在21世紀初期迅猛發(fā)展,各種各樣的社區(qū)發(fā)現(xiàn)算法被提出并得到論證。優(yōu)秀的社區(qū)發(fā)現(xiàn)算法可以提高復雜網(wǎng)絡社區(qū)劃分的指標標準,從性能方面也可以提高發(fā)現(xiàn)效率,減少時間開銷。但是隨著大數(shù)據(jù)時代的降臨,復雜網(wǎng)絡的規(guī)模也是快速發(fā)展。在進行實際操作時,單機的計算能力無法滿足人們的需求,即使進一步優(yōu)化算法,在單機條件下也無法帶來質(zhì)的飛躍。因此,如果將計算交給大數(shù)據(jù)計算平臺,就可以滿足人們對規(guī)模巨大的復雜網(wǎng)絡進行高效計算的需求。大數(shù)據(jù)時代產(chǎn)生了許多大數(shù)據(jù)計算框架平臺,其中,Spark因為計算速度快,生態(tài)圈豐富,從而獲得了大數(shù)據(jù)業(yè)內(nèi)的廣泛認可。并且,Spark計算平臺擁有的相關圖計算組件GraphX,可以幫助實現(xiàn)算法同步化。基于上述知識,本文提出基于Spark的大規(guī)模復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法的研究與改進。本文首先對一個無權值的復雜網(wǎng)絡進行加權預處理;其次選取經(jīng)典的高效社區(qū)發(fā)現(xiàn)算法——標簽傳播算法,進行包括標簽初始化、標簽傳播和標簽更新策略、迭代收斂策略等多方面的優(yōu)化工作,進而建立一個新的社區(qū)發(fā)現(xiàn)算法模型;然后,將算法接入Spark,通過GraphX編程實現(xiàn)算法同步化,并建立Spark實驗平臺;最后,通過經(jīng)典的復雜網(wǎng)絡數(shù)據(jù)和規(guī)模較大的復雜網(wǎng)絡數(shù)據(jù)進行實驗,與一些經(jīng)典的社區(qū)發(fā)現(xiàn)算法進行對比,驗證提出的算法是否有效,并且通過大規(guī)模復雜網(wǎng)絡數(shù)據(jù)集來驗證基于Spark GraphX平臺確實大幅度提高了在復雜網(wǎng)絡中進行社區(qū)發(fā)現(xiàn)的計算性能。
【圖文】：

第一章 引言第一章 引言 研究背景隨著信息科技的不斷發(fā)展和人工智能水平的提高，人類進入了一個萬物代，尤其近 5 年以來，物聯(lián)網(wǎng)、車聯(lián)網(wǎng)等詞匯越來越多的出現(xiàn)在我們的這些先進的概念都可以抽象成復雜網(wǎng)絡�！拔铩迸c“車”相當于復雜網(wǎng)點，而節(jié)點之間的聯(lián)系（比如設備之間的物理連線，，車與車之間的信息交看做復雜網(wǎng)絡中兩個節(jié)點之間的連線。不僅如此，世界本身就可以看做的復雜網(wǎng)絡，它由許多節(jié)點（實體）和邊（實體之間實際或者抽象的關，而我們就生活在這個巨大的復雜網(wǎng)絡之中。

圖 1.2 社交網(wǎng)絡示例 圖 1.3 知識圖譜示例發(fā)現(xiàn)復雜網(wǎng)絡中的社區(qū)需要用到社區(qū)發(fā)現(xiàn)算法。社區(qū)發(fā)現(xiàn)算法是一種無監(jiān)督學習算法，其目的是聚合在復雜網(wǎng)絡中相似的節(jié)點。除了理論研究價值之外，該算法在現(xiàn)實生活中同樣有著重要的意義：在社交網(wǎng)絡中，通過社區(qū)發(fā)現(xiàn)可以發(fā)現(xiàn)關聯(lián)性強的群體，可以對群體進行組推薦；在電話網(wǎng)絡中，公安機關通過社區(qū)發(fā)現(xiàn)可以劃分出聯(lián)系緊密的社會人群，在已知少數(shù)犯罪嫌疑人的情況下，可以根據(jù)他們所在的社區(qū)偵查出團伙，提高辦案效率；在突發(fā)傳染病的情況下，可以通過對人群進行社區(qū)劃分鎖定傳染病源出現(xiàn)的社區(qū)，確定高危人群，利于傳染病及時的防護與控制。目前，對于復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法的研究很多，很多學者對一些基礎算法做了足夠的改進，并且效果優(yōu)良。但是隨著社會的發(fā)展，科技的進步以及信息的不斷積累，各行各業(yè)的數(shù)據(jù)呈現(xiàn)迅速增長的趨勢，一些類復雜網(wǎng)絡結構的數(shù)據(jù)規(guī)模也越來越大，其拓撲結構也越來越復雜。以社交網(wǎng)絡為例，由于 2010 年后智能
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5

【參考文獻】

相關期刊論文 前9條

1 張賢坤;田雪;費松;宋琛;熬陽月;;一種基于局部回路的標簽傳播改進算法[J];計算機應用與軟件;2015年09期

2 于海;趙玉麗;崔坤;朱志良;;一種基于交叉熵的社區(qū)發(fā)現(xiàn)算法[J];計算機學報;2015年08期

3 辛宇;楊靜;謝志強;;基于隨機游走的語義重疊社區(qū)發(fā)現(xiàn)算法[J];計算機研究與發(fā)展;2015年02期

4 石夢雨;周勇;邢艷;;基于LeaderRank的標簽傳播社區(qū)發(fā)現(xiàn)算法[J];計算機應用;2015年02期

5 索勃;李戰(zhàn)懷;陳群;王忠;;基于信息流動分析的動態(tài)社區(qū)發(fā)現(xiàn)方法[J];軟件學報;2014年03期

6 王剛;鐘國祥;;基于信息熵的社區(qū)發(fā)現(xiàn)算法研究[J];計算機科學;2011年02期

7 淦文燕;赫南;李德毅;王建民;;一種基于拓撲勢的網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[J];軟件學報;2009年08期

8 沈華偉;程學旗;陳海強;劉悅;;基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J];計算機學報;2008年04期

9 段曉東;王存睿;劉向東;林延平;;基于粒子群算法的Web社區(qū)發(fā)現(xiàn)[J];計算機科學;2008年03期

本文編號：2635519