符號網絡和異構網絡中的社區(qū)檢測方法.pdf

1、近年來,復雜網絡已經成為備受關注的研究領域,越來越多的研究人員投身于對復雜網絡的研究。研究發(fā)現(xiàn),很多復雜網絡都具有社區(qū)結構這一特性。所以,如何能有效地找到實際社會網絡中的社區(qū)結構,是近年來對復雜網絡研究的重點之一。其中,大部分現(xiàn)有的研究都是檢測傳統(tǒng)無符號、非異構網絡的社區(qū)結構方法,即網絡中邊的符號都為正,或網絡中的節(jié)點種類單一。而在真實社會網絡中,節(jié)點之間不僅有表示“友好、聯(lián)盟”等的正向關系,而且有表示“敵視、競爭”等的負向關系。這種網

2、絡中既存在正向關系又存在負向關系的網絡被稱為符號網絡(Signed networks, SNs)。除此之外,還存在多種類型節(jié)點的網絡,稱為異構網絡(Multi-dimensional networks,MDNs)。本論文主要研究符號網絡和異構網絡中的社區(qū)檢測問題。基于多目標進化算法( Multi-Objective Evolutionary Algorithm, MOEAs)、聚類算法(Cluster Algorithms, CAs)和

3、遺傳算法(Genetic Algorithms, GAs),提出了一種符號網絡的社區(qū)檢測方法和兩種異構網絡的社區(qū)檢測方法。下面是本論文的主要工作:
　　1.改進了原始的模塊度函數(Q),將其擴展為評價符號網絡社區(qū)結構質量的兩個指標Q+和Q-。改進后的Q+和Q-保留了原始Q函數的特性,能夠很好的應用于檢測符號網絡的社區(qū)結構?；赒+和Q-兩個目標,提出了基于多目標進化算法的符號網絡社區(qū)檢測方法(MOEA-SN)。實驗中采用了4個基準

4、符號網絡和隨機生成的符號網絡對MOEA-SN的性能進行了測試,結果表明MOEA-SN是一種有效的符號網絡社區(qū)檢測方法。
　　2.設計了一種基于聚類方法的異構網絡社區(qū)檢測方法(CA-MDN)。根據馬爾科夫隨機游走的模型計算網絡中節(jié)點之間的相似性,并以此計算社區(qū)間的相似性,作為聚類方法中的相似性度量,并使用了一種局部模塊度增量來確定聚合聚類的停止標準。實驗中,采用了1個真實社會網絡和隨機生成的異構網絡對CA-MDN的性能進行了測試,結

5、果表明CA-MDA是一種有效的異構社會網絡社區(qū)檢測方法。
　　3.提出了一種基于遺傳算法的異構網絡社區(qū)檢測方法(GA-MDN),改進了模塊密度函數D以用于衡量異構網絡的社區(qū)結構質量,并將其作為遺傳算法的適應度函數進行優(yōu)化;改進了一種帶局部搜索的變異算子,避免進化陷入局部最優(yōu),并提高了算法的效率。采用了1個真實社會網絡和隨機生成的異構網絡對GA-MDN進行了實驗分析,結果表明GA-MDN是一種有效的異構網絡社區(qū)檢測方法,能夠準確檢測