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

在審

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

本發明公開了一種社區圖識別及采樣方法、電子設備及計算機可讀存儲介質，所述方法包括：步驟1，采集原始數據，給原始數據添加標記；步驟2，選擇量化指標作為訓練特征；步驟3，訓練分類器；步驟4，利用分類器將待處理圖數據劃分為社區平衡圖和社區不平衡圖，對社區平衡圖進行采樣處理；步驟5，將社區不平衡圖劃分為兩個子圖；步驟6，對兩個子圖進行并行采樣，并將采樣結果合并得到社區不平衡圖的采樣結果；本發明采樣過程簡單、效率高，且能全面保留社區圖中的原始圖結構和關鍵圖屬性。

技術領域

本發明屬于數據結構和圖挖掘技術領域，特別是涉及一種社區圖識別及采樣方法、電子設備及計算機可讀存儲介質。

背景技術

圖是一類常見的數據結構，復雜網絡的研究中常采用圖數據結構來進行存儲、分析，大多數人們感興趣的真實世界網絡均展現出社區結構，社區代表著網絡內部存在一定的自然劃分，反映了網絡集團化的程度，可以根據圖中所包含社區結構的均衡性將圖劃分為社區平衡圖和社區不平衡圖，包含單個社區或多個規模相近的社區的圖為社區平衡圖，如圖1中(a)所示，包含多個社區且這些社區呈現較大規模差異的圖則為社區不平衡圖，如圖1中(b)所示。

圖采樣旨在保持原始圖結構或關鍵圖屬性的同時，有效縮減圖的規模，相比于社區平衡的圖數據集，圖采樣算法運行在社區不平衡圖上時，難以很好地保持原始圖中的一些特定結構，尤其是一類稀有結構(Minority Structure)，原因在于：現有的采樣算法，尤其是基于遍歷的算法，難以保持社區不平衡圖中的小社區及邊緣的小集團(far clique)，而一些重要的稀有結構往往與這些小社區、邊緣集團相關聯，如較長的連接結構(longtie)和鏈狀的邊緣結構(chain-like rim)，因此處理圖數據集中的社區不平衡圖對圖采樣至關重要，但目前仍沒有與之相關的研究及可行的解決方案。

發明內容

本發明實施例的目的在于提供一種社區圖識別及采樣方法，使用本發明能夠準確地將社區圖分為社區平衡圖和社區不平衡圖，并對不同圖分別進行處理，以便全面保留社區圖中的原始圖結構和關鍵圖屬性，使采樣結果更加準確，同時在社區不平衡圖采樣中將其劃分為兩個子圖，避免了社區不平衡圖劃分過細導致的團簇太多，降低了采樣的復雜性和計算開銷，提高了社區圖采樣的準確性和效率。

本發明還提供了一種電子設備和計算機可讀存儲介質。

為解決上述技術問題，本發明所采用的技術方案是，社區圖識別及采樣方法，包括以下步驟：

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

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

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

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

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

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

進一步的，所述原始數據集由以下數據組成：真實世界數據集、真實世界數據集子圖及圖生成器合成的數據集。

進一步的，所述步驟2具體包括：使用公式(1)分別計算各度量指標與原始數據集中社區圖的皮爾遜相關系數，將皮爾遜相關系數按降序排列，選擇皮爾遜相關系數較高的5個量化指標作為訓練特征；