[發(fā)明專利]一種基于網(wǎng)絡(luò)分區(qū)的層次網(wǎng)絡(luò)嵌入方法

有效

• 申請?zhí)枺?/td>: 202010410813.3
• 申請日: 2020-05-15
• 公開（公告）號: CN111597665B
• 公開（公告）日: 2023-05-23
• 發(fā)明（設(shè)計）人: 張賢坤;馬蘊(yùn)玢;康俊龍
• 申請（專利權(quán)）人: 天津科技大學(xué)
• 主分類號: G06F30/18
• 分類號: G06F30/18
• 代理公司: 北京慕達(dá)星云知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11465
• 代理人: 符繼超

1.一種基于網(wǎng)絡(luò)分區(qū)的層次網(wǎng)絡(luò)嵌入方法，其特征在于，包括：

步驟1：基于模塊度增益判斷網(wǎng)絡(luò)原圖中節(jié)點(diǎn)的歸屬社區(qū)，確定網(wǎng)絡(luò)分區(qū)數(shù)；

步驟2：將網(wǎng)絡(luò)分區(qū)數(shù)設(shè)定為最小規(guī)模抽象圖的規(guī)模閾值，基于混合坍縮方法對網(wǎng)絡(luò)原圖進(jìn)行圖抽象，輸出規(guī)模逐漸縮小的抽象圖，直至最粗抽象圖等于最小規(guī)模抽象圖的規(guī)模；混合坍縮方法具體坍縮過程需要滿足雙射函數(shù)和滿射函數(shù)：

雙射函數(shù)使得有其中C表示網(wǎng)絡(luò)原圖的社區(qū)，v_a表示抽象圖的節(jié)點(diǎn)，V_a表示抽象圖節(jié)點(diǎn)集，C_i表示網(wǎng)絡(luò)原圖的各個社區(qū)，表示抽象圖節(jié)點(diǎn)集的各個節(jié)點(diǎn)；

滿射函數(shù)使得有其中G表示網(wǎng)絡(luò)原圖，V表示網(wǎng)絡(luò)原圖節(jié)點(diǎn)集，G_a表示抽象圖，V_a表示抽象圖節(jié)點(diǎn)集，v_i表示網(wǎng)絡(luò)原圖節(jié)點(diǎn)集V的各個節(jié)點(diǎn)，表示抽象圖節(jié)點(diǎn)集V_a的各個節(jié)點(diǎn)；

步驟3：根據(jù)基線算法對最粗抽象圖進(jìn)行表示學(xué)習(xí)，得到最粗抽象圖的表示；具體為：

通過基線算法Embed應(yīng)用于(G_aL,0)進(jìn)行學(xué)習(xí)，得到最粗抽象圖的表示G_aL表示最粗抽象圖，0表示零矩陣，作為最粗抽象圖的初始參照；

步驟4：通過嵌入傳播方法由最粗抽象圖的表示逐層傳播和細(xì)化，得到原始圖表示；具體為：

將最粗抽象圖的表示作為最粗抽象圖的上一層抽象圖G_aL-1的參照嵌入，將傳播算法Propagation應(yīng)用于

將基線算法Embed應(yīng)用于得到最粗抽象圖的上一層抽象圖的表示

重復(fù)以上步驟，直到嵌入傳播得到首層抽象圖G_a0的表示

嵌入傳播過程需要滿足嵌入函數(shù)和傳播函數(shù)：

傳播函數(shù)其中G_aL-1表示最粗抽象圖的上一層抽象圖，G_aL表示最粗抽象圖，表示最粗抽象圖的表示，表示最粗抽象圖的上一層抽象圖的參照嵌入；

嵌入函數(shù)其中G_aL-1表示最粗抽象圖的上一層抽象圖，表示最粗抽象圖的上一層抽象圖的參照嵌入，G_aL-1表示最粗抽象圖的上一層抽象圖的表示。

2.根據(jù)權(quán)利要求1所述的一種基于網(wǎng)絡(luò)分區(qū)的層次網(wǎng)絡(luò)嵌入方法，其特征在于，步驟1包括：

步驟11：輸入網(wǎng)絡(luò)原圖G＝(V,E)，其中，V表示網(wǎng)絡(luò)原圖G的節(jié)點(diǎn)集，E表示網(wǎng)絡(luò)原圖G的邊集；

步驟12：根據(jù)模塊度增益ΔQ將網(wǎng)絡(luò)原圖中的節(jié)點(diǎn)重新劃分歸屬社區(qū)，從而確定出網(wǎng)絡(luò)分區(qū)數(shù)n_c；

ΔQ表示模塊度增益，其值反應(yīng)了節(jié)點(diǎn)i由當(dāng)前社區(qū)并入到其鄰居社區(qū)的模塊度增益，|E|表示網(wǎng)絡(luò)原圖中邊數(shù)目，c_a表示節(jié)點(diǎn)i發(fā)生社區(qū)變化前的鄰居社區(qū)，c_b表示節(jié)點(diǎn)i發(fā)生社區(qū)變化前的當(dāng)前社區(qū)，表示節(jié)點(diǎn)i發(fā)生社區(qū)變化前社區(qū)c_a中所有節(jié)點(diǎn)的度之和，表示節(jié)點(diǎn)i發(fā)生社區(qū)變化前社區(qū)c_b中所有節(jié)點(diǎn)的度之和，k_i表示節(jié)點(diǎn)i的度，表示節(jié)點(diǎn)i與并入后社區(qū)c_a中節(jié)點(diǎn)的連接邊數(shù)，表示節(jié)點(diǎn)i與并入前社區(qū)c_b中節(jié)點(diǎn)的連接邊數(shù)。

3.根據(jù)權(quán)利要求2所述的一種基于網(wǎng)絡(luò)分區(qū)的層次網(wǎng)絡(luò)嵌入方法，其特征在于，步驟2具體包括：

在圖抽象的過程中，每層圖的劃分結(jié)果需要滿足以下條件：

其中,C_i、C_j分別表示網(wǎng)絡(luò)原圖中第i、j個社區(qū)；|C_i|表示網(wǎng)絡(luò)原圖中的分區(qū)數(shù)目，v_j表示網(wǎng)絡(luò)原圖分區(qū)C_i的節(jié)點(diǎn)集，V表示網(wǎng)絡(luò)原圖的節(jié)點(diǎn)集，G表示網(wǎng)絡(luò)原圖；

通過圖抽象輸出規(guī)模逐漸縮小的抽象圖：

G_ai＝(V_ai,E_ai),i＝1,2,...,L??????(3)

其中，|V_ai|＜＜|V|,|E_ai|＜＜|E|，|V|表示網(wǎng)絡(luò)原圖的節(jié)點(diǎn)數(shù)目，|E|表示網(wǎng)絡(luò)原圖的邊數(shù)目，V_ai表示抽象圖G_ai的節(jié)點(diǎn)集，E_ai表示抽象圖G_ai的邊集，|V_ai|表示抽象圖G_ai的節(jié)點(diǎn)數(shù)目，|E_ai|表示抽象圖G_ai的邊數(shù)目，i表示第i層抽象圖。