[發明專利]基于振蕩器相位同步的符號網絡社區檢測方法

有效

• 申請號: 201310392893.4
• 申請日: 2013-09-01
• 公開（公告）號: CN103475539A
• 公開（公告）日: 2013-12-25
• 發明（設計）人: 吳建設;焦李成;張龍;緱水平;焦洋;王芳;郭開武;袁林;侯艷巧
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

技術領域

本發明屬于網絡技術領域，更進一步涉及數據挖掘技術領域中的一種基于振蕩器相位同步的符號網絡社區檢測方法。本發明通過引入改進的振蕩器模型，利用振蕩器相位同步原理，提高了并行處理能力，可快速有效地檢測出符號網絡的各個社區。

背景技術

目前復雜網絡已成為最前沿和最具挑戰性的多學科性研究領域之一，現有復雜網絡分析往往采用單一正關系邊值模型來表示節點間的關系，然而現實社會網絡關系中對于一個事物的評價或者人與人之間的關系，往往存在兩面性，支持與反對，朋友和敵人，積極與消極，從無符號網絡角度已經無法很好的解釋這種網絡結構關系。例如，在虛擬網絡社區中，用戶之間不僅存在朋友關系，也可能存在由黑名單產生的敵對關系。

為了更加全面客觀地發現社會網絡數據的潛在特征關系，有必要對現有網絡分析模型加以擴展得出符號網絡分析模型。符號網絡是指包含正負兩種關系的復雜網絡。例如在社會網絡中，“喜歡”、“尊重”和“表揚”屬于正向關系，而“厭惡”、“輕視”和“責備”屬于負向關系。類似的正負關系在生物網絡和科技網絡等其它復雜網絡中也廣泛存在。符號網絡中的社區是指多個不相交的節點集合，集合內的正關系稠密而集合間負關系稠密。符號網絡社區結構挖掘方法的研究對分析復雜網絡的拓撲結構和發現復雜網絡中的隱藏規律具有十分重要的意義，例如識別社會網中的恐怖組織，預測蛋白質的未知功能，萬維網的網頁自動分類等。

方平申請的專利“一種復雜網絡局部社區發現方法”（專利申請號201210306231.5，公開號CN102819611A）中公開一種復雜網絡的社區檢測方法。該方法是以網絡中的最大度節點為起始節點，計算其鄰居節點，獲得其鄰居節點集；找到與最大度節點擁有最多共同鄰居節點的節點；以此兩個節點組成初始局部社區；獲得初始局部社區的各鄰居節點接近度，取接近度最大的節點加入初始局部社區形成新的初始局部社區；計算初始局部社區的Q值；重復上述步驟，直到形成新的初始局部社區Q值大于0或網絡中節點為空。該方法存在不足之處是：該方法不適合于對存在負向關系的符號網絡的社區檢測。對于給定的網絡，每次合并初始社區模塊都必須查找初始社區鄰居節點的接近度，然后計算合并初始社區模塊所得的社區模塊Q值，該專利計算過程過于復雜，需要較長的時間來計算節點的接近度，循環次數過多，降低了檢測效率，耗費時間長。

發明內容

本發明的目的在于上述克服現有技術的不足，提出一種基于振蕩器相位同步的符號網絡社區檢測方法，以實現符號網絡中社區結構的快速有效地進行檢測。本發明使用改進的Kuramoto模型，基于振蕩器相位同步原理，通過微分方程的并行處理方式使節點相位快速進行更新并達到同步，根據各個節點穩定時的相位，可快速有效地檢測出符號網絡的各個社區和社區間的重疊節點。

實現本發明目的的具體步驟如下：

(1)生成鄰接矩陣：

將待檢測符號網絡中節點按照1～N依次編號，N表示該符號網絡中節點的總個數；將待檢測符號網絡中節點i與節點j之間有正向連接邊所對應的鄰接矩陣中的元素a_ij設定為1；將待檢測符號網絡中節點i與節點j之間無連接邊所對應的鄰接矩陣中的元素a_ij設定為0；將待檢測符號網絡中節點i與節點j之間有負向連接邊所對應的鄰接矩陣中的元素a_ij設定為-1；獲得與待檢測符號網絡所對應的鄰接矩陣；

(2)節點相位初始化：

在[0,2π]相位值范圍內，隨機產生且服從均勻分布的N個隨機數，將所產生的隨機數一一對應地設為符號網絡中N個節點的初始相位；

(3)更新節點相位：

3a)將振蕩器模型中的N個振蕩器按照1～N依次編號，振蕩器模型中的第i個振蕩器對應被檢測的符號網絡中的第i個節點，第i個振蕩器的相位更新值對應被檢測符號網絡中第i個節點的相位更新值；

3b)將節點的初始相位值代入以下振蕩器模型，通過各個振蕩器之間的相互正負耦合作用，求解微分方程，并行計算所有振蕩器更新后的相位值集合P₁；