[發明專利]一種基于屬性圖信息的社團檢測方法

在審

• 申請號: 202111404046.6
• 申請日: 2021-11-24
• 公開（公告）號: CN114090835A
• 公開（公告）日: 2022-02-25
• 發明（設計）人: 于東曉;張立芳;羅琦
• 申請（專利權）人: 山東大學
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 青島華慧澤專利代理事務所(普通合伙) 37247
• 代理人: 付秀穎

1.一種基于屬性圖信息的社團檢測方法，其特征在于，包括以下步驟：

S1：對復雜網絡的數據進行預處理，構造網絡圖；

S2：將網絡圖構造成屬性圖，其中包括：將兩個節點之間的關系強度映射成所在邊上的權重，每個節點的強度映射成節點上的權重；

S3：給定查詢節點q和正整數k，在屬性圖上計算極大(s,c,k)-clique的模型；

S4：優化計算極大(s,c,k)-clique的模型的算法。

2.根據權利要求1所述的一種基于屬性圖信息的社團檢測方法，其特征在于，S2中構造的屬性圖中包括四個元素，即G＝(V,E,S,C),其中V表示節點集合，E表示邊集，S和C分別表示圖中節點權重集合和邊上的權重集合；

給定G的一個子屬性圖G’和查詢節點q，子屬性圖G’的權重W(G’)＝(s’，c’)，其中s’是圖中除q之外的其他頂點的最小權重，c’是子屬性圖中所有邊的最小權重。

3.根據權利要求2所述的一種基于屬性圖信息的社團檢測方法，其特征在于，在步驟S3中，當給定一個屬性圖G＝(V,E,S,C),一個查詢節點q和一個正整數k時，需要計算屬性圖中所有的極大(s,c,k)-clique；一個極大的(s,c,k)-clique指的是包含q的k-clique，且一個極大的(s,c,k)-clique的權重W＝(s,c)滿足極大性,即不存在另一個包含q的k-clique的子屬性圖的權重W’＝(s’,c’)使得s’≥s且c’c或者c’≥c且s’c，其中k為節點個數。

4.根據權利要求3所述的一種基于屬性圖信息的社團檢測方法，其特征在于，計算所有的極大(s,c,k)-clique的步驟為，

S31:計算屬性圖中包含q的極大(k-1)-core，因為所有的k-clique都會包含在(k-1)-core中，且計算k-core的算法是線性的；

S32:計算圖中所有包含查詢節點q的k-clique，具體方法包括以下步驟：

S321:初始化結果集R＝{q},候選集P＝{N(q)}，其中N(q)是q的鄰居集合；

S322:當P不為空時，每次從P中選擇一個節點u,N(u)是u的鄰居集合，使得N(u)∩P最大；

S323:對于每一個v∈P\N(u)，將v加入結果集R中，令P’＝P∩N(v)更新候選集，計算同時包含q和v的k-clique；

S324：當|R|＝k時，當前的R就是要求的一個k-clique，之后將P’恢復成P，并且將v從候選集中刪除，若P為空，則算法終止，否則返回S323；

S33：計算每個k-clique的權重；

S34：找出所有滿足極大性的k-clique，即為需要找的所有的極大(s，c，k)-clique。

5.根據權利要求1所述的一種基于屬性圖信息的社團檢測方法，其特征在于，

步驟S4中，優化計算極大(s，c，k)-clique的模型的算法，具體的計算步驟如下：

S41：計算圖中包含q的極大(k-1)-core，如果不存在則算法終止，否則繼續執行；

S42：對q的所有鄰居按照s值遞減進行排序，令s*是包含q的k-clique中最大的s值，且c’是對應的最大的c值，計算出(s*，c’)對應的k-clique；

S43：若S42中找不到對應的k-clique，則算法終止，若能找到，則將它們放入結果集中，繼續進行下一步；

S44：刪除圖中權重不大于c’的邊；

S45：重新回到41。

6.根據權利要求1所述的一種基于屬性圖信息的社團檢測方法，其特征在于，

步驟S4中，優化計算極大(s，c，k)-clique的模型的算法，具體的計算步驟如下：

當給定查詢節點q和參數k時，圖中存在一個比較大的k’-clique，其中k’＞k，且q和任意另外k-1個節點組成的k-clique都是滿足極大(s，c，k)-clique的定義；在這種情況下，需要計算的k-clique的數目為C(k’，k)，當k’＞＞k時，具體的計算步驟如下：

S4-1：計算圖中包含q的極大(k-1)-core，如果不存在則算法終止，否則繼續執行；

S4-2：計算圖中包含q的k-clique中可能的最大的c值，具體的公式如下：

c_Δ＝argmax_C≥0{|{v∈N(q)|C(q，v)≥c}|≥k-1}

S4-3：令c_δ為圖中最小的邊權重，當c_Δ＝c_δ時，直接計算包含q的極大clique；若c_Δ≠c_δ，令s*是包含q的k-clique中最大的s值，且c’是對應的最大的c值，計算滿足權重為(s*，c’)的極大clique，之后可以根據極大clique提取出k-clique，即q和任意的k-1個節點；

S4-4：令s_δ為圖中除q之外的最小頂點權重，如果s*＝s_δ或者c’＝c_Δ，則算法終止；否則，執行下一步；

S4-5：刪除圖中權重不大于c’的邊；

S4-6：重新回到S4-1。