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

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

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

【參考文獻(xiàn)】

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

1 張賢坤;田雪;費(fèi)松;宋琛;熬陽(yáng)月;;一種基于局部回路的標(biāo)簽傳播改進(jìn)算法[J];計(jì)算機(jī)應(yīng)用與軟件;2015年09期

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

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

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

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

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

7 淦文燕;赫南;李德毅;王建民;;一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J];軟件學(xué)報(bào);2009年08期

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

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

本文編號(hào)：2635519