[發明專利]基于傳播限制的標簽傳播方法

在審

• 申請號: 201610021892.2
• 申請日: 2016-01-13
• 公開（公告）號: CN105631157A
• 公開（公告）日: 2016-06-01
• 發明（設計）人: 姚勇;劉慧慧;劉志鏡;馮阿敏;武文驍;王炳華
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 程曉霞;王品華

技術領域

本發明屬于數據處理技術領域，主要涉及利用計算機數據挖掘技術對真實網絡數 據進行分析和處理，具體是一種基于傳播限制的標簽傳播法，特別適于復雜網絡中模塊的 分析和處理。

背景技術

現實世界紛繁復雜，各種事物之間存在著普遍的聯系和彼此的依賴。隨著計算機 技術的快速發展，人們對于復雜的事物和系統用復雜網絡來建模表示，并通過網絡分析與 數據挖掘方法進行深入的研究與探索，探索復雜事物之間相關因素的關聯和規律。20世紀 末，人類對復雜網絡的認識有了突破性進展,除了眾所周知的小世界特性和無標度特性外， 科學家們還發現各類復雜網絡中普遍存在著模塊結構。所謂模塊結構是指網絡中內部連接 較為緊密而彼此連接較為松散的子結構。在現實世界中,模塊結構往往對應著各類系統中 不同的功能與結構。例如生物蛋白質相互作用網絡中的蛋白復合體、電路網絡中的各個功 能模塊以及社會網絡中的組織團體等。

標簽傳播算法(labelpropagationalgorithm,LPA)是由ZhuXJ于2002年提出， 它是一種基于圖的半監督學習方法，其基本思想是用已標記節點的標簽信息去預測未標記 節點的標簽信息。該算法的優點是計算過程非常簡單，計算速度非常之快，但缺點是算法的 穩定性較差，每次運行得到的結果會很不相同，導致實際運用價值不高。

因此，非常有必要開發一種快速并且穩定性好的方法，來對大的復雜網絡進行更 準確的劃分。

發明內容

本發明的主要技術問題是在復雜網絡中，如何減少不同模塊間標簽在傳遞中的相 互干擾，使得同一模塊內的標簽只在模塊內傳播，而不擴散到不同的模塊之間。通過改變初 始條件為2-node子結構，同一子結構具有相同的標簽，這樣可以減少模塊間標簽傳播的相 互干擾。因此通過限制標簽傳播，可以找到復雜網絡中的真實模塊。通過采用迭代策略,進 一步提高了結果的準確性。

本發明是一種基于傳播限制的標簽傳播方法，其特征在于，對復雜網絡采用2- node子結構建模來限制各個模塊間的標簽傳播，減少模塊間標簽傳播的相互干擾，將一個 大的復雜的網絡劃分為多個有關聯的模塊，包括有如下步驟：

第1步、給定的大的復雜網絡使用相似度公式生成2-node子結構，在2-node子結構 中節點的相似度最大。

初始化時，將大的復雜網絡定義為G：設G＝(V,E)為無向無權網絡，V為節點集合，E 為邊集合，對G＝(V,E)的任意邊ij，使用相似度公式：

Sim=|N(vi)∩N(vj)||N(vi)∪N(vj)|]]>

其中，v_i、v_j分別表示節點i和節點j，N(v_i)、N(v_j)分別代表節點i和節點j的相鄰節 點的集合。

第2步、每一個2-node子結構中的兩個節點分配相同的標簽。

第3步、對每一個節點的標簽進行更新，根據相鄰節點中標簽出現次數最大的標簽 來更新自身的標簽，如果出現次數最大的標簽不唯一，從中隨機選擇一個標簽來更新本節 點。也可以說根據同一標簽數量最多的相鄰節點來更新自身的標簽，如果此節點存在多個 相同最大標簽數量的相鄰節點群時，在這些節點群中隨機選擇任意一個節點群，使用此群 中節點的標簽對該節點進行更新，該節點和所選擇的節點群屬于同一標簽和同一群結構。