[發(fā)明專利]動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)劃分方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201611074435.6
• 申請(qǐng)日: 2016-11-29
• 公開（公告）號(hào): CN106780058A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 時(shí)巖;趙靜文;陳濱;陳山枝
• 申請(qǐng)（專利權(quán)）人: 北京郵電大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00;H04L12/24
• 代理公司: 北京同立鈞成知識(shí)產(chǎn)權(quán)代理有限公司11205
• 代理人: 張洋,黃健

技術(shù)領(lǐng)域

本發(fā)明實(shí)施例涉及網(wǎng)絡(luò)科學(xué)技術(shù)領(lǐng)域，尤其涉及一種動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)劃分方法及裝置。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)普遍存在于現(xiàn)實(shí)世界中，具有復(fù)雜拓?fù)浣Y(jié)構(gòu)和復(fù)雜節(jié)點(diǎn)行為，如計(jì)算機(jī)網(wǎng)絡(luò)，生物網(wǎng)絡(luò)，社會(huì)關(guān)系網(wǎng)絡(luò)等等。而研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的最常用的方法是模塊化和社團(tuán)結(jié)構(gòu)。社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行不同的分組，而它們往往具有組內(nèi)節(jié)點(diǎn)連接比較稠密，組間節(jié)點(diǎn)連接比較稀疏的性質(zhì)。通過社團(tuán)結(jié)構(gòu)探測(cè)可以學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)功能、分析網(wǎng)絡(luò)特性、尋找隱藏模式、進(jìn)行鏈路預(yù)測(cè)和學(xué)習(xí)網(wǎng)絡(luò)演化等。研究表明真實(shí)網(wǎng)絡(luò)并不完全是無權(quán)網(wǎng)絡(luò)，而是網(wǎng)絡(luò)節(jié)點(diǎn)間存在著不同強(qiáng)度的耦合，即加權(quán)網(wǎng)絡(luò)，比如人與人之間關(guān)系有緊密和疏遠(yuǎn)，航空網(wǎng)絡(luò)中機(jī)場(chǎng)間的客流量有大小。加權(quán)網(wǎng)絡(luò)能夠?qū)?shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的動(dòng)力學(xué)演化特性提供更加真實(shí)細(xì)致的描述。

現(xiàn)有加權(quán)網(wǎng)絡(luò)的社團(tuán)檢測(cè)算法主要針對(duì)靜態(tài)網(wǎng)絡(luò)，例如層次聚類算法、邊聚類系數(shù)算法等等。由于靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)集和邊集是固定不變的，因此現(xiàn)有社團(tuán)檢測(cè)算法忽略網(wǎng)絡(luò)的時(shí)間特性，將網(wǎng)絡(luò)建模成一個(gè)靜態(tài)圖，在靜態(tài)圖的基礎(chǔ)上對(duì)社團(tuán)進(jìn)行檢測(cè)。

而實(shí)際上真實(shí)的網(wǎng)絡(luò)通常是結(jié)構(gòu)隨時(shí)間變化的動(dòng)態(tài)網(wǎng)絡(luò)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的網(wǎng)絡(luò)性質(zhì)都會(huì)隨著時(shí)間發(fā)生變化。所以社團(tuán)結(jié)構(gòu)也可能隨時(shí)間的推移而發(fā)生變化。動(dòng)態(tài)網(wǎng)絡(luò)的規(guī)模往往數(shù)倍于傳統(tǒng)的靜態(tài)網(wǎng)絡(luò)，且網(wǎng)絡(luò)無時(shí)不刻不在產(chǎn)生新的數(shù)據(jù)。因此，如何對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)，獲得穩(wěn)定社團(tuán)劃分結(jié)果是當(dāng)前動(dòng)態(tài)網(wǎng)絡(luò)的研究重點(diǎn)。

發(fā)明內(nèi)容

本發(fā)明提供一種動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)劃分方法及裝置，以實(shí)現(xiàn)對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)，獲得穩(wěn)定社團(tuán)劃分結(jié)果。

本發(fā)明的一個(gè)方面是提供一種動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)劃分方法，包括：

獲取動(dòng)態(tài)網(wǎng)絡(luò)分別在至少兩個(gè)時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所述動(dòng)態(tài)網(wǎng)絡(luò)包括多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)屬于一個(gè)社團(tuán)；

分別以所述多個(gè)節(jié)點(diǎn)中的每一個(gè)節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，遍歷每個(gè)目標(biāo)節(jié)點(diǎn)，執(zhí)行以下步驟：

在每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，計(jì)算所述目標(biāo)節(jié)點(diǎn)分別與其相鄰的每個(gè)節(jié)點(diǎn)的模塊度增量，所述目標(biāo)節(jié)點(diǎn)與其相鄰的節(jié)點(diǎn)的模塊度增量為所述目標(biāo)節(jié)點(diǎn)移動(dòng)到所述相鄰的節(jié)點(diǎn)所屬的社團(tuán)時(shí)產(chǎn)生的模塊度增量；

根據(jù)每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的權(quán)重，以及每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，所述目標(biāo)節(jié)點(diǎn)與同一個(gè)相鄰節(jié)點(diǎn)的模塊度增量，計(jì)算所述目標(biāo)節(jié)點(diǎn)與同一個(gè)相鄰節(jié)點(diǎn)的平均模塊度增量；

比較所述目標(biāo)節(jié)點(diǎn)與各個(gè)相鄰節(jié)點(diǎn)的平均模塊度增量；

若所述目標(biāo)節(jié)點(diǎn)與所述相鄰節(jié)點(diǎn)的平均模塊度增量最大，且最大的所述平均模塊度增量為正值，則在每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，將所述目標(biāo)節(jié)點(diǎn)移動(dòng)到所述相鄰節(jié)點(diǎn)所屬的社團(tuán)中；

遍歷每個(gè)目標(biāo)節(jié)點(diǎn)結(jié)束后，分別以每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的每個(gè)社團(tuán)作為目標(biāo)節(jié)點(diǎn)，重復(fù)遍歷每個(gè)目標(biāo)節(jié)點(diǎn)，直到每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的任意兩個(gè)社團(tuán)均無法繼續(xù)合并為止。

進(jìn)一步的，所述獲取動(dòng)態(tài)網(wǎng)絡(luò)分別在至少兩個(gè)時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，包括：

獲取動(dòng)態(tài)網(wǎng)絡(luò)在一時(shí)間段內(nèi)至少兩個(gè)時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

所述每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的權(quán)重為所述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)應(yīng)的時(shí)刻在所述時(shí)間段內(nèi)的時(shí)間順序，與所述時(shí)間段內(nèi)獲取到的所述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的總數(shù)的比值。

進(jìn)一步的，所述目標(biāo)節(jié)點(diǎn)與同一個(gè)相鄰節(jié)點(diǎn)的平均模塊度增量，根據(jù)公式(1)確定：

其中，ΔQ_avg表示所述平均模塊度增量，N表示所述時(shí)間段內(nèi)的N個(gè)時(shí)刻，I表示所述N個(gè)時(shí)刻中的第I個(gè)時(shí)刻，w_I表示第I個(gè)時(shí)刻對(duì)應(yīng)的所述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的權(quán)重，ΔQ_I表示在第I個(gè)時(shí)刻對(duì)應(yīng)的所述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，所述目標(biāo)節(jié)點(diǎn)與所述同一個(gè)相鄰節(jié)點(diǎn)的模塊度增量。

進(jìn)一步的，所述目標(biāo)節(jié)點(diǎn)移動(dòng)到所述同一個(gè)相鄰節(jié)點(diǎn)所屬的社團(tuán)時(shí)產(chǎn)生的模塊度增量，根據(jù)公式(2)確定：

其中，C表示所述同一個(gè)相鄰節(jié)點(diǎn)所屬的社團(tuán)，W_c表示社團(tuán)C內(nèi)部所有連邊的權(quán)重和，S_c表示與社團(tuán)C中的節(jié)點(diǎn)相連的連邊的權(quán)重和，S_i表示與所述目標(biāo)節(jié)點(diǎn)i相連的連邊的權(quán)重和，S_i,in表示連接所述目標(biāo)節(jié)點(diǎn)i與社團(tuán)C中的節(jié)點(diǎn)的連邊的權(quán)重和，W表示所述動(dòng)態(tài)網(wǎng)絡(luò)中所有邊的權(quán)重和。

進(jìn)一步的，所述分別以每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的每個(gè)社團(tuán)作為目標(biāo)節(jié)點(diǎn)，包括：在每個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，將連接兩個(gè)社團(tuán)之間的連邊的權(quán)重和作為兩個(gè)目標(biāo)節(jié)點(diǎn)連邊的權(quán)重，所述社團(tuán)內(nèi)部所有連邊的權(quán)重和作為所述目標(biāo)節(jié)點(diǎn)上的環(huán)路的權(quán)重。