一種隨機超網絡構建方法
2023-11-07 13:44:57
一種隨機超網絡構建方法
【專利摘要】本發明公開了一種基於多個簡單超圖鄰接矩陣的Tracy-Singh和運算的隨機超網絡構建方法，其主要步驟包括確定生成超網絡集合、計算生成超網絡鄰接矩陣集合、計算生成超網絡節點度分布多項式集合、計算生成超網絡節點超度分布多項式集合、計算生成超網絡超邊度分布多項式集合、計算超網絡的鄰接矩陣、計算隨機超網絡節點度分布多項式、計算隨機超網絡節點超度分布多項式、計算隨機超網絡超邊度分布多項式等。採用本發明構建的隨機超網絡節點度分布、節點超度分布及超邊度分布呈正態分布，具備隨機超網絡的特點，其實質在於生成超網絡正態分布形式的節點度分布、節點超度分布、超邊度分布的線性組合。
【專利說明】一種隨機超網絡構建方法
【技術領域】
[0001]本發明屬於電數字數據處理領域，特別適用於特定功能的數據處理方法，具體涉及一種基於多個簡單生成超網絡鄰接矩陣的Tracy-Singh積運算的超網絡構建方法。
【背景技術】
[0002]在現實生活中，普通的圖或網絡並不能完全刻畫真實世界網絡的各項特性，儘管隨機網絡、小世界網絡、無標度網絡及自相似網絡等網絡模型在描述分析真實複雜網絡中取得了巨大的成功。在研究超大規模的網絡系統時，往往出現網絡中的網絡的問題，在這些情況下，相較於複雜網絡，超網絡可以更完美地描述現實生活中的複雜系統。對超網絡的研究方法主要集中在四個方面:基於圖的研究方法、基於超圖的研究方法、基於變分不等式的研究方法、基於系統科學的研究方法。目前超網絡的研究尚處於起步階段，在概念、模型、性質、應用等方面均有許多需要進一步改進與完善的地方。現階段超網絡的研究主要有如下幾種方法:
[0003](I)基於圖的研究方法
[0004]基於圖的超網絡(Supernetwork)提出於1985年，此種觀點認為超網絡是規模巨大、連接複雜且網絡嵌套網絡的大型網絡。參考文獻[I] ^Supernetworks:Decis1n-Making for the Informat1n Age」(Nagurney A, Dong J.Cheltenham:Edward ElgarPublishing, [M], 2002)認為超網絡是「高於而又超於現存網絡」的網絡，即網絡嵌套網絡，且存在虛擬的節點、邊和流等的網絡。基於圖的超網絡由多種節點與邊組成，子網內與子網間均有邊相連，節點眾多且規模巨大，比複雜網絡更複雜。該類基於圖的超網絡具有網絡嵌套網絡、多層、多級、多維、多屬性、多準則、擁塞性、協調性等特徵。
[0005](2)基於超圖的研究方法
[0006]由於複雜網絡點與邊的同質性，其只能描述兩節點間的關係，無法描述多節點間的合作關係，相關學者據此提出了基於超圖的超網絡(Hypernetwork)。參考文獻[2] 「Graphs and hypergraphs(Berge C.New York:Elsevier[M], 1973)提出了超圖的概念，參考文獻[3] 「Subgraphcentrality in complex networks，，(Estrada E, RodriguesV R.Physical Review E[J]，2005，71 (5): 1_9)認為:凡是可以用超圖表示的網絡就是超網絡。該類基於超圖的超網絡與複雜網絡的區別在於:複雜網絡的邊只連接兩個節點，而超圖網絡的超邊是可包含任意數量節點的集合。參考文獻[4] 「一種超網絡的構建方法」(李天瑞，劉勝久，楊燕，王紅軍[P],CN201410330803.3.西南交通大學.2014-7-14)提出了基於簡單超網絡的鄰接矩陣，採用矩陣運算的策略生成超網絡，此種超網絡的節點度分布、節點超度分布及超邊度分布可以從理論上嚴格計算出來。基於超圖的研究被認為是當前一個較為重要的研究方向。
[0007](3)基於變分不等式的研究方法
[0008]變分不等式最早用於解決機械原理問題與交通平衡問題。參考文獻[5]「A supplychain network equilibrium model」(Nagurney A, Dong J, Zhang D.Transportat1nResearch E[J], 2002, 38(5):281-303)證明所有超網絡模型都可轉換為有限維的變分不等式問題，並用變分不等式和投影算法解決固定條件下的供應鏈超網絡平衡問題。通過構建條件可變的動態系統，並結合Cojocaru等綜合進化變分不等式與Hilbert空間上的投影動力系統，相關學者提出了解決動態系統的修改後的投影算法。目前該方法已用於解決多層、多準則的超網絡模型平衡問題。
[0009](4)基於系統科學的研究方法
[0010]超網絡可以認為是系統的抽象描述，所以系統科學的研究方法同樣適用於超網絡的研究。參考文獻[6] 「組織知識系統的知識超網絡模型及應用」(席運江，黨延忠，廖開際.管理科學學報[J]，2009，12(3):12-21)在分析知識點內在聯繫和知識存儲類型的基礎上，構建了加入物質載體及相關關聯的無權組織知識超網絡模型。基於系統科學的超網絡研究首先研究分析系統、子系統、要素等元素，並構建相應的超網絡、網絡模型；隨後研究網絡間關係、要素間關係、網絡與要素間關係等局部性特徵；最後研究超網絡的整體性、等級結構性等全局特性，得到整個超網絡的特徵以及其它自定義特徵。
[0011](4)其他研究方法
[0012]對超網絡的研究，除常用的基於圖的研究方法、基於超圖的研究方法、基於變分不等式的研究方法、基於系統科學的研究方法外，其他方法也用於超網絡的研究。 參考文獻[7] 「Supernetworks:An introduct1n to the concept and itsapplicat1ns with a specific focus on knowledge supernetworks，， (NagurneyA，Wakolbinger T.1nternat1nal Journal of Knowledge Culture and ChangeManagement [J].2005, 4:1-16)構建了供應鏈與社會網絡結合的超網絡模型，供應鏈網絡和社會網絡均由三層決策者構成，社會網絡中的流是各層之間的關係，供應鏈網絡中的流是產品之間的交易。參考文獻[8] 「一種超網絡演化模型構建及特性分析」(胡楓，趙海興，馬秀娟.中國科學:物理學力學天文學[J]，2013，43:16-22)構建了一種超網絡動態演化模型，從理論上分析了超度分布的特性，並進行了仿真實驗，發現隨著網絡規模的增大，模型出現與已有的增長和優先連接複雜網絡一致的結果。
[0013]總體上講，對超網絡特性的研究仍是現今超網絡研究領域的一大熱點，不可否認的是，儘管對基於圖的研究方法、基於超圖的研究方法、基於變分不等式的研究方法、基於系統科學的研究方法等均有較為成熟的理論與方法，大部分研究也與真實超網絡相符，但仍無法全面反映現實生活中真實超網絡的各種特點，需要進一步深入研究超網絡的各項特性。從多個簡單生成超網絡的鄰接矩陣出發，採用Tracy-Singh和運算研究隨機超網絡模型的構建問題具有重要意義和實際應用價值。
【發明內容】
[0014]為了克服現有技術的上述缺點，本發明公開了一種基於多個簡單超圖鄰接矩陣的Tracy-Singh和運算的隨機超網絡構建方法，其主要步驟包括確定生成超網絡集合、計算生成超網絡鄰接矩陣集合、計算生成超網絡節點度分布多項式集合、計算生成超網絡節點超度分布多項式集合、計算生成超網絡超邊度分布多項式集合、計算超網絡的鄰接矩陣、計算隨機超網絡節點度分布多項式、計算隨機超網絡節點超度分布多項式、計算隨機超網絡超邊度分布多項式等。採用本發明構建的隨機超網絡節點度分布、節點超度分布及超邊度分布呈正態分布，具備隨機超網絡的特點，其實質在於生成超網絡正態分布形式的節點度分布、節點超度分布、超邊度分布的線性組合。而且，對所構建的隨機超網絡應用節點度分布多項式、節點超度分布多項式及超邊度分布多項式等，並採用通常多項式乘法的次數相乘及係數相加的運算可以從理論上嚴格計算出此類隨機超網絡的節點度分布、節點超度分布及超邊度分布。此外，通過選擇並設置不同種類、不同數量、不同順序的生成超網絡可以構建出不同的隨機超網絡。
[0015]本發明解決其技術問題所採用的技術方案是:一種隨機超網絡構建方法，包括如下步驟:
[0016](I)確定生成超網絡集合 Uh = {H1; H2, H3, -,Hi,...};
[0017](2)計算生成超網絡集合Uh中所有超網絡Hi的鄰接矩陣A(Hi)，得到生成超網絡集合 Uh 的鄰接矩陣集合 UA(H) = (A(H1)iA(H2)iA(H3),…，A(Hi),...}:
[0018]在生成超網絡集合Uh中，對於任一具有η個頂點、m條超邊(即m個節點，下同)的生成超網絡H，其鄰接矩陣是nXm的矩陣A(H)nxm，其中對於矩陣中的每一個數據，若頂點i在超邊j(即節點j，下同)中，則有A(H) (i，j) = 1，否則，A(H) (i，j) =0，由於A(H)nxm的每一列代表一條超邊，可以將A(H)nxm視為m個nX I的分塊矩陣A(H)nxi的組合，即有:
[0019]A(H)nxm = [A(H) nA(H)12A(H) y A(H) ir.A(H) Km-DA(H)1J (I)
[0020](3)計算生成超網絡集合Uh中所有超網絡Hi的節點度分布多項式，得到生成超網絡集合Uh的節點度分布多項式集合UMyDD(Hd) = {PolyDD (Hd1)，PolyDD (Hd2)，PolyDD (Hd3), —, PolyDD (Hdi), —}:
[0021]在生成超網絡集合Uh中，任一超網絡H的節點度分布多項式PolyDD(Hd)計算方法為:
【權利要求】
1.一種隨機超網絡構建方法，其特徵在於:包括如下步驟: (1)確定生成超網絡集合Uh={H1; H2, H3, -,Hi,...}; (2)計算生成超網絡集合Uh中所有超網絡Hi的鄰接矩陣A(Hi),得到生成超網絡集合Uh 的鄰接矩陣集合 Ua(H) = (A(H1), A(H2), A(H3),…，A(Hi),...}: 在生成超網絡集合Uh中，對於任一具有η個頂點、m條超邊的生成超網絡H，其鄰接矩陣是nXm的矩陣A(H)nxm，其中對於矩陣中的每一個數據，若頂點i在超邊j中，則有A(H)(i，j) =1，否則，A(H) (i，j) = O;由於A(H)nxm的每一列代表一條超邊，可以將A(H)nxm視SmfnXl的分塊矩陣A(H)nxi的組合，即有: A(H)nxm= [AOD11A OD12AJ ； (3)計算生成超網絡集合Uh中所有超網絡Hi的節點度分布多項式，得到生成超網絡集合 Uh 的節點度分布多項式集合 UMyDD(Hd) = {PoIyDD (Hd1)，PolyDD (Hd2)，PolyDD (Hd3)，…，PolyDD (Hdi),…}: 在生成超網絡集合Uh中，任一超網絡H的節點度分布多項式PolyDD(Hd)計算方法為:
其中，η為超網絡H的超邊數目，Hdi表示第i條超邊包含的頂點數目，即超邊i的度，Nj表示度為j的節點的數目； (4)計算生成超網絡集合Uh中所有超網絡Hi的節點超度分布多項式，得到生成超網絡集合Uh的節點超度分布多項式集合Upo酬M) = {PolyDD (Hhd1)，PolyDD (Hhd2)，PolyDD(Hhd3),…，PolyDD(Hhdi)， 在生成超網絡集合Uh中，任一超網絡H的節點超度分布多項式PolyDD(Hhd)計算方法為:
其中，η為超網絡H的頂點數目，Hdi表示包含第i個頂點的超邊數目，即頂點i的超度，Nj表示超度為j的頂點的數目； (5)計算生成超網絡集合Uh中所有超網絡Hi的超邊度分布多項式，得到生成超網絡集合Uh的超邊度分布多項式集合UMyDD(Hed) = {PolyDD (Hed1)，PolyDD (Hed2)，PolyDD(Hed3), —, PolyDD(Hedi), 在生成超網絡集合Uh中，任一超網絡H的超邊度分布多項式PolyDD(Hed)計算方法為:
其中，η為超網絡H的超邊數目，Hedi表示與第i條超邊鄰接的超邊數目，即超邊i的超邊度，Nj表示超邊度為j -1的超邊的數目； (6)從生成超網絡集合中順次選取k個生成超網絡Ηω、Η(2)、Η(3)、…、H(k—^Hao,記為ΗωΗ⑵H(3)…H(k — DH00，允許重複選取，對每個生成超網絡Ηω對應的鄰接矩陣A (Ηω)按如下方法計算所構建的隨機超網絡的鄰接矩陣Α(1) (Ηω)，其中，I代表運算的次數，Α(1) (Ηω)代表I個生成超網絡對應的鄰接矩陣順次進行運算後得到的一個隨機超網絡的鄰接矩陣: 根據Tracy-Singh和的規則A(k+1)(H(k+1)) = A(k) (H(k)) VA(H)進行計算，得到所構建的隨機超網絡的鄰接矩陣，其中，矩陣A (Bij)mXn及矩陣B (bu)pXq的Tracy-Singh和Amxn V Bpxq定義如下:
AmXn ▽ BpXq 一 AmXn ο ΙηΧη+ΙηΧη ο BpXq ； 其中Inxn表示nXn單位矩陣，ο表示Tracy-Singh積運算dfA(k)(H(k))及A(H)視為分塊的列矩陣進行Tracy-Singh積運算；對於mXη的矩陣A及ρ X q的矩陣B，可先將其分別劃分為Hii Xnj的分塊矩陣Aij及pkX qj分塊矩陣Bkl，再進行Tracy-Singh積運算；矩陣A及矩陣B的Tracy-Singh積A ο B定義如下:A° Bzi (/4"。B) if1 ( (j4jj0Bki) u) ij; 其中，?表示Kronecker積運算； 設Au為矩陣Amxn的第i行第j列HiiXr^階分塊矩陣，Bkl為矩陣Bpxq的第k行第I列PkXq1階分塊矩陣，且有:
了, Inj = m Ση?=η Σα =ρ
k
,I將所有的鄰接矩陣視為I行的分塊矩陣，每個分塊矩陣均是nx I的普通矩陣，即有: K=1.1? =1
矩陣 A(Bij)mxn 及矩陣 Β(Χ」)ρΧ(1 的 Tracy-Singh 積需要用到 Kronecker 積；Kronecker積運算的具體方法為:對任意矩陣AmXn與矩陣BpXq而言,其Kronecker積AmXn BpXq定義如下
? αΛζ …—Α …aA …α'η\、
α?' a] i^22 " '…aI Al…...A11^:...aUbpq■■■aubP,aubP2■■■au,bM;: '■.:::'■.:'■....:'■.:KamAB -■ a^Jftlwnql?,Al...a?A...amA'a Jh...am\
α?Λ,?,,A2...a,n'hlq■■■amnb2]amnbn■■■amlhlq
am]bt...am]bpq ■■.amnbp] amnbp2...卻 採用步驟(6)順次選取k個生成超網絡H(1)、H⑵、H(3)、...、&, —進行Tracy-Singh和而得到的隨機超網絡Ηω可以記為如下形式:
H(k) =V H⑴H⑵H⑶...H(k —A)； (7)按照如下方法計算所構建的隨機超網絡Ηω的節點度分布多項式PolyDD (Hd(1))，其中，I代表Tracy-Singh積運算的次數，PolyDD (Hda))代表I個生成超網絡對應的鄰接矩陣順次進行Tracy-Singh積運算後得到的隨機超網絡節點度分布多項式:
(8)按照如下方法計算所構建的隨機超網絡H(k)的節點超度分布多項式PolyDD (Hhd(1))，其中，I代表Tracy-Singh和運算的次數，PolyDD (Hhdw)代表1個生成超網絡對應的鄰接矩陣順次進行Tracy-Singh和運算後得到的隨機超網絡節點超度分布多項式:
(9)按照如下方法計算所構建的隨機超網絡的超邊度分布多項式PolyDD(Hed(1))，其中，I代表Tracy-Singh和運算的次數，PolyDD(Hedw)代表1個生成超網絡對應的鄰接矩陣順次進行Tracy-Singh和運算後得到的隨機超網絡超邊度分布多項式:
(10)重複步驟(6)至步驟(9)，得到指定頂點數目、指定節點數目或指定超網絡數目的隨機超網絡時，終止操作。
2.根據權利要求1所述的一種隨機超網絡構建方法，其特徵在於:確定生成超網絡集合Uh時，選擇頂點數目η小於等於10且超邊間連接較少的簡單超網絡作為生成超網絡。
3.根據權利要求1所述的一種隨機超網絡構建方法，其特徵在於:對於順次選取k個生成超網絡Ηω、Η⑵、H(3)、…、H(k —^H00而得到的隨機超網絡Ηω，得到的隨機超網絡的頂點數"(幻=Τ^77./,)，超邊數/H(幻=--^("(,?)，其中η (Ηω)表示生成超網絡知)的頂點數，m(H⑴)表示生成超網絡知)的超邊數。
【文檔編號】G06F17/50GK104133952SQ201410350336
【公開日】2014年11月5日 申請日期:2014年7月22日 優先權日:2014年7月22日
【發明者】李天瑞, 劉勝久, 楊燕, 陳紅梅 申請人:西南交通大學