[發(fā)明專(zhuān)利]一種復(fù)雜網(wǎng)絡(luò)的雙曲嵌入方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201811256608.5
• 申請(qǐng)日: 2018-10-26
• 公開(kāi)（公告）號(hào): CN109471995A
• 公開(kāi)（公告）日: 2019-03-15
• 發(fā)明（設(shè)計(jì)）人: 江昊;羿舒文;江穎;謝菁;曾園園
• 申請(qǐng)（專(zhuān)利權(quán)）人: 武漢大學(xué)
• 主分類(lèi)號(hào): G06F16/958
• 分類(lèi)號(hào): G06F16/958;G06F16/901
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 羅飛

1.一種復(fù)雜網(wǎng)絡(luò)的雙曲嵌入方法，其特征在于，包括：

步驟S1：獲得復(fù)雜網(wǎng)絡(luò)構(gòu)成的圖；

步驟S2：基于龐加萊圓盤(pán)模型將復(fù)雜網(wǎng)絡(luò)構(gòu)成的圖映射至曲率為-1的雙曲空間，獲得復(fù)雜網(wǎng)絡(luò)嵌入的雙曲圖，雙曲圖中包括各個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)坐標(biāo)和節(jié)點(diǎn)間的連接概率，根據(jù)所述復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的度和權(quán)重以及雙曲圖中各個(gè)節(jié)點(diǎn)的連接性質(zhì)，通過(guò)對(duì)數(shù)極大似然的方法估計(jì)出雙曲圖中的節(jié)點(diǎn)坐標(biāo)，根據(jù)每個(gè)節(jié)點(diǎn)的原始連接關(guān)系，進(jìn)而獲得復(fù)雜網(wǎng)絡(luò)嵌入雙曲空間后的網(wǎng)絡(luò)。

2.如權(quán)利要求1所述的方法，其特征在于，所述復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)總個(gè)數(shù)n，復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的連邊信息和節(jié)點(diǎn)間連邊的權(quán)重其中w_ij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間連邊的權(quán)重，i＝1，...，n，j＝1，...，n，當(dāng)連邊不存在時(shí)，權(quán)重為0，且w_ii＝1恒成立，步驟S1具體包括：

根據(jù)節(jié)點(diǎn)間的連邊信息生成復(fù)雜網(wǎng)絡(luò)鄰接矩陣其中x_ij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間是否存在連邊，i＝1，...，n，j＝1，...，n，如果存在連邊則為1，不存在連邊則為0，且x_ii＝1恒成立；

將上述復(fù)雜網(wǎng)絡(luò)構(gòu)成圖G(V，E)，其中，V表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)之間連邊的集合。

3.如權(quán)利要求2所述的方法，其特征在于，步驟S2具體包括：

步驟S2.1：根據(jù)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)總個(gè)數(shù)和龐加萊圓盤(pán)模型，計(jì)算雙曲圓盤(pán)半徑R；

步驟S2.2：設(shè)定迭代次數(shù)k，根據(jù)極大似然求解方法初步估計(jì)各個(gè)節(jié)點(diǎn)的第一角坐標(biāo)θ和第一度相關(guān)參數(shù)κ，其中，第一角坐標(biāo)θ為復(fù)雜網(wǎng)絡(luò)構(gòu)成的圖嵌入雙曲空間后初步估計(jì)的坐標(biāo)，第一度相關(guān)參數(shù)κ用以表征各個(gè)節(jié)點(diǎn)之間的連邊情況，通過(guò)統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)的度獲得；

步驟S2.3：根據(jù)初步估計(jì)的第一角坐標(biāo)θ和第一度相關(guān)參數(shù)κ，計(jì)算強(qiáng)度相關(guān)參數(shù)σ，其中，強(qiáng)度相關(guān)參數(shù)σ用以表征各個(gè)節(jié)點(diǎn)連邊的權(quán)重；

步驟S2.4：根據(jù)初步估計(jì)的第一角坐標(biāo)θ和第一強(qiáng)度相關(guān)參數(shù)σ，計(jì)算第二度相關(guān)參數(shù)κ′；

步驟S2.5：根據(jù)的強(qiáng)度相關(guān)參數(shù)σ和第二度相關(guān)參數(shù)κ′，計(jì)算各個(gè)節(jié)點(diǎn)的第二角坐標(biāo)θ′，其中，第二角坐標(biāo)為各個(gè)節(jié)點(diǎn)調(diào)整后的坐標(biāo)；

步驟S2.6：判斷迭代次數(shù)是否達(dá)到設(shè)定值k，如果未達(dá)到，則執(zhí)行步驟S2.3，其中步驟S2.3中用以估計(jì)的角坐標(biāo)和度相關(guān)參數(shù)均為步驟S2.4和步驟S2.5更新后的參數(shù)；

步驟S2.7：判斷條件估計(jì)的第二角坐標(biāo)θ′的精度是否已經(jīng)收斂，如果沒(méi)有收斂，則轉(zhuǎn)到步驟S2.3，其中步驟S2.3中用以估計(jì)的角坐標(biāo)和度相關(guān)參數(shù)均為步驟S2.4和步驟S2.5更新后的參數(shù)；

步驟S2.8：利用極大似然方法精估計(jì)各個(gè)節(jié)點(diǎn)的第三角坐標(biāo)θi，其中，第三角坐標(biāo)為各個(gè)節(jié)點(diǎn)在雙曲空間的實(shí)際坐標(biāo)；

步驟S2.9：根據(jù)節(jié)點(diǎn)總個(gè)數(shù)n、圓盤(pán)半徑R、冪律參數(shù)α和溫度T，計(jì)算各個(gè)節(jié)點(diǎn)的徑坐標(biāo)r_i；

步驟S2.10：根據(jù)節(jié)點(diǎn)的第三角坐標(biāo)θ_i和徑坐標(biāo)r_i，獲得所有復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的雙曲空間坐標(biāo)(r，θ)，所有雙曲空間節(jié)點(diǎn)構(gòu)成嵌入后的網(wǎng)絡(luò)。

4.如權(quán)利要求3所述的方法，其特征在于，步驟S2.1中，雙曲圓盤(pán)半徑R的具體計(jì)算方式如下：

其中，n為輸入加權(quán)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)總個(gè)數(shù)，β為冪律指數(shù)，根據(jù)累計(jì)度分布的經(jīng)典算法估計(jì)，α為調(diào)節(jié)參數(shù)，用于調(diào)節(jié)冪律指數(shù)β，其中，β和α之間的關(guān)系為β＝2α+1，T為溫度參數(shù)，用于調(diào)整雙曲空間基礎(chǔ)幾何結(jié)構(gòu)，|E|為圖節(jié)點(diǎn)連邊的總個(gè)數(shù)。