[發明專利]一種復雜網絡中的社團探測方法

有效

• 申請號: 201210154812.2
• 申請日: 2012-05-17
• 公開（公告）號: CN102722530A
• 公開（公告）日: 2012-10-10
• 發明（設計）人: 李侃;龐垠
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種復雜網絡中的社團探測方法，包括以下步驟：

一、事先給定復雜網絡中的社團數目m；假定網絡中有n個節點，則初始時刻有n個社團，即網絡中每個節點就是一個社團；

二、把網絡中任意兩個社團合并，計算并用合并后的Q值減去合并前的Q值得到Q值的變化；

其中節點i和節點j是網絡中屬于同一社團的任意兩個節點；N_ij＝|Г_i∩Γ_j|且N_ii＝0，Γ_x表示網絡中節點x的鄰居，也就是那些通過一條邊跟節點x直接相連的節點的集合，|Γ_i∩Γ_j|表示節點i和節點j的共同鄰居節點的個數，也就是同時與節點i和節點j都有邊相連的節點的數目；R為網絡中的共同鄰居節點數目，其中節點a和節點b是網絡中的任意兩個節點；

定義鄰接矩陣A為對稱矩陣，如果有一條邊連接節點i和節點j，那么A_ij＝1，否則，A_ij＝0，定義a_i為矩陣A的第i個列向量即矩陣A的第i列，則矩陣A也可以寫作A＝[a₁，a₂，...，a_n]a_n]，當且僅當A_ikA_kj＝1時，節點k是節點i和節點j的共同鄰居，令a_i·a_i＝k_i，即節點i的度，共同鄰居指數c_x＝k_x(k_x-1)/2；

三、選擇使Q值的變化最大的合并方案進行合并，此時網絡中的社團數減一；如果使得Q值的變化最大的合并方案不是唯一的，那么分別按照這些方案進行合并，得到不同方案的合并結果；

四、重復步驟二，三，直到網絡中剩余社團數目為m時結束；如果出現了多個方案，那么比較這些方案的Q值，選擇Q值最大的方案，如果仍存在多個方案，則同時作為最終方案，從而得到對復雜網絡進行社團探測的最終結果。