[發明專利]一種針對復雜網絡的混合型聚類方法

有效

• 申請號: 201210185427.4
• 申請日: 2012-06-06
• 公開（公告）號: CN102810113A
• 公開（公告）日: 2012-12-05
• 發明（設計）人: 童超;韓軍威;牛建偉;戴彬
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

1.一種針對復雜網絡的混合型聚類方法，其特征在于，該方法包括如下步驟：

步驟1：構建整個網絡的無向圖，統計整個網絡中的所有節點和邊，為每個節點順序編號，設節點總數為N，i為節點的編號，1≤i≤N；標記節點i和節點j之間的邊為e_ij，1≤i≤N，1≤j≤N，i≠j；

步驟2：初始將網絡中的所有節點劃分到一個社區中；

步驟3：確定網絡中的每條邊e_ij的連接聚類系數EdgeClusteringCoefficient：

EdgeClusteringCoefficient(eij)=Traid+1min(srcdeg-1,destdeg-1)]]>

其中，Traid表示是節點i和節點j共同的鄰居節點的個數，srcdeg表示節點i的度，destdeg表示節點j的度，min()表示取較小值；

步驟4：找到當前連接聚類系數值最大的邊，標記為e_AB，連接邊e_AB的節點為A和B，刪除連接聚類系數值最大的那條邊e_AB，判斷節點A和節點B之間是否存在連通的路徑，若不存在，更新網絡中的社區，然后執行下一步驟；若存在，轉步驟3執行；更新網絡中的社區，具體是：標記節點A和節點B在未更新社區前都屬于社區s，s代表網絡中第s個社區，將社區s中能連通節點A的節點劃分到一個社區s_A，將社區s中能連通節點B的節點劃分到一個社區s_B，然后更新社區的總數k＝k+1，將社區s_A記為第s個社區，社區s_B記為第k個社區；

步驟5：獲取當前網絡中的社區，并確定當前網絡所劃分的社區的模塊性評價指標值CurQ：

CurQ=AVEsk{Cs2ms+cs+cs2(m-ms)-cs}]]>

其中，AVE為平均數，s代表網絡中第s個社區，k代表網絡中社區的總數，c_s代表在步驟1的網絡中社區s與其他社區之間連接的邊的數量，m_s代表社區s內的邊的數量，m代表整個網絡的邊數；設置變量BestQ表示到目前為止最好的社區劃分所對應的模塊性評價指標值，初始賦值為0；設置變量steps用于標記當前迭代次數與BestQ所對應的迭代次數的差值，初始值為0；

判斷CurQ與BestQ的大小：如果BestQ<=CurQ，令BestQ=CurQ，保存當前所劃分的社區結構，更新迭代次數steps=0，轉步驟3執行；如果BestQ>CurQ，更新迭代次數steps=steps+1，并判斷steps是否小于用戶設定的閾值threshold，若否，轉步驟3執行，若是，執行步驟6；

步驟6：列舉網絡中當前存在的所有社區的兩兩組合，每個組合中不是相同的社區，針對每個組合，確定合并該組合中的兩個社區i和j后，確定網絡所劃分的社區的模塊性評價指標值Q_ij：

Qij=Σs=1k[msm-(ds2m)2]]]>

其中，d_s表示社區s中節點度之和；找到計算得到最大的Q_ij：max(Q_ij)，將最大Q_ij對應的兩個社區合并，然后執行步驟7；

步驟7：令變量CurQ=max(Q_ij)；判斷CurQ與BestQ的大小，如果BestQ<=CurQ，更新變量BestQ=CurQ，保存當前網絡中的社區結構，然后執行步驟8；如果BestQ>CurQ，直接執行步驟8；

步驟8：判斷當前網絡是否已經組合為一個社區，若是，執行步驟9，若否，轉步驟6執行；

步驟9：將最終保存的社區結構輸出。