【摘要】：迅猛發(fā)展的網(wǎng)絡(luò)科學(xué)為人們分析和研究復(fù)雜系統(tǒng)提供了重要工具,已經(jīng)成為一個(gè)跨學(xué)科的研究平臺。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)與系統(tǒng)的功能與動力學(xué)特性緊密相關(guān),是對網(wǎng)絡(luò)進(jìn)行分析研究的重要切入點(diǎn)和研究對象。對社團(tuán)劃分算法的研究經(jīng)歷了十余年的發(fā)展,盡管取得了許多研究成果,但對其實(shí)際應(yīng)用的研究仍存在一定缺陷,主要體現(xiàn)在以下兩個(gè)方面:1)缺乏對算法實(shí)際應(yīng)用效率的評價(jià)方法。對算法進(jìn)行性能評價(jià)時(shí)往往采用多次實(shí)驗(yàn)取平均值的方法,平均值雖能體現(xiàn)算法的平均性能,但無法體現(xiàn)算法在實(shí)際應(yīng)用中的效率;2)社團(tuán)劃分算法的結(jié)果帶有隨機(jī)性,多次實(shí)驗(yàn)得到的多個(gè)結(jié)果之間存在差異性,如何從帶有差異性的多個(gè)結(jié)果中找到準(zhǔn)確、合理的劃分結(jié)果,以便進(jìn)行后續(xù)研究工作,依然缺乏一種合理的解釋和快速有效的算法。圍繞這些問題,本文依據(jù)算法在實(shí)際應(yīng)用中的情況提出了新的評價(jià)指標(biāo),提出了實(shí)際應(yīng)用效率更高的社團(tuán)劃分算法,分析了社團(tuán)劃分結(jié)果差異性的成因,提出了從多個(gè)劃分結(jié)果中找到準(zhǔn)確、合理的劃分結(jié)果的算法。本文的主要研究成果和學(xué)術(shù)貢獻(xiàn)如下:1)提出了基于小概率事件原理的自適應(yīng)隨機(jī)鄰居Louvain算法。本文以經(jīng)典Louvain算法為基礎(chǔ),借鑒隨機(jī)鄰居Louvain算法降低模塊度增益計(jì)算次數(shù)的改進(jìn)思想,提出了基于小概率事件原理的自適應(yīng)隨機(jī)鄰居Louvain算法。算法隨機(jī)抽取部分鄰居節(jié)點(diǎn)計(jì)算模塊度增益,從而降低模塊度增益計(jì)算次數(shù),提高運(yùn)算速度;鄰居節(jié)點(diǎn)抽取數(shù)量通過小概率事件原理推導(dǎo)獲得。算法從劃分的中間結(jié)果中獲取網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)信息,對計(jì)算所使用的物理量進(jìn)行估計(jì)。利用LFR人工基準(zhǔn)圖和實(shí)證網(wǎng)絡(luò)對該算法進(jìn)行測試,并與經(jīng)典Louvain算法和隨機(jī)鄰居Louvain算法進(jìn)行對比,發(fā)現(xiàn)本文所提算法可以在保證劃分結(jié)果的模塊度的大小和穩(wěn)定的同時(shí),有效提高算法的運(yùn)行速度,在110萬節(jié)點(diǎn)的Youtube網(wǎng)絡(luò)上提速比例超過 100%。2)提出了等效運(yùn)算時(shí)間指標(biāo)�；谏鐖F(tuán)劃分算法在實(shí)際應(yīng)用中的情況,本文提出了等效運(yùn)算時(shí)間指標(biāo),作為評價(jià)社團(tuán)劃分算法實(shí)際應(yīng)用效率的標(biāo)準(zhǔn)。利用該指標(biāo)對自適應(yīng)隨機(jī)鄰居Louvain算法進(jìn)行了測試,該算法可以有效提高實(shí)際應(yīng)用效率,在多數(shù)網(wǎng)絡(luò)中具有最佳的表現(xiàn),在實(shí)證網(wǎng)絡(luò)中,與經(jīng)典Louvain算法相比,本文算法的提速比例最高可達(dá)4倍以上。3)提出了帶噪聲的社團(tuán)結(jié)構(gòu)模型。針對社團(tuán)劃分算法結(jié)果不穩(wěn)定的問題,本文提出了帶噪聲的社團(tuán)結(jié)構(gòu)模型,將網(wǎng)絡(luò)中的連邊分為信息邊和噪聲邊,指出信息邊可以幫助社團(tuán)劃分算法找到網(wǎng)絡(luò)中的真實(shí)社團(tuán)結(jié)構(gòu),而噪聲邊會對社團(tuán)劃分算法產(chǎn)生干擾,使其無法準(zhǔn)確、穩(wěn)定地找到網(wǎng)絡(luò)中的真實(shí)社團(tuán)結(jié)構(gòu)。4)提出了利用社團(tuán)劃分的網(wǎng)絡(luò)去噪算法。依據(jù)帶噪聲的社團(tuán)結(jié)構(gòu)模型,本文提出了一種網(wǎng)絡(luò)去噪算法。算法利用一組社團(tuán)劃分結(jié)果,通過統(tǒng)計(jì)連邊兩端點(diǎn)的同社團(tuán)關(guān)系出現(xiàn)概率,對連邊的權(quán)值進(jìn)行計(jì)算、更新,對網(wǎng)絡(luò)中的信息邊和噪聲邊進(jìn)行區(qū)分,并對噪聲邊進(jìn)行濾除,從而得到僅包含有信息邊的網(wǎng)絡(luò)結(jié)構(gòu)。通過將去噪算法與自適應(yīng)隨機(jī)鄰居Louvain算法進(jìn)行結(jié)合,在LFR人工基準(zhǔn)圖和實(shí)證網(wǎng)絡(luò)上進(jìn)行驗(yàn)證,結(jié)果表明本文所提去噪算法可以有效提高劃分結(jié)果的準(zhǔn)確性。與共識算法進(jìn)行對比,去噪算法不僅可使劃分結(jié)果的準(zhǔn)確度有所提升,算法的運(yùn)算時(shí)間也顯著降低,時(shí)間復(fù)雜度僅為O(m),顯著低于共識算法的時(shí)間復(fù)雜度O(n~2)。
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【參考文獻(xiàn)】

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

1 陳趣;時(shí)變復(fù)雜系統(tǒng)的Gibrat漲落與最優(yōu)導(dǎo)航研究[D];華東師范大學(xué);2016年

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

1 王元欣;復(fù)雜網(wǎng)絡(luò)中重疊模塊發(fā)現(xiàn)及噪聲處理研究[D];山東師范大學(xué);2016年

2 韓路;基于核心圖的標(biāo)簽傳播社團(tuán)劃分算法[D];南京信息工程大學(xué);2015年

3 董哲;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法研究[D];解放軍信息工程大學(xué);2014年

本文編號：2782781