[發明專利]社區圖識別及采樣方法、電子設備及計算機可讀存儲介質

在審

• 申請號: 202110474647.8
• 申請日: 2021-04-29
• 公開（公告）號: CN113191428A
• 公開（公告）日: 2021-07-30
• 發明（設計）人: 趙穎;武宜韜;吳岱霖;張辰琦;蔣昊瑾;白東英;談宜育;楊璐;周芳芳
• 申請（專利權）人: 中南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 蘇州拓云知識產權代理事務所(普通合伙) 32344
• 代理人: 王云峰

1.社區圖識別及采樣方法，其特征在于，包括以下步驟：

步驟1，采集原始數據集，給原始數據集中社區圖添加標記，標記“0”為社區平衡圖，標記“1”為社區不平衡圖；

步驟2，選擇能度量圖結構特征的量化指標，分別計算各量化指標與原始數據集中社區圖的皮爾遜相關系數，篩選出皮爾遜相關系數較高的五個量化指標作為訓練特征；

步驟3，將原始數據集分為訓練集和測試集，利用訓練集和訓練特征訓練數個分類器，根據各分類器對測試集的分類結果篩選出適用的分類器；

步驟4，將批量待處理社區圖輸入分類器得到社區圖的分類結果，若分類結果顯示為“0”則直接對其進行采樣，若分類結果顯示為“1”則執行步驟5；

步驟5，對社區不平衡圖進行劃分得到兩個社區平衡子圖；

步驟6，對社區平衡子圖進行平行采樣，將各采樣結果合并得到社區不平衡圖的采樣結果。

2.根據權利要求1所述的社區圖識別及采樣方法，其特征在于，所述原始數據集由以下數據組成：真實世界數據集、真實世界數據集子圖及圖生成器合成的數據集。

3.根據權利要求1所述的社區圖識別及采樣方法，其特征在于，所述步驟2具體包括：使用公式(1)分別計算各度量指標與原始數據集中社區圖的皮爾遜相關系數，將皮爾遜相關系數按降序排列，選擇皮爾遜相關系數較高的5個量化指標作為訓練特征；

公式(1)中為原始數據集包含的社區圖X與第j個量化指標Y^j的相關系數，i為原始數據集中社區圖的數目變量，I為原始數據集中社區圖的總數，X_i為第i幅社區圖的標記，X_i＝1或X_i＝0，j為量化指標的數目標量，j＝1,…,10，Y_i^j為第i幅社區圖的第j個量化指標值，分別為原始數據集中社區圖標記的均值與第j個量化指標值的均值，σ_X、分別為原始數據集中社區圖標記的標準差與第j個量化指標值的標準差，

所述訓練特征為密度最大的子圖節點數量、度同配系數、Wiener指數、總節點數和平均聚類系數。

4.根據權利要求1所述的社區圖識別及采樣方法，其特征在于，所述步驟3包括以下過程：

步驟31，將原始數據集按照8：2分為訓練集和測試集，利用訓練集和訓練特征分別訓練以下分類器：梯度上升決策樹、決策樹、隨機森林、基于網格搜索的最優超參邏輯回歸、有最優超參的遞歸特征消除結合邏輯回歸以及K近鄰；

步驟32，使用各分類器分別對測試集進行分類，計算各分類結果的準確度、精準度和召回率，據此將各分類器按綜合表現降序排列，選擇綜合表現最優的分類器進行分類；

所述最優的分類器為梯度上升決策樹。

5.根據權利要求1所述的社區圖識別及采樣方法，其特征在于，所述步驟5包括以下過程：

步驟51，對社區不平衡圖進行粗略化壓縮，過程如下：對于社區不平衡圖G＝(V,E)，選擇邊集E′＝E，從邊集E′中任選一條邊e，將邊e連接的兩個v_a、v_b收縮為一個節點，從邊集E′中刪除節點v_a、v_b關聯的所有邊，重復上述過程直至邊集E′為空；

步驟52，將粗略化社區不平衡圖劃分為兩個分區；

步驟53，將粗略化社區不平衡圖的劃分結果映射到原社區不平衡圖，得到兩個社區子圖。