基于振蕩器相位同步的網絡社區結構劃分方法
2023-10-24 07:01:37 5
專利名稱：基于振蕩器相位同步的網絡社區結構劃分方法
技術領域：
本發明屬於計算機領域，更進一步涉及小世界網絡技術領域中基于振蕩器相位同步的網絡社區結構劃分方法。本發明通過引入包含正負耦合強度的Kuramoto模型，由振蕩器相位同步原理，提高了並行處理能力，可快速有效地進行小世界網絡中社區結構的劃分。
背景技術：
小世界網絡是最典型的複雜網絡之一，即一個高度聚集的包含了「局部連接」節點的子網，連同一些有助於產生短路徑的長距離隨機連接。異構網絡中由不同性質、類型的節點組成的關係豐富的結構稱為「社區」(子網絡)。社區內關係稠密，而不同社區節點之間關係稀疏的結構-社區結構是複雜網絡的特徵之一。對網絡中社區結構的劃分是複雜網絡中面臨的主要問題之一，人們也提出了很多方法來對網絡進行社區結構的劃分。北京航空航天大學申請的專利「一種複雜網絡中的社區劃分方法」(專利申請號 200810224175. 5，公開號CN 101383748A)。該方法是以若干個不同的局部帶有影響力的節點為核心，並使節點的影響力從核心逐層向外均勻擴散，最終形成了以影響力最大的節點為核心，逐層擴展中節點的影響力不斷衰減，它們之間相互關聯形成一個局部區域，擴展到方法的停止，節點影響力很小，到達該局部區域的網絡邊緣。該方法存在不足之處是，對於給定的拓撲結構，要計算網絡中所有節點相互作用之後而產生的影響力疊加值，該計算過程過於複雜，需要較長的時間來對所有節點的相關值進行計算，並且要計算每一層擴展節點對上一層節點和對下一層節點連接的邊數的比值，最後還要保證網絡所有的節點都被擴展過，該方法迭代次數過多，降低了劃分效率，耗費時間長。
發明內容
本發明的目的在於克服現有技術的不足，提出一種基于振蕩器相位同步的網絡社區結構劃分方法，以實現小世界網絡中社區結構的快速有效地進行劃分。本發明使用加入正負耦合係數的Kuramoto模型，基于振蕩器相位同步原理，通過微分方程的並行處理方式使節點相位快速有效的同步，實現網絡社區的劃分。本發明的具體步驟如下(1)繪製由若干個獨立環狀結構組成的網絡結構圖，以特定概率隨機連接環狀結構中的節點對；(2)生成網絡鄰接矩陣根據網絡的結構圖，生成網絡對應的鄰接矩陣；(3)求解各個節點相位值在Kuramoto模型中，網絡中的每個節點與一個振蕩器一一對應，分別編號為1到 N ；振蕩器的相位變化值對應節點的相位變化值，在MATLAB環境下，通過求解以下微分方程獲得每一個振蕩器在O到t時刻內的相位變化值，時間間隔為0. 05 ；(Pi = + —Σ α sinC^y - Ψι) 0· = 1，2··. N)
7 = 1其中，&為振蕩器i的相位隨時間的變化率，Wi為振蕩器i的固有頻率，該固有頻
率在[-0. 01,0. 01]之間服從均勻分布的隨機產生，K為耦合強度，當任意兩個節點i與節點j有連接時，即= ι時，κ = K1 (K1 > 0)，為正耦合；當任意兩個節點i與節點j無連接時，即aij = 0時，K = K2(K2 < 0)，為負耦合；N為網絡中節點的總數，aij為網絡的鄰接矩陣中的對應元素，釣，約分別為振蕩器i和j的相位，振蕩器的初始相位在W，2 π ]之間服從均勻分布的隨機產生；sin(約-仍)為對節點j和節點i的相位差取正弦函數；(4)判斷節點相位是否同步計算第i個社區的相位參數Mi,若Mi大於0. 8時，則說明第i個社區內部有超過百分之八十的節點已經趨於相位同步，則進入下一步驟；否則，返回步驟(3)，修改參數K， 使正耦合係數Kl增大，而負耦合係數K2減小，繼續求解節點的相位值；(5)檢驗劃分結果5a)在節點的相位圖結果中，將每一個相位同步的振蕩器所對應的節點放入一個同步組中；將同一個同步組中的節點劃分為一個社區，以此類推，直至將所有節點劃分到各自對應的社區；5b)將步驟5a)得到的最終劃分結果中對應的節點編號1到N分別與原始社區中的節點編號進行對比，驗證劃分的正確性。本發明與現有技術相比存在以下優點第一，由於本發明利用了振蕩器的相位同步原理，並行處理社區結構劃分，克服了現有技術的劃分效率低，時間較長的問題。本發明用微分方程求解振蕩器相位變化過程是一個並行處理過程，可大大減少對整個網絡節點進行相位同步運算的時間，從而有效地提高了節點相位同步的效率。第二，由於本發明引入了正負耦合係數的Kuramoto模型，根據社區內部連接緊密，鄰接矩陣中對應元素多數為1，作用的正耦合係數較多，優先使社區內部的節點的相位趨於同步；而在不同社區之間，由於節點對連接較為稀疏，鄰接矩陣中對應元素多數為0， 作用的負耦合係數較多，從而將不同社區的節點對的相位分離開。本發明克服了現有技術中採用Kuramoto模型進行社區劃分時，只有正耦合係數而使整個網絡的節點相位(無論在不在一個社區)趨於同步，而體現不出社區結構的缺點。使得本發明中同一個社區內的節點的相位聚集，形成一個同步組，而不同社區間的節點的相位分離。根據同步組的數量就可以確定出社區個數，同步組中的節點即為對應的社區中的節點。本發明依據節點的相位圖， 可以準確的劃分出社區結構。
圖1為本發明的流程圖；圖2為本發明實例中構造出的網絡結構圖；圖3為本發明與現有技術參數M的比較圖；圖4為本發明與現有技術社區劃分的結果圖。
具體實施例方式下面結合圖1對本發明的具體實施步驟做進一步的詳細描述。步驟1.繪製網絡結構圖繪製由若干個獨立環狀結構組成的網絡結構圖，以特定概率隨機連接環狀結構中的節點對，網絡結構圖特定概率是指每個環狀結構對應一個社區，環狀結構內部的節點對連接的概率大於不同環狀結構之間的節點對連接的概率，網絡結構圖的節點數為20 800 個。本發明的實施例用Matlab軟體繪製一個由四個獨立的環狀結構構成的網絡圖， 每個環狀結構有10 = 40/4個節點，每個節點與他的最鄰近的四個鄰居連接(每邊各有二個鄰居)；最初狀態下，每個環狀結構之間沒有連接，每個獨立的環狀結構相當於一個社區。設定概率Pl = 0.4，p2 = 0. 1，以概率pi分別連接4個社區內部之間的節點對，以概率P2連接4個社區之間的節點對。最終生成的網絡結構圖如圖2所示，圖中1到40分別表示節點的編號，X表示節點在橫軸上的坐標，Y表示節點在縱軸上的坐標。步驟2.生成網絡鄰接矩陣根據網絡的結構圖，生成網絡對應的鄰接矩陣；生成的鄰接矩陣中的元素是由網絡中任意兩個節點i與節點j之間是否相連而確定，若相連，則= 1，否則aij = 0。本發明實施例中網絡對應的鄰接矩陣為
權利要求
1.一種基于振蕩器相位同步的網絡社區結構劃分方法，具體步驟如下(1)繪製由若干個獨立環狀結構組成的網絡結構圖，以特定概率隨機連接環狀結構中的節點對；(2)生成網絡鄰接矩陣根據網絡的結構圖，生成網絡對應的鄰接矩陣；(3)求解各個節點相位值在Kuramoto模型中，網絡中的每個節點與一個振蕩器一一對應，分別編號為1到N ；振蕩器的相位變化值對應節點的相位變化值，在MATLAB環境下，通過求解以下微分方程獲得每一個振蕩器在O到t時刻內的相位變化值，時間間隔為0. 05 ； .κ NΨι = W, + —Σ Ciij sin(^y - (Pi) (i = 1,2··· N)丄、y = l其中，&為振蕩器i的相位隨時間的變化率，Wi為振蕩器i的固有頻率，該固有頻率在 [-0. 01,0. 01]之間服從均勻分布的隨機產生，K為耦合強度，當任意兩個節點i與節點j有連接時，即= 1時，K = KJK1 > 0)，為正耦合；當任意兩個節點i與節點j無連接時，即 Bij = 0時，K = K2(K2 < 0)，為負耦合；N為網絡中節點的總數，aij為網絡的鄰接矩陣中的對應元素，仍，約分別為振蕩器i和j的相位，振蕩器的初始相位在W，2 π ]之間服從均勻分布的隨機產生；sin(約-仍)為對節點j和節點i的相位差取正弦函數；(4)判斷節點相位是否同步計算第i個社區的相位參數Mi,若Mi大於0. 8時，則說明第i個社區內部有超過百分之八十的節點已經趨於相位同步，則進入下一步驟；否則，返回步驟(3)，修改參數K，使正耦合係數Kl增大，而負耦合係數K2減小，繼續求解節點的相位值；(5)檢驗劃分結果5a)在節點的相位圖結果中，將每一個相位同步的振蕩器所對應的節點放入一個同步組中；將同一個同步組中的節點劃分為一個社區，以此類推，直至將所有節點劃分到各自對應的社區；5b)將步驟5a)得到的最終劃分結果中對應的節點編號1到N分別與原始社區中的節點編號進行對比，驗證劃分的正確性。
2.根據權利要求1所述的基于振蕩器相位同步的網絡社區結構劃分方法，其特徵在於，步驟(1)所述的網絡結構圖特定概率是指每個環狀結構對應一個社區，環狀結構內部的節點對連接的概率大於不同環狀結構之間的節點對連接的概率。
3.根據權利要求1所述的基于振蕩器相位同步的網絡社區結構劃分方法，其特徵在於，步驟(1)所述的網絡結構圖的節點數為20 800個。
4.根據權利要求1所述的基于振蕩器相位同步的網絡社區結構劃分方法，其特徵在於，步驟(2)所述生成的鄰接矩陣中的元素％是由網絡中任意兩個節點i與節點j之間是否相連而確定，若相連，則= 1，否則= 0。
5.根據權利要求1所述的基于振蕩器相位同步的網絡社區結構劃分方法，其特徵在於，步驟(4)所述的相位參數Mi的表達式為其中，Mi表示在社區i中已經同步的節點佔社區i節點總數的百分比，N。表示社區i中節點總數，約表示節點j的相位，表示複數。
全文摘要
本發明提出了一種基于振蕩器相位同步的網絡社區劃分方法，克服了現有技術中劃分效率低，耗費時間長以及傳統Kuramoto模型中只有正耦合係數而不能體現社區結構的問題。其實現步驟是(1)繪製網絡結構圖；(2)生成網絡鄰接矩陣；(3)求解節點相位值；(4)判定節點相位是否同步；(5)檢驗劃分結果。本發明提出的方法使用加入正負耦合係數的Kuramoto模型，基于振蕩器相位同步原理，通過微分方程的並行處理方式有效地提高了節點相位同步的效率，得到準確的社區結構劃分結果。
文檔編號H04L12/28GK102355393SQ20111028998
公開日2012年2月15日 申請日期2011年9月27日 優先權日2011年9月27日
發明者吳家驥, 吳建設, 尚榮華, 戚玉濤, 焦李成, 王達, 白靜, 靳超, 韓紅 申請人:西安電子科技大學