[發(fā)明專利]一種基于鄰接矩陣的復(fù)雜網(wǎng)絡(luò)構(gòu)建方法

在審

• 申請?zhí)枺?/td>: 201410606280.0
• 申請日: 2014-10-31
• 公開（公告）號(hào): CN104376156A
• 公開（公告）日: 2015-02-25
• 發(fā)明（設(shè)計(jì)）人: 李天瑞;劉勝久;珠杰;王紅軍
• 申請（專利權(quán)）人: 西南交通大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50
• 代理公司: 成都信博專利代理有限責(zé)任公司 51200
• 代理人: 張澎

1.一種基于鄰接矩陣的復(fù)雜網(wǎng)絡(luò)構(gòu)建方法，確定生成網(wǎng)絡(luò)、計(jì)算生成網(wǎng)絡(luò)鄰接矩陣、計(jì)算生成網(wǎng)絡(luò)度分布多項(xiàng)式、計(jì)算復(fù)雜網(wǎng)絡(luò)的鄰接矩陣、計(jì)算復(fù)雜網(wǎng)絡(luò)的度分布多項(xiàng)式處理步驟構(gòu)建復(fù)雜網(wǎng)絡(luò)，包括如下步驟：

(1)確定生成網(wǎng)絡(luò)G；

(2)計(jì)算生成網(wǎng)絡(luò)G的鄰接矩陣A(G)：

對于具有n個(gè)節(jié)點(diǎn)的生成網(wǎng)絡(luò)G，其鄰接矩陣A(G)是n×n的方陣，其中對于方陣中的每一個(gè)數(shù)據(jù)，若節(jié)點(diǎn)i與節(jié)點(diǎn)j相鄰，則有A(G)(i,j)＝1，否則，A(G)(i,j)＝0；若生成網(wǎng)絡(luò)G的鏈路數(shù)為m，則鄰接矩陣A(G)中1的個(gè)數(shù)也為m，且生成網(wǎng)絡(luò)的網(wǎng)絡(luò)密度

(3)根據(jù)生成網(wǎng)絡(luò)G的度分布確定生成網(wǎng)絡(luò)G的度分布多項(xiàng)式Poly(G)：

Poly(G)=Σi=1nxDi=Σj=1∞Njxj---(1)]]>

式中，n為節(jié)點(diǎn)數(shù)目，D_i表示第i個(gè)節(jié)點(diǎn)的度，N_j表示度為j的節(jié)點(diǎn)的數(shù)目；

(4)按如下方法計(jì)算所構(gòu)建的網(wǎng)絡(luò)的鄰接矩陣A^(l)(G^(l))，其中，l代表進(jìn)行Kronecker和運(yùn)算或Kronecker積運(yùn)算的次數(shù)，A^(l)(G^(l))代表對A(G)進(jìn)行l(wèi)次Kronecker和運(yùn)算和/或Kronecker積運(yùn)算后得到復(fù)雜網(wǎng)絡(luò)的鄰接矩陣：

若矩陣A^(j)(G^(j))與A(G)采用Kronecker和運(yùn)算進(jìn)行運(yùn)算，則有：

A(j+1)(G(j+1))=A(j)(G(j))⊕A(G)---(2)]]>

若矩陣A^(j)(G^(j))與A(G)采用Kronecker積運(yùn)算進(jìn)行運(yùn)算，則有：

A(j+1)(G(j+1))=A(j)(G(j))⊗A(G)---(3)]]>

其中，矩陣A(a_ij)_m×m及矩陣B(b_ij)_n×n的Kronecker和定義如下：

Am×m⊕Bn×n=Am×m⊗In×n+Im×m⊗Bn×n---(4)]]>

其中，I_n×n表示n×n單位矩陣，表示Kronecker和運(yùn)算，表示Kronecker積運(yùn)算，可以看出Kronecker和運(yùn)算需要用到Kronecker積運(yùn)算；

對任意矩陣P_p×p與矩陣Q_q×q而言，其Kronecker積定義如下：

為方便書寫，采用此方法對生成網(wǎng)絡(luò)G對應(yīng)的鄰接矩陣進(jìn)行k次Kronecker積運(yùn)算或Kronecker和運(yùn)算而得到的鄰接矩陣對應(yīng)的復(fù)雜網(wǎng)絡(luò)G^(k)可以記為如下形式：

G(k)＝⊙₍₁₎⊙₍₂₎⊙₍₃₎…⊙_(k-1)⊙_(k)G??(6)

其中，⊙表示或

特別的，在特殊情況下，若只采用一種運(yùn)算，則有：

基于一個(gè)生成網(wǎng)絡(luò)G的k次Kronecker積運(yùn)算而得到的復(fù)雜網(wǎng)絡(luò)可以記為：

G(k)=⊗kG---(7)]]>

基于一個(gè)生成網(wǎng)絡(luò)G的k次Kronecker和運(yùn)算而得到的復(fù)雜網(wǎng)絡(luò)可以記為：

G(k)=⊕kG---(8)]]>

；

(5)按照如下方法計(jì)算所構(gòu)建的新的復(fù)雜網(wǎng)絡(luò)的度分布PolyDD(G^(l))，其中，l代表Kronecker積運(yùn)算或Kronecker和運(yùn)算的次數(shù)，PolyDD(G^(l))代表對生成網(wǎng)絡(luò)進(jìn)行l(wèi)次Kronecker積運(yùn)算和/或Kronecker和運(yùn)算后得到的新的復(fù)雜網(wǎng)絡(luò)度分布多項(xiàng)式：

若矩陣A^(j)(G^(j))與A(G)采用Kronecker和運(yùn)算進(jìn)行運(yùn)算，則有：

PolyDD(G(k+1))=KronSum(Poly(G(k)),Poly(G))=KronSum(Σi=1∞Ni(k)xi,Σj=1∞Njxj)=Σi=1∞Σj=1∞Ni(k)Njxi+j(i,j=1,2,3,...)---(9)]]>

若矩陣A^(j)(G^(j))與A(G)采用Kronecker積運(yùn)算進(jìn)行運(yùn)算，則有：

PolyDD(G(k+1))=KronPro(Poly(G(k)),Poly(G))=KronPro(Σi=1∞Ni(k)xi,Σj=1∞Njxj)=Σi=1∞Σj=1∞Ni(k)Njxij(i,j=1,2,3,...)---(10)]]>

(6)重復(fù)步驟(4)及步驟(5)，得到指定節(jié)點(diǎn)數(shù)目、指定鏈路數(shù)目或指定生成網(wǎng)絡(luò)數(shù)目的復(fù)雜網(wǎng)絡(luò)時(shí)，終止操作。