[發(fā)明專利]一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202010723330.9
• 申請(qǐng)日: 2020-07-24
• 公開(kāi)（公告）號(hào): CN111860866A
• 公開(kāi)（公告）日: 2020-10-30
• 發(fā)明（設(shè)計(jì)）人: 何嘉林
• 申請(qǐng)（專利權(quán)）人: 西華師范大學(xué)
• 主分類號(hào): G06N20/00
• 分類號(hào): G06N20/00
• 代理公司: 成都行之專利代理事務(wù)所(普通合伙) 51220
• 代理人: 李朝虎

1.一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，包括以下步驟：

步驟1：數(shù)據(jù)收集與處理階段：使用一種密度函數(shù)，通過(guò)在網(wǎng)絡(luò)G上使用隨機(jī)游走策略，獲得頂點(diǎn)序列樣本S＝{s₁,s₂,...,s_n}；

步驟2：數(shù)據(jù)表示學(xué)習(xí)階段：優(yōu)化Skip-gram模型，使用Skip-gram模型來(lái)訓(xùn)練頂點(diǎn)序列樣本S＝{s₁,s₂,...,s_n}，得到每個(gè)頂點(diǎn)序列的向量表示；

步驟3：數(shù)據(jù)計(jì)算階段：對(duì)每個(gè)頂點(diǎn)序列的向量表示進(jìn)行相似度計(jì)算，獲得社團(tuán)劃分相似度。

2.根據(jù)權(quán)利要求1所述的一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，所述步驟1中，頂點(diǎn)序列樣本S＝{s₁,s₂,...,s_n}中頂點(diǎn)序列表示為s＝{v1,v2...,v|s|}。

3.根據(jù)權(quán)利要求2所述的一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，

所述步驟1中的密度函數(shù)定義為：

其中和分別是頂點(diǎn)序列s中所有頂點(diǎn)的內(nèi)部度之和與外部度之和，而α是分辨率參數(shù)，用于控制社團(tuán)的大小；

所述密度函數(shù)還具有密度增益Δf^v_s，所述密度增益Δf^v_s應(yīng)滿足如下公式：

△f_s＝f_s+{v}-f_s

其中符號(hào)s+{v}表示將頂點(diǎn)v移到s后得到的新頂點(diǎn)序列。

4.根據(jù)權(quán)利要求3所述的一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，所述步驟1中獲得頂點(diǎn)序列樣本的具體步驟為：

步驟11：從集合N′(v_|s|)中隨機(jī)選擇一個(gè)頂點(diǎn)v_|s|+1；

步驟12：根據(jù)公式△f_s＝f_s+{v}-f_s計(jì)算Δf_s^v|s|+1；

步驟13：如果Δf_s^v|s|+10，則從集合N′(v_|s|)中刪除v_|s|+1，然后返回步驟11；

步驟14：如果Δf_s^v|s|+10，則將v_|s|+1添加到集合s上，并將v_|s|+1標(biāo)記為當(dāng)前頂點(diǎn)；

其中頂點(diǎn)v_|s|是最后添加的頂點(diǎn)，令最后添加的頂點(diǎn)v_|s|為當(dāng)前頂點(diǎn)；N′(v_|s|)表示當(dāng)前頂點(diǎn)v_|s|的所有不在s中的鄰居頂點(diǎn)集合；重復(fù)步驟11～步驟14直到不能增加頂點(diǎn)序列s的密度為止。

5.根據(jù)權(quán)利要求2所述的一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，所述步驟2中Skip-gram模型通過(guò)最小化以下目標(biāo)函數(shù)來(lái)訓(xùn)練頂點(diǎn)序列樣本：

其中t是窗口大小，v_j是v_i在窗口內(nèi)的上下文網(wǎng)絡(luò)中的頂點(diǎn)表示，以上公式中的概率p(v_j|v_i)定義為

其中Φ(s)表示s的嵌入向量，Φ′(s)表示上下文向量，s表示頂點(diǎn)序列集合。

6.根據(jù)權(quán)利要求1所述的一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法，其特征在于，所述步驟3中對(duì)每個(gè)頂點(diǎn)序列的向量表示進(jìn)行相似度計(jì)算具體包括：對(duì)于網(wǎng)絡(luò)中每個(gè)頂點(diǎn)序列的向量表示計(jì)算它與其他的頂點(diǎn)序列的向量表示的相似程度，具體使用NMI公式計(jì)算相似度。

7.一種具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)裝置，其特征在于，包括：

數(shù)據(jù)收集與處理模塊，用于讀取頂點(diǎn)序列樣本，獲得頂點(diǎn)序列樣本S＝{s₁,s₂,...,s_n}；

數(shù)據(jù)表示學(xué)習(xí)模塊，用于優(yōu)化Skip-gram模型，使用Skip-gram模型來(lái)訓(xùn)練頂點(diǎn)序列樣本S＝{s₁,s₂,...,s_n}，得到每個(gè)頂點(diǎn)序列的向量表示；

相似度計(jì)算模塊，用于對(duì)每個(gè)頂點(diǎn)序列的向量表示進(jìn)行相似度計(jì)算，獲得社團(tuán)劃分相似度。