[發明專利]基于振蕩器相位同步的網絡社區結構劃分方法

無效

• 申請號: 201110289983.1
• 申請日: 2011-09-27
• 公開（公告）號: CN102355393A
• 公開（公告）日: 2012-02-15
• 發明（設計）人: 吳建設;焦李成;靳超;尚榮華;戚玉濤;吳家驥;韓紅;白靜;王達
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/28
• 分類號: H04L12/28;G06F17/50
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

技術領域

本發明屬于計算機領域，更進一步涉及小世界網絡技術領域中基于振蕩器相位同步的網絡社區結構劃分方法。本發明通過引入包含正負耦合強度的Kuramoto模型，由振蕩器相位同步原理，提高了并行處理能力，可快速有效地進行小世界網絡中社區結構的劃分。

背景技術

小世界網絡是最典型的復雜網絡之一，即一個高度聚集的包含了“局部連接”節點的子網，連同一些有助于產生短路徑的長距離隨機連接。異構網絡中由不同性質、類型的節點組成的關系豐富的結構稱為“社區”(子網絡)。社區內關系稠密，而不同社區節點之間關系稀疏的結構-社區結構是復雜網絡的特征之一。對網絡中社區結構的劃分是復雜網絡中面臨的主要問題之一，人們也提出了很多方法來對網絡進行社區結構的劃分。

北京航空航天大學申請的專利“一種復雜網絡中的社區劃分方法”(專利申請號200810224175.5，公開號CN?101383748A)。該方法是以若干個不同的局部帶有影響力的節點為核心，并使節點的影響力從核心逐層向外均勻擴散，最終形成了以影響力最大的節點為核心，逐層擴展中節點的影響力不斷衰減，它們之間相互關聯形成一個局部區域，擴展到方法的停止，節點影響力很小，到達該局部區域的網絡邊緣。該方法存在不足之處是，對于給定的拓撲結構，要計算網絡中所有節點相互作用之后而產生的影響力疊加值，該計算過程過于復雜，需要較長的時間來對所有節點的相關值進行計算，并且要計算每一層擴展節點對上一層節點和對下一層節點連接的邊數的比值，最后還要保證網絡所有的節點都被擴展過，該方法迭代次數過多，降低了劃分效率，耗費時間長。

發明內容

本發明的目的在于克服現有技術的不足，提出一種基于振蕩器相位同步的網絡社區結構劃分方法，以實現小世界網絡中社區結構的快速有效地進行劃分。本發明使用加入正負耦合系數的Kuramoto模型，基于振蕩器相位同步原理，通過微分方程的并行處理方式使節點相位快速有效的同步，實現網絡社區的劃分。

本發明的具體步驟如下：

(1)繪制由若干個獨立環狀結構組成的網絡結構圖，以特定概率隨機連接環狀結構中的節點對；

(2)生成網絡鄰接矩陣：根據網絡的結構圖，生成網絡對應的鄰接矩陣；

(3)求解各個節點相位值

在Kuramoto模型中，網絡中的每個節點與一個振蕩器一一對應，分別編號為1到N；振蕩器的相位變化值對應節點的相位變化值，在MATLAB環境下，通過求解以下微分方程獲得每一個振蕩器在0到t時刻內的相位變化值，時間間隔為0.05；

其中，為振蕩器i的相位隨時間的變化率，w_i為振蕩器i的固有頻率，該固有頻率在[-0.01，0.01]之間服從均勻分布的隨機產生，K為耦合強度，當任意兩個節點i與節點j有連接時，即a_ij＝1時，K＝K₁(K₁＞0)，為正耦合；當任意兩個節點i與節點j無連接時，即a_ij＝0時，K＝K₂(K₂＜0)，為負耦合；N為網絡中節點的總數，a_ij為網絡的鄰接矩陣中的對應元素，分別為振蕩器i和j的相位，振蕩器的初始相位在[0，2π]之間服從均勻分布的隨機產生；為對節點j和節點i的相位差取正弦函數；

(4)判斷節點相位是否同步

計算第i個社區的相位參數M_i，若M_i大于0.8時，則說明第i個社區內部有超過百分之八十的節點已經趨于相位同步，則進入下一步驟；否則，返回步驟(3)，修改參數K，使正耦合系數K1增大，而負耦合系數K2減小，繼續求解節點的相位值；

(5)檢驗劃分結果

5a)在節點的相位圖結果中，將每一個相位同步的振蕩器所對應的節點放入一個同步組中；將同一個同步組中的節點劃分為一個社區，以此類推，直至將所有節點劃分到各自對應的社區；

5b)將步驟5a)得到的最終劃分結果中對應的節點編號1到N分別與原始社區中的節點編號進行對比，驗證劃分的正確性。

本發明與現有技術相比存在以下優點：

第一，由于本發明利用了振蕩器的相位同步原理，并行處理社區結構劃分，克服了現有技術的劃分效率低，時間較長的問題。本發明用微分方程求解振蕩器相位變化過程是一個并行處理過程，可大大減少對整個網絡節點進行相位同步運算的時間，從而有效地提高了節點相位同步的效率。