基于密度和進化的社區(qū)結構檢測方法.pdf

1、近年來網(wǎng)絡社區(qū)結構檢測受到越來越多的關注。社區(qū)結構是復雜網(wǎng)絡的一個重要屬性。網(wǎng)絡社區(qū)結構就是網(wǎng)絡中某些特定節(jié)點的子集,其內部節(jié)點之間的聯(lián)系比較緊密,而和網(wǎng)絡中其它節(jié)點的聯(lián)系相對稀疏。網(wǎng)絡社區(qū)結構分析對于理解網(wǎng)絡子結構的功能、發(fā)現(xiàn)網(wǎng)絡中的隱藏規(guī)律以及預測網(wǎng)絡的行為不僅有十分重要的理論意義,而且有廣泛的應用前景。
　　基于密度的方法在社區(qū)結構檢測領域的研究熱度越來越高。這類方法依賴于兩個參數(shù),因此對輸入的參數(shù)極為敏感,導致難以選擇合適

2、的全局參數(shù)。正因為這些參數(shù)非常敏感而且具有全局作用,我們并沒有采用常規(guī)的選擇參數(shù)的做法,而是利用了參數(shù)的上述特性,提出了一種全新的從社區(qū)層面對網(wǎng)絡結構進行深入分析的思路,同時提出了一種啟發(fā)式的基于密度的社區(qū)結構檢測方法。在所提出的方法中,首先,利用參數(shù)的閾值作用本質,找出所有可能的輸入?yún)?shù)情況。這些參數(shù)按照經(jīng)典方法將產(chǎn)生多種多樣的網(wǎng)絡結構劃分。其次,我們提出了包括劃分、融合、分解、重組的策略對這些劃分進行社區(qū)層面的處理。尤其在重組步驟中

3、,我們用到了進化算法的思想,利用模塊度搜索出了最好的結果。當這些策略處理完畢之后,我們將可以獲得一個高質量的社區(qū)劃分。在虛擬網(wǎng)絡和實際網(wǎng)絡上的實驗證明了我們方法的有效性。
　　網(wǎng)絡的動態(tài)特征是另一個持續(xù)受到關注的網(wǎng)絡屬性?，F(xiàn)實世界中的網(wǎng)絡多數(shù)都是動態(tài)網(wǎng)絡,動態(tài)網(wǎng)絡的社區(qū)結構會隨著時間不斷演化,因此它比靜態(tài)網(wǎng)絡社區(qū)檢測更富有挑戰(zhàn)性。在動態(tài)網(wǎng)絡中,我們仍然需要考慮每個時間點的靜態(tài)網(wǎng)絡劃分質量,同時也要兼顧各時間點之間的動態(tài)聯(lián)系。在時間

4、光滑的假設下,這種動態(tài)聯(lián)系被數(shù)學化為相鄰兩時間節(jié)點間結構的相似性,與多目標進化算法的框架不謀而合。在先前的工作中,一種基于分解的多目標社區(qū)結構檢測進化算法已經(jīng)被提出。在此基礎上,為了進一步提高算法性能,我們試驗了一種局部搜索策略。這種局部搜索策略利用標簽傳播的思想,對每個時間點的結構都起著微調的作用。在動態(tài)網(wǎng)絡上進行的一系列實驗體現(xiàn)了該局部算子對算法性能的提高。
　　總結本文貢獻如下:
　　(1)解決了基于密度的社區(qū)結構檢測

5、方法中參數(shù)的選擇問題。我們的方法不僅克服了參數(shù)敏感以及難以選擇的問題,而且找到了所有可能的參數(shù),以參數(shù)為工具,對網(wǎng)絡結構進行分析,最終結合進化算法,形成了一個完整的處理社區(qū)結構檢測問題的新方法,在與其他算法結果對比中占優(yōu)。
　　(2)在基于分解的多目標優(yōu)化算法的框架下,我們提高了其解決動態(tài)社區(qū)結構檢測的能力。在大量實驗的基礎上,基于標簽傳播思想的局部搜索策略確實提高了目標算法的性能,達到了預期效果,另外通過實驗,假設合理性與框架合