[發明專利]一種面向有向-加權網絡的社區結構發現方法

在審

• 申請號: 201410631672.2
• 申請日: 2014-11-11
• 公開（公告）號: CN104391889A
• 公開（公告）日: 2015-03-04
• 發明（設計）人: 安健;桂小林;鄧昕宇;楊建偉;鐘華劍;陳立;田仕偉
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

1.一種面向有向-加權網絡的社區結構發現方法，其特征在于，包括以下步驟：

步驟一：根據已知社會網絡中節點集合N和不同節點邊的方向權重w，構造有向-加權網絡圖G；

步驟二：將有向-加權網絡圖G轉換為無向-加權網絡圖G'；

步驟三：對無向-加權網絡圖G'進行初始化：使用權重矩陣的形式存儲無向-加權網絡圖G'中鄰居節點及與鄰居節點邊的權重，得到權重矩陣A；

步驟四：對權重矩陣A進行歸一化處理；

步驟五：計算社區發現決策因子：基于歸一化后權重矩陣A，計算社區發現決策因子，包括節點活躍度，記為：H_i；社區關系強度，記為：I(S_k)；社區關系密度，記為：D(S_k)；社區耦合度，記為：F(S_k)；

步驟六：社區發現：從活躍度最大的節點開始作為初始社區的起點，依次計算加入社區外某節點后社區的耦合度F'，若存在節點j使得F'>F或F-F'<ε，則選擇使F'-F最大或F-F'最小的節點加入該社區，并更新節點j的社區標號以及該社區的耦合度；

步驟七：社區發現終止條件判斷：當社區加入任何節點都會使耦合度出現下降時，停止擴展該社區，認定該社區已穩定；選擇活躍度次之的節點作為新社區的起點，重復步驟六，直到所有節點均判決完畢；

步驟八：孤立節點處理：尋找與孤立節點j在原始加權-有向圖G中存在關聯的節點集，從關聯節點集中選擇與孤立節點邊權重差最小的節點作為其有效關聯節點，并將該孤立節點加入該有效關聯節點所屬社區。

2.根據權利要求1所述的一種面向有向-加權網絡的社區結構發現方法，其特征在于，步驟二具體包括：節點i指向節點j的有向邊的權值記為wi_j，節點j指向節點i的有向邊的權值記為w_ji，簡化后加權圖中節點i和節點j之間無向邊權值記為w_ij'或w_ji'；對于有向-加權網絡圖G中任意兩個節點i和j，若去掉節點i和節點j之間的兩條有向邊；若|wij-wji|>12max(wij,wji),]]>則將兩條有向邊變為無向邊，令wji′=12(wij+wji);]]>其中，i、j表示社會網絡中的節點，其中，i∈N，j∈N；S_k表示網絡中的不同社區，其中k∈C，C為網絡中社區數集合；w為節點間邊的權重，節點i指向節點j的有向邊的權值記為w_ij，節點j指向節點i的有向邊的權值記為w_ji。

3.根據權利要求1所述的一種面向有向-加權網絡的社區結構發現方法，其特征在于，步驟三中使用權重矩陣的形式存儲無向-加權網絡圖G'中鄰居節點及與鄰居節點邊的權重，如下表示形式：A＝(a_ij)，其中a_ij＝a_ji＝w_ij'；