復雜網絡重疊社區(qū)結構發(fā)現(xiàn)的算法研究與實現(xiàn).pdf

1、復雜網絡可以用來描述交通網、互聯(lián)網、社交關系網絡、神經網絡以及科研合作網絡等現(xiàn)實網絡。隨著對復雜網絡研究的深入，研究者們發(fā)現(xiàn)社區(qū)結構存在于很多的現(xiàn)實網絡中，并且現(xiàn)實生活中很多社區(qū)之間存在相互關聯(lián)和彼此重疊?；诖宋覀冎饕獙碗s網絡中社區(qū)的發(fā)現(xiàn)及劃分進行研究。
　　復雜網絡是由節(jié)點和邊構成，網絡中的節(jié)點代表不同實體，可以同時屬于多個社區(qū)；邊表示實體之間的某種關系。在劃分社區(qū)時可根據節(jié)點鄰居屬性劃分其所屬社區(qū)，本文基于節(jié)點鄰居的多樣性

2、及節(jié)點選取的隨機性主要做了以下工作：
　　1）提出復雜網絡重疊社區(qū)結構劃分的個體從眾演化算法 ICEA（Individual Conformity Evolutionary Algorithm）。算法根據社區(qū)節(jié)點的從眾和變異屬性，使得在劃分社區(qū)時根據節(jié)點的鄰居不同從而產生不同的社區(qū)劃分結果，通過比較模塊度找到比較好的社區(qū)劃分，在社區(qū)結構確定的基礎上我們使用陳俊宇等人的鄰居投票機制LM-NV（Louvain Method with

3、Neighbor Voting）對社區(qū)的邊界節(jié)點進行判斷，判斷其是否為重疊節(jié)點，從而完成復雜網絡重疊社區(qū)的劃分工作。
　　2）提出一種基因片段覆蓋算法GFCA（Gene Fragment Covering Algorithm），基本思想是將由節(jié)點鄰居組成的個體，隨機選取其它個體的一個基因片段覆蓋到當前個體的相應位置上，若覆蓋后，模塊度有改善，則選擇覆蓋后的個體作為當前個體；否則保留原來的個體。在真實網絡上進行實驗，結果表明此算法具

4、有一定的優(yōu)勢及實際可用性。
　　為了驗證所提算法ICEA和GFCA社區(qū)劃分的有效性，我們選取常用于測試復雜網絡劃分算法的三個真實數(shù)據集Zachary Karate club、Dolphin Social network以及American College football對兩個算法進行了測試，并將我們的算法與Newman的GN算法和快速算法FN、基于改進的K-means模糊聚類的網絡社區(qū)結構劃分算法NKFCM以及基于粒子群算法的模