[發(fā)明專利]一種基于隨機(jī)擴(kuò)散的復(fù)雜網(wǎng)絡(luò)生成模型的建立方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210421428.4
• 申請(qǐng)日: 2012-10-29
• 公開（公告）號(hào): CN103023692A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計(jì)）人: 牛建偉;彭井;童超
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 北京永創(chuàng)新實(shí)專利事務(wù)所 11121
• 代理人: 姜榮麗

1.一種基于隨機(jī)擴(kuò)散的復(fù)雜網(wǎng)絡(luò)生成模型的建立方法，其特征在于，包括如下步驟：

步驟1：創(chuàng)建一個(gè)新網(wǎng)絡(luò)G，其結(jié)點(diǎn)集合V僅包含一個(gè)結(jié)點(diǎn)v₁，邊集合E為空集；

步驟2：設(shè)變量i＝2，準(zhǔn)備向網(wǎng)絡(luò)G中加入結(jié)點(diǎn)v_i；

步驟3：取得當(dāng)前網(wǎng)絡(luò)G中的結(jié)點(diǎn)集合V；

步驟4：將v_i加入網(wǎng)絡(luò)G的結(jié)點(diǎn)集合V；

步驟5：按區(qū)間[0,1]上的均勻分布生成一個(gè)隨機(jī)數(shù)num；

步驟6：若num≤p_host，等概率隨機(jī)從結(jié)點(diǎn)集合V中選取一個(gè)節(jié)點(diǎn)begin，并從begin開始執(zhí)行結(jié)點(diǎn)v_i的隨機(jī)擴(kuò)散過程，隨機(jī)擴(kuò)散結(jié)束后轉(zhuǎn)步驟5執(zhí)行；若num＞p_host，設(shè)置變量i＝i+1，若i＞n，轉(zhuǎn)步驟7執(zhí)行，否則若i≤n，轉(zhuǎn)步驟3執(zhí)行；其中p_host為一個(gè)新加入網(wǎng)絡(luò)的結(jié)點(diǎn)執(zhí)行所述的隨機(jī)擴(kuò)散過程的概率；n表示模型輸出的網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)；

步驟7：輸出生成的網(wǎng)絡(luò)G。

2.根據(jù)權(quán)利要求1所述的一種基于隨機(jī)擴(kuò)散的復(fù)雜網(wǎng)絡(luò)生成模型的建立方法，其特征在于，步驟6中所述的從結(jié)點(diǎn)begin開始的結(jié)點(diǎn)v_i隨機(jī)擴(kuò)散過程，具體包括如下步驟：

步驟6.1：設(shè)變量frontier為一空隊(duì)列，設(shè)變量visited為一空集合；

步驟6.2：將結(jié)點(diǎn)begin分別加入隊(duì)列frontier和集合visited；

步驟6.3：將邊(v_i,begin)加入網(wǎng)絡(luò)G，并標(biāo)記其時(shí)間戳為i；

步驟6.4：若隊(duì)列frontier不為空，則轉(zhuǎn)步驟6.5執(zhí)行，否則結(jié)束隨機(jī)擴(kuò)散過程；

步驟6.5：從隊(duì)列frontier彈出一個(gè)結(jié)點(diǎn)，記為結(jié)點(diǎn)host；

步驟6.6：設(shè)變量neighbors為結(jié)點(diǎn)host在網(wǎng)絡(luò)G中的所有鄰接結(jié)點(diǎn)集合；

步驟6.7：根據(jù)集合neighbors和集合visited，隨機(jī)選取即將擴(kuò)散到的結(jié)點(diǎn)集合，記為nodes；

步驟6.8：對(duì)于nodes中的每個(gè)結(jié)點(diǎn)nd，向網(wǎng)絡(luò)G中添加邊(v_i,nd)G，并標(biāo)記其時(shí)間戳為i；將結(jié)點(diǎn)nd分別加入隊(duì)列frontier和集合visited。轉(zhuǎn)步驟6.4執(zhí)行。

3.根據(jù)權(quán)利要求2所述的一種基于隨機(jī)擴(kuò)散的復(fù)雜網(wǎng)絡(luò)生成模型的建立方法，其特征在于，步驟6.7中所述的根據(jù)neighbors和visited隨機(jī)選取即將擴(kuò)散的結(jié)點(diǎn)集合，具體包括如下步驟：

步驟6.7.1：若集合neighbors為空，則返回空集；否則轉(zhuǎn)步驟6.7.2執(zhí)行；

步驟6.7.2：設(shè)變量count＝0；

步驟6.7.3：按區(qū)間[0,1]上的均勻分布生成一個(gè)隨機(jī)數(shù)，記為t；

步驟6.7.4：若t≤p_frnd，則設(shè)變量count＝count+1，轉(zhuǎn)步驟6.7.3執(zhí)行；否則轉(zhuǎn)步驟6.7.5執(zhí)行；其中，p_frnd為模型的參數(shù)，表示在確定步驟6.7.6中隨機(jī)選取的結(jié)點(diǎn)總數(shù)時(shí)，還需多選擇一個(gè)結(jié)點(diǎn)的概率；

步驟6.7.5：設(shè)變量candidate為集合neighbors和集合visited的差集，即neighbors-visited；

步驟6.7.6：從集合candidate中等概率隨機(jī)選取min{count,|candidate|}個(gè)結(jié)點(diǎn)，返回已選取的結(jié)點(diǎn)。