[發明專利]基于貪婪策略的緊密k核子圖查詢方法

在審

• 申請號: 202110365960.8
• 申請日: 2021-04-06
• 公開（公告）號: CN113010546A
• 公開（公告）日: 2021-06-22
• 發明（設計）人: 趙丹楓;姚賢標;宋巍;郭偉其;包曉光;黃政;黃冬梅
• 申請（專利權）人: 上海海洋大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/2455
• 代理公司: 上海伯瑞杰知識產權代理有限公司 31227
• 代理人: 李慶

本發明提供一種基于貪婪策略的緊密k核子圖查詢方法，包括步驟：S1：進行連通k核查詢，得到候選子圖集合；S2：若當前所述候選子圖集合不滿足緊密子圖的條件，在所述候選子圖集合中迭代刪除節點權值最小的節點；S3：刪除當前所述候選子圖集合中節點度小于k的節點；S4：重復步驟S2～S3直至當前所述候選子圖集合的節點平均權值大于第一閾值w_Q或當前所述候選子圖集合的節點數小于第二閾值n_Q；S5：返回當前所述候選子圖集合，所述候選子圖集合為滿足條件的緊密k核子圖集。本發明的一種基于貪婪策略的緊密k核子圖查詢方法，具有更好的可擴展性，更加的貼合實際應用場景。

技術領域

本發明涉及大數據圖查詢領域，尤其涉及一種基于貪婪策略的緊密k核子圖查詢方法。

背景技術

在現有的大部分研究中，關于k核社團查詢使用的圖都是未加權的圖，其只考慮從圖中尋找一個稠密且內聚的結構，卻很少關注圖中節點與節點之間聯系的緊密程度。為解決這個問題，有文獻提出在加權圖中查詢親密核心組(querying intimate-core groups，QICG)問題，其將圖中邊的權值考慮在內，圖中各邊權值之和越小則表示圖內節點越親密。QICG問題給定加權圖G，查詢節點集Q，目標是在加權圖中查詢包含查詢節點集Q且邊權值總和最小的子圖。

但在現實生活中的大多數應用場景下，QICG存在如下問題：

1、需要查詢的社團僅包含給定的節點集；

2、節點之間邊的權值越大則聯系的緊密程度就越高，而QICG問題卻與之相反；

3、在很多的應用中并不需要查詢社團權重的最值。

發明內容

針對上述現有技術中的不足，本發明提供一種基于貪婪策略的緊密k核子圖查詢方法，其所得到的圖是一個具有一定規模、內部稠密、聯系緊密且連通的結構，具有更好的可擴展性，更加的貼合實際應用場景。

為了實現上述目的，本發明提供一種基于貪婪策略的緊密k核子圖查詢方法，包括步驟：

S1：進行連通k核查詢，得到候選子圖集合；

S2：若當前所述候選子圖集合不滿足緊密子圖的條件，在所述候選子圖集合中迭代刪除節點權值最小的節點；

S3：刪除當前所述候選子圖集合中節點度小于k的節點；

S4：重復步S2～S3直至當前所述候選子圖集合的節點平均權值大于第一閾值w_Q或當前所述候選子圖集合的節點數小于第二閾值n_Q；

S5：返回當前所述候選子圖集合，所述候選子圖集合為滿足條件的緊密k核子圖集。

優選地，所述S1步驟進一步包括步驟：

S11：計算目標圖中每個節點的核值；

S12：對所述目標圖進行k核分解后使用廣度優先搜索找到連通k核的所述候選子圖集合S_H，所述候選子圖集合S_H包括多個候選子圖。

優選地，所述S2前還包括步驟：

遍歷每個所述候選子圖，若所述候選子圖的節點數小于給定的所述第二閾值n_Q，則將該候選子圖從所述候選子圖集合S_H中移除；

若所述候選子圖的節點數大于等于第二閾值n_Q且所述候選子圖的節點平均權值大于等于所述第一閾值w_Q，則保留該候選子圖，否則在所述候選子圖集合S_H迭代刪除節點權值最小的節點。