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

有效

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

技術領域

本發明涉及一種復雜網絡中的社團探測方法，屬于網絡技術領域。?

背景技術

社交網絡、生物網絡等復雜網絡都是極具動態性的客體，他們能夠隨著時間的推移快速的成長和變化。這些網絡都可以劃分為多個社團。“社團”，也可以叫做“群”，是一組擁有相同的屬性或者在圖中扮演相似角色的節點的集合。復雜網絡社團探測就是找到復雜網絡中的節點屬于哪個社團，給節點分群。復雜網絡社團探測是了解復雜網絡拓撲結構，理解復雜網絡功能，發現隱藏模式，鏈路預測，進化檢測的關鍵。

比較流行的尋找社團結構的方法是由Newman等人提出的模塊化矩陣方法，這種方法是基于譜聚類的。事實證明，這種模塊化模型在知道網絡結構類型的情況下能夠分別通過最大特征值或者最小特征值發現unipartite網絡和bipartite網絡中的社團結構。Michael?J.Barber和一些學者也尋找到方法探測bipartite網絡中的社團。Barber和他的同事提出的BRIM算法能夠檢測出bipartite網絡中的社團數目。此外，Bareber和Clark使用標簽傳播算法(LPA)識別了社團結構。然而，這些方法在不知道網絡類型的情況下卻不奏效。?

在一些情況下，研究者們并不知道網絡的結構類型。例如，我們知道蛋白質網絡中節點的相互作用，但是我們卻不知道網絡的類型。再如，我們知道一個網絡由學校里的人際關系構成，網絡的類型卻不確定。因為如果連接只是存在于學生之間，那么這個網絡就是unipartite網絡，如果連接存在于學生和老師之間，那么這個網絡便是bipartite網絡。因此，需要有一個有效的同時適用于unipartite網絡和bipartite網絡的社團探測方法。?

發明內容

本發明的目的是提供一種復雜網絡中的社團探測方法，該方法不需要事先知道網絡是unipartite網絡還是bipartite網絡。?

本發明的目的是通過以下技術方案實現的：?

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

一、事先給定復雜網絡中的社團數目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_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值最大的方案，如果仍存在多個方案，則同時作為最終方案，從而得到對復雜網絡進行社團探測的最終結果。?

本發明在復雜網絡中進行社團探測的原理是：在不同類型的網絡結構中的邊以不同的方式連接，在相同的社團中的節點是相似的。所以本發明把注意力從邊上轉移到點上，從節點的角度進行社團探測。?

1、unipartite網絡?