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

在審

• 申請?zhí)枺?/td>: 202110365960.8
• 申請日: 2021-04-06
• 公開（公告）號(hào): CN113010546A
• 公開（公告）日: 2021-06-22
• 發(fā)明（設(shè)計(jì)）人: 趙丹楓;姚賢標(biāo);宋巍;郭偉其;包曉光;黃政;黃冬梅
• 申請（專利權(quán)）人: 上海海洋大學(xué)
• 主分類號(hào): G06F16/2453
• 分類號(hào): G06F16/2453;G06F16/2455
• 代理公司: 上海伯瑞杰知識(shí)產(chǎn)權(quán)代理有限公司 31227
• 代理人: 李慶

1.一種基于貪婪策略的緊密k核子圖查詢方法，包括步驟：

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

S2：若當(dāng)前所述候選子圖集合不滿足緊密子圖的條件，在所述候選子圖集合中迭代刪除節(jié)點(diǎn)權(quán)值最小的節(jié)點(diǎn)；

S3：刪除當(dāng)前所述候選子圖集合中節(jié)點(diǎn)度小于k的節(jié)點(diǎn)；

S4：重復(fù)步驟S2～S3直至當(dāng)前所述候選子圖集合的節(jié)點(diǎn)平均權(quán)值大于第一閾值w_Q或當(dāng)前所述候選子圖集合的節(jié)點(diǎn)數(shù)小于第二閾值n_Q；

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

2.根據(jù)權(quán)利要求1所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述S1步驟進(jìn)一步包括步驟：

S11：計(jì)算目標(biāo)圖中每個(gè)節(jié)點(diǎn)的核值；

S12：對(duì)所述目標(biāo)圖進(jìn)行k核分解后使用廣度優(yōu)先搜索找到連通k核的所述候選子圖集合S_H，所述候選子圖集合S_H包括多個(gè)候選子圖。

3.根據(jù)權(quán)利要求2所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述S2前還包括步驟：

遍歷每個(gè)所述候選子圖，若所述候選子圖的節(jié)點(diǎn)數(shù)小于給定的所述第二閾值n_Q，則將該候選子圖從所述候選子圖集合S_H中移除；

若所述候選子圖的節(jié)點(diǎn)數(shù)大于等于第二閾值n_Q且所述候選子圖的節(jié)點(diǎn)平均權(quán)值大于等于所述第一閾值w_Q，則保留該候選子圖，否則在所述候選子圖集合S_H迭代刪除節(jié)點(diǎn)權(quán)值最小的節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求3所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述S2步驟中，若所述候選子圖的節(jié)點(diǎn)數(shù)小于所述第二閾值n_Q，認(rèn)為當(dāng)前所述候選子圖集合不滿足緊密子圖的條件。

5.根據(jù)權(quán)利要求4所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述S1步驟前還包括步驟：對(duì)所述目標(biāo)圖進(jìn)行壓縮。

6.根據(jù)權(quán)利要求5所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述對(duì)所述目標(biāo)圖進(jìn)行壓縮步驟進(jìn)一步包括步驟：

先將所述目標(biāo)圖中權(quán)值相近的節(jié)點(diǎn)合并，得到超節(jié)點(diǎn)；

所述超節(jié)點(diǎn)包含的節(jié)點(diǎn)若在原圖中存在邊，則在所述超節(jié)點(diǎn)之間構(gòu)建超邊；

最后將所述超邊的權(quán)值設(shè)為兩個(gè)所述超節(jié)點(diǎn)之間所包含的節(jié)點(diǎn)在原圖中邊權(quán)值的總和。

7.根據(jù)權(quán)利要求6所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，還包括步驟：按照一刪除規(guī)則刪除所述節(jié)點(diǎn)。

8.根據(jù)權(quán)利要求7所述的基于貪婪策略的緊密k核子圖查詢方法，其特征在于，所述刪除規(guī)則為：

設(shè)置每次迭代時(shí)的刪除比率γ，γ∈(0,1)，若所述候選子圖的節(jié)點(diǎn)數(shù)為|V(H)|，設(shè)每次迭代時(shí)待刪除節(jié)點(diǎn)集為S，則所述待刪除節(jié)點(diǎn)集S的數(shù)量|S|＝γ(|V(H)|-n_Q)；所述待刪除節(jié)點(diǎn)集S的取值通過對(duì)每次迭代后剩余子圖的節(jié)點(diǎn)按節(jié)點(diǎn)權(quán)值進(jìn)行排序，權(quán)值最小的前γ(|V(H)|-n_Q)個(gè)節(jié)點(diǎn)組成的集合即為所述待刪除節(jié)點(diǎn)集S；在下一次迭代刪除時(shí)，所述待刪除節(jié)點(diǎn)集S即作為需要從所述候選子圖中刪除的節(jié)點(diǎn)集。