本文關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)方法研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社團(tuán)結(jié)構(gòu) 社團(tuán)檢測(cè) 網(wǎng)絡(luò)稀疏化 主動(dòng)學(xué)習(xí)

【摘要】：現(xiàn)實(shí)世界中眾多的復(fù)雜系統(tǒng)都可抽象地表示為復(fù)雜網(wǎng)絡(luò),而社團(tuán)結(jié)構(gòu)是很多復(fù)雜網(wǎng)絡(luò)最為顯著的結(jié)構(gòu)特征,其中的社團(tuán)往往對(duì)應(yīng)于網(wǎng)絡(luò)的功能單元,從某種程度而言,整個(gè)網(wǎng)絡(luò)的功能往往取決于社團(tuán)之間的相互作用。通過檢測(cè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu),可以在中觀(mesoscale)結(jié)構(gòu)層面探索網(wǎng)絡(luò)的性質(zhì),研究網(wǎng)絡(luò)的結(jié)構(gòu)與功能之間的關(guān)系。此外,社團(tuán)結(jié)構(gòu)也能對(duì)網(wǎng)絡(luò)的動(dòng)力學(xué)特性產(chǎn)生重要的影響。因此,社團(tuán)檢測(cè)的研究不僅具有重要的理論意義,而且具有重要的實(shí)際應(yīng)用價(jià)值,近年來吸引了計(jì)算機(jī)、物理、生物等多個(gè)學(xué)科研究人員的廣泛關(guān)注,已成為復(fù)雜網(wǎng)絡(luò)學(xué)科的一個(gè)研究熱點(diǎn)。本文對(duì)已有的社團(tuán)檢測(cè)方法進(jìn)行了深入的分析,針對(duì)這些方法中存在的問題與不足,提出了兩類共5種社團(tuán)檢測(cè)方法。第一類方法關(guān)注的是如何從網(wǎng)絡(luò)中檢測(cè)得到盡可能精確的、高質(zhì)量的社團(tuán)結(jié)構(gòu),其中包括三種社團(tuán)檢測(cè)方法:(1)DBSCD:該方法首先利用一個(gè)稀疏化處理過程,從網(wǎng)絡(luò)中移除可能位于不同社團(tuán)之間的一些邊,使得社團(tuán)之間的邊界變得清晰;接著使用譜二分法,基于網(wǎng)絡(luò)轉(zhuǎn)移矩陣第二特征向量中元素的符號(hào),將網(wǎng)絡(luò)分裂為兩個(gè)子網(wǎng)絡(luò);然后在模塊度的約束、指導(dǎo)下,以迭代方式使用同樣的譜二分法對(duì)選中的子網(wǎng)絡(luò)進(jìn)行分裂,每一次迭代選中的都是其分裂能使得模塊度增量最大的一個(gè)子網(wǎng)絡(luò)。通過這樣的持續(xù)分裂,得到最終的社團(tuán)結(jié)構(gòu)。(2)HBSCD:該方法同樣先對(duì)網(wǎng)絡(luò)進(jìn)行稀疏化處理,使社團(tuán)結(jié)構(gòu)更加突出。接著基于網(wǎng)絡(luò)轉(zhuǎn)移矩陣第二特征向量中元素的符號(hào),持續(xù)將網(wǎng)絡(luò)分裂為一系列不可再分的子網(wǎng)絡(luò),并將每一個(gè)子網(wǎng)絡(luò)當(dāng)做一個(gè)社團(tuán),形成初始的社團(tuán)結(jié)構(gòu)。然后借鑒Fast算法的思想,通過合并其中一些社團(tuán)得到最終的社團(tuán)結(jié)構(gòu)。(3)ASSCD:該方法將主動(dòng)學(xué)習(xí)技術(shù)引入到社團(tuán)檢測(cè)的研究中,并與半監(jiān)督社團(tuán)檢測(cè)算法結(jié)合,從網(wǎng)絡(luò)中提取其社團(tuán)結(jié)構(gòu)。主動(dòng)學(xué)習(xí)策略從網(wǎng)絡(luò)中主動(dòng)選取對(duì)半監(jiān)督社團(tuán)檢測(cè)算法效用最大的頂點(diǎn),生成高質(zhì)量的Must-Link和Cannot-Link成對(duì)約束的半監(jiān)督成分;半監(jiān)督社團(tuán)檢測(cè)算法首先利用這些半監(jiān)督成分構(gòu)建初始的社團(tuán)結(jié)構(gòu)框架,然后充分利用它們以貪心方式對(duì)每一社團(tuán)進(jìn)行擴(kuò)張,得到最終的社團(tuán)結(jié)構(gòu)。為了測(cè)試、驗(yàn)證這三種方法的性能,本文分別在一些實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證實(shí),這三種方法均具有較強(qiáng)的社團(tuán)檢測(cè)能力,得到的社團(tuán)結(jié)構(gòu)質(zhì)量明顯優(yōu)于對(duì)比方法。第二類方法的目標(biāo)是從網(wǎng)絡(luò)中高效地獲取基本合理的、確定的社團(tuán)結(jié)構(gòu),以克服一些運(yùn)行效率較高的社團(tuán)檢測(cè)方法得到的結(jié)果具有不確定性的缺陷,并增強(qiáng)社團(tuán)檢測(cè)方法的泛化能力,方便對(duì)未知的新網(wǎng)絡(luò)快速地進(jìn)行探索性挖掘。主要包括兩種社團(tuán)檢測(cè)方法:(1)VSAHCD:該方法受人類社交活動(dòng)中選舉投票行為的啟發(fā),首先通過模擬投票過程,讓每個(gè)頂點(diǎn)按照一定的規(guī)則進(jìn)行投票,得到一系列的小團(tuán)體,然后分別使用兩種策略,將其中一些小團(tuán)體合并為較大的社團(tuán)。一種策略借鑒了Fast算法的思想,每次合并能使得模塊度增量最大并且相似性不為0的兩個(gè)社團(tuán);另一種策略則合并相似性最大的兩個(gè)社團(tuán),但確保合并操作能帶來正的模塊度增量。通過分別以這兩種方式對(duì)小團(tuán)體進(jìn)行合并,得到最終的社團(tuán)結(jié)構(gòu)。(2)LPAd:該算法是對(duì)LPA算法的一個(gè)改進(jìn)和增強(qiáng),首先確定了一個(gè)合理的頂點(diǎn)序列,按照該序列的順序,將其中每一頂點(diǎn)的標(biāo)簽更新為其鄰居中最頻繁出現(xiàn)的一個(gè)標(biāo)簽,同時(shí)也提出了存在標(biāo)簽競(jìng)爭時(shí)的解決方案。通過這兩方面的改進(jìn),使LPAd成為一個(gè)確定性的算法。然后在其運(yùn)行得到的社團(tuán)結(jié)構(gòu)基礎(chǔ)上,借鑒Fast算法的思想并結(jié)合相似性對(duì)其中一些社團(tuán)進(jìn)行合并,得到最終的社團(tuán)結(jié)構(gòu)。理論分析表明這兩種方法均具有較高的運(yùn)行效率。此外,本文也通過在5個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集和2個(gè)LFR人工合成網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn),分別對(duì)這兩種方法的性能進(jìn)行了測(cè)試和評(píng)估。評(píng)估結(jié)果表明,這兩種方法均能快速地從網(wǎng)絡(luò)中檢測(cè)得到比較合理的、確定的社團(tuán)結(jié)構(gòu)。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社團(tuán)結(jié)構(gòu) 社團(tuán)檢測(cè) 網(wǎng)絡(luò)稀疏化 主動(dòng)學(xué)習(xí)
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5;TP181
【目錄】：

• 中文摘要3-5
• Abstract5-16
• 第一章 緒論16-27
• 1.1 引言16-17
• 1.2 復(fù)雜網(wǎng)絡(luò)與鏈接挖掘17-23
• 1.2.1 復(fù)雜網(wǎng)絡(luò)研究的起源及發(fā)展17-19
• 1.2.2 常見的復(fù)雜網(wǎng)絡(luò)19-20
• 1.2.3 復(fù)雜網(wǎng)絡(luò)的特性20-22
• 1.2.4 鏈接挖掘的內(nèi)容、任務(wù)22-23
• 1.3 本論文的主要工作及貢獻(xiàn)23-25
• 1.4 本論文的組織結(jié)構(gòu)25-27
• 第二章 理論基礎(chǔ)與相關(guān)工作27-43
• 2.1 相關(guān)概念、術(shù)語、符號(hào)及定義27-29
• 2.2 社團(tuán)檢測(cè)的意義29-30
• 2.3 社團(tuán)檢測(cè)研究的相關(guān)工作30-39
• 2.4 本論文實(shí)驗(yàn)使用的網(wǎng)絡(luò)數(shù)據(jù)集39-40
• 2.5 社團(tuán)結(jié)構(gòu)的評(píng)價(jià)指標(biāo)40-43
• 第三章 DBSCD：分裂的譜二分層次社團(tuán)檢測(cè)方法43-65
• 3.1 引言43-44
• 3.2 動(dòng)因44-46
• 3.3 DBSCD方法46-54
• 3.3.1 網(wǎng)絡(luò)稀疏化算法46-47
• 3.3.2 迭代的譜二分社團(tuán)檢測(cè)算法47-51
• 3.3.3 實(shí)現(xiàn)策略51-54
• 3.4 實(shí)驗(yàn)及結(jié)果分析54-63
• 3.4.1 對(duì)比方法及參數(shù)設(shè)置54-55
• 3.4.2 實(shí)驗(yàn)結(jié)果55-63
• 3.5 小結(jié)63-65
• 第四章 HBSCD：混合的譜二分層次社團(tuán)檢測(cè)方法65-78
• 4.1 引言65-66
• 4.2 HBSCD方法66-69
• 4.3 實(shí)驗(yàn)及結(jié)果分析69-75
• 4.3.1 對(duì)比算法及參數(shù)設(shè)置69
• 4.3.2 實(shí)驗(yàn)結(jié)果69-75
• 4.4 小結(jié)75-78
• 第五章 ASSCD：基于主動(dòng)學(xué)習(xí)的半監(jiān)督社團(tuán)檢測(cè)方法78-101
• 5.1 引言78-80
• 5.2 ASSCD方法80-90
• 5.2.1 概念和定義80-81
• 5.2.2 半監(jiān)督社團(tuán)檢測(cè)算法81-83
• 5.2.3 基于主動(dòng)學(xué)習(xí)的半監(jiān)督成分獲取算法83-88
• 5.2.4 基于隨機(jī)游走的頂點(diǎn)相似性計(jì)算88-89
• 5.2.5 時(shí)間復(fù)雜度分析89-90
• 5.3 實(shí)驗(yàn)及結(jié)果分析90-100
• 5.3.1 參數(shù)設(shè)置90-91
• 5.3.2 實(shí)驗(yàn)方法及結(jié)果91-100
• 5.4 小結(jié)100-101
• 第六章 VSAHCD：模擬投票行為的凝聚層次社團(tuán)檢測(cè)方法101-122
• 6.1 引言101-102
• 6.2 思想啟發(fā)102-103
• 6.3 VSAHCD方法103-110
• 6.3.1 VSAHCD方法的總體框架103
• 6.3.2 投票過程103-106
• 6.3.3 社團(tuán)合并過程106-108
• 6.3.4 時(shí)間復(fù)雜度分析108-110
• 6.4 實(shí)驗(yàn)及結(jié)果分析110-121
• 6.4.1 評(píng)價(jià)標(biāo)準(zhǔn)的變更110-111
• 6.4.2 對(duì)比算法及設(shè)置111
• 6.4.3 實(shí)驗(yàn)結(jié)果及分析111-121
• 6.5 小結(jié)121-122
• 第七章 LPAd：一個(gè)確定性的LPA算法122-137
• 7.1 引言122-123
• 7.2 LPAd算法123-128
• 7.3 實(shí)驗(yàn)及結(jié)果分析128-136
• 7.3.1 對(duì)比算法及設(shè)置128
• 7.3.2 實(shí)驗(yàn)結(jié)果及分析128-136
• 7.4 小結(jié)136-137
• 第八章 總結(jié)與展望137-140
• 8.1 本文工作總結(jié)137-138
• 8.2 下一步需要開展的工作138-140
• 參考文獻(xiàn)140-152
• 在學(xué)期間的研究成果152-154
• 致謝154

，

本文編號(hào)：755915