(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院， 甘肅 蘭州 730070)

數(shù)學(xué)的拓撲圖是編碼關(guān)系結(jié)構(gòu)的一種自然的表示，這種關(guān)系結(jié)構(gòu)在許多領(lǐng)域都會遇到.通過圖結(jié)構(gòu)數(shù)據(jù)定義的計算被廣泛應(yīng)用于各領(lǐng)域，計算生物學(xué)和化學(xué)的分子分析，自然語言理解的知識圖或圖結(jié)構(gòu)解析的分析等等.

1 研究背景、術(shù)語、定義

1.1 拓撲圖是各種學(xué)科的通用語言之一

當(dāng)今世界的數(shù)不清的事物關(guān)聯(lián)組合都可以用拓撲圖來表示或描繪，拓撲圖屬于數(shù)學(xué)的一個叫做圖論的分支.圖1、圖2、圖3和圖4是拓撲圖應(yīng)用的例子.

圖1 拓撲圖的例子Fig.1 Examples of topological graphs

(a) 泛著色泛結(jié)構(gòu)拓撲圖；(b) 飽和烷烴拓撲圖；(c) 物理關(guān)聯(lián)知識拓撲圖

圖2 英特網(wǎng)絡(luò)

圖3 左右主導(dǎo)的大腦網(wǎng)絡(luò)

圖4 引自文獻[10]的一個生物網(wǎng)絡(luò)Fig.4 A biological network cited from Ref.[10]

通常，全體網(wǎng)絡(luò)可分為動態(tài)網(wǎng)絡(luò) (dynamic networks) 和非動態(tài)網(wǎng)絡(luò).非動態(tài)網(wǎng)絡(luò)是在一個時間段內(nèi)沒有節(jié)點和連線數(shù)目的變化，如鐵路、公路網(wǎng)等；而動態(tài)網(wǎng)絡(luò)的節(jié)點和連線的數(shù)目隨時間而變，如Internet，WWW，生物代謝網(wǎng)，物聯(lián)網(wǎng)等.網(wǎng)絡(luò)研究中的網(wǎng)絡(luò)圖是一種圖解模型，形狀如同網(wǎng)絡(luò)，故稱為網(wǎng)絡(luò)圖，他們均是拓撲圖.網(wǎng)絡(luò)圖是由作業(yè) (箭線)、事件 (節(jié)點) 和路線三個因素組成的.Pavlopoulos 等[1]指出：“圖論的 (隨機的或非隨機的) 圖和有向圖自然而生動地被用來作為理解的模型以及模擬復(fù)雜的網(wǎng)絡(luò).”更多的例子指明拓撲圖是各種學(xué)科的通用語言之一.

1.2 人工智能研究中的拓撲圖應(yīng)用

2018年6月，Battaglia等[2]發(fā)表關(guān)于圖網(wǎng)絡(luò)的論文.孫茂松團隊[3]2018年12月綜述了關(guān)于圖神經(jīng)網(wǎng)絡(luò)的研究.2019年1月，俞士綸團隊[4]發(fā)表了圖神經(jīng)網(wǎng)絡(luò)研究的綜述.

在機器學(xué)習(xí)和人工智能中，許多有關(guān)系推理能力的方法都使用關(guān)系歸納偏置(relational inductive biase).Battaglia 等在文獻[2]中提出了一個新的人工智能模塊——圖網(wǎng)絡(luò) (graph network).圖網(wǎng)絡(luò)具有強大的關(guān)系歸納偏置，是對以前各種對圖進行操作的神經(jīng)網(wǎng)絡(luò)方法的推廣和擴展，為操縱結(jié)構(gòu)化知識和生成結(jié)構(gòu)化行為提供了一個直接的界面.Battaglia 等還討論了圖網(wǎng)絡(luò)如何支持關(guān)系推理和組合泛化 (combinatorialGeneralization)，探討了如何在深度學(xué)習(xí)結(jié)構(gòu) (例如，全連接層、卷積層和遞歸層) 中，使用關(guān)系歸納偏置，促進對實體、關(guān)系，以及組成它們的規(guī)則進行學(xué)習(xí)，為更復(fù)雜、可解釋和靈活的推理模式打下基礎(chǔ).圖網(wǎng)絡(luò)已經(jīng)被用來分析自然語言3D場景生物學(xué)等實際應(yīng)用場景.

Li等[5]針對圖結(jié)構(gòu)對象的檢索與匹配這一具有挑戰(zhàn)性的問題發(fā)表了關(guān)于圖匹配網(wǎng)絡(luò)(Graph Matching Networks)的文章，研究了圖結(jié)構(gòu)對象的相似性學(xué)習(xí)(similarity learning)問題，演示了如何訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)在向量空間中生成圖嵌入，從而實現(xiàn)高效的相似性推理，提出了一種新的圖匹配網(wǎng)絡(luò)模型，通過一種新的基于注意力的跨圖匹配機制，對圖對進行聯(lián)合推理，計算出一對圖之間的相似度評分.

張鈸(1)清華大學(xué)張鈸院士在2018全球人工智能與機器人峰會大會報告“走向真正的人工智能”(Towards A Real Artifitial Intelligence)，CCF-GAIR 2018年6月15日，深圳.主張“有理解的人工智能”，他指出，由于一種人工智能的基本方法是用符號模型來模擬理性行為，符號模型可以表達信息的內(nèi)容，所以它是在一個語義的符號空間里頭，離散符號表示使得很多數(shù)學(xué)工具用不上.另一種基本方法是模擬感性行為，用的是特征空間的向量，可以把優(yōu)化工具、概率統(tǒng)計工具等數(shù)學(xué)工具用上.

李立浧(2)2018鹽城綠色智慧能源大會李立浧院士主題演講“智能電網(wǎng)與能源網(wǎng)的融合”.首次提出了“透明電網(wǎng)”的定義是信息技術(shù)、計算機技術(shù)、數(shù)據(jù)通信技術(shù)、傳感器技術(shù)、電子控制技術(shù)、自動控制理論、運籌學(xué)、人工智能、互聯(lián)網(wǎng)等有效地綜合運用于電力系統(tǒng).通過在電網(wǎng)中安裝多個小微智能傳感器，使每一個設(shè)備都處于數(shù)據(jù)影像下.形成小微智能傳感器的傳感.智能設(shè)備和設(shè)備的智能化，智能二次系統(tǒng)，強大的軟件平臺、大數(shù)據(jù)平臺、小微燃料獲取的自由化，這些就構(gòu)成了整個透明電網(wǎng).透明電網(wǎng)會徹底改變電網(wǎng)的信息形態(tài)，整個電網(wǎng)系統(tǒng)都將是智能的、透明的.

1.3 運用圖論理論和技術(shù)到網(wǎng)絡(luò)研究中

Newman等[6]指出：“純圖論是美好而深刻的，但它與現(xiàn)實世界中的網(wǎng)絡(luò)并不是緊密相關(guān)的.應(yīng)用圖論，顧名思義，則更關(guān)注現(xiàn)實世界的網(wǎng)絡(luò)問題，但其方法是面向設(shè)計和工程”.著名的網(wǎng)絡(luò)研究論著[1，7-9]均強調(diào)并使用了圖論技術(shù).

利用圖論的知識來研究網(wǎng)絡(luò)的文章數(shù)量龐大，涉及眾多的網(wǎng)絡(luò)學(xué)科分支，以個人之力綜合網(wǎng)絡(luò)研究是極其困難的.拋開實際應(yīng)用網(wǎng)絡(luò)，如電力網(wǎng)、物流網(wǎng)、社交網(wǎng)、財經(jīng)網(wǎng)等，本文側(cè)重動態(tài)網(wǎng)絡(luò)的拓撲性質(zhì)、構(gòu)造，聚焦新概念、新問題，捕捉新對象、新技術(shù)、新理論，力圖接近網(wǎng)絡(luò)研究的主流，為網(wǎng)絡(luò)研究提供有價值的參考.具有圖論基礎(chǔ)知識的讀者理解本文的內(nèi)容是不太困難的.

2 無標(biāo)度圖、集散點、崩潰度、物聯(lián)網(wǎng)定義

2.1 無標(biāo)度圖定義

稱函數(shù)f(x)為無標(biāo)度函數(shù) (scale-free function)，如果它滿足f(ax)=g(a)f(x)，例如，f(x)=cxγ，則有

f(ax)=c(ax)γ=xγf(x).

2005 年，Li 等在文獻[13]中首次提出建立無標(biāo)度圖理論，他們利用度-度相關(guān)系數(shù)，給出無標(biāo)度圖的定義：n個頂點的圖G有定標(biāo)度序列d=(d1,d2,…,dn)，如果對1≤k≤ns≤n，定標(biāo)度序列d滿足形如

(1)

的冪率規(guī)模秩關(guān)系，其中常數(shù)c>0，α>0.定義圖G的s-度量為

(2)

注意到，對動態(tài)網(wǎng)絡(luò)來說，精確量化s(G)是困難的，這就使得判斷一個圖是否為無標(biāo)度圖沒有基于圖的基本參數(shù)、可操作的量化標(biāo)準(zhǔn).從動態(tài)的角度出發(fā)，運用文獻[14]中的冪率度分布 (power law degree distribution)，給出下面的無標(biāo)度圖定義：

定義1[15-16]一個動態(tài)網(wǎng)絡(luò) (dynamic network) 是N(t)=(p(u,k,t),G(t)) (t∈[a,b])，其中p(u,k,t)是一個新進入網(wǎng)絡(luò)N(t)的節(jié)點u與其他k個節(jié)點隨機連接的概率，G(t)是網(wǎng)絡(luò)N(t)的連通拓撲結(jié)構(gòu) (connected topological structure).對t∈[a,b]，若概率p(u,k,t)服從冪率度分布β(t)k-α，其中β(t)>0，則稱G(t)為無標(biāo)度圖，網(wǎng)絡(luò)N(t)為無標(biāo)度網(wǎng)絡(luò) (scale-free network).

定義1的一個例子在圖5中給出，但是這個定義仍然是利用冪率度分布來定義無標(biāo)度圖的，在實際應(yīng)用中也是不容易操作的.因此，無標(biāo)度圖的定義仍需研究、探討.

圖5 無標(biāo)度網(wǎng)絡(luò)Fig.5 A scale-free network

2.2 集散點定義

注意到，無標(biāo)度網(wǎng)絡(luò)N(t)中的無標(biāo)度圖G(t)的階數(shù)和邊數(shù)一般情形下不是一個常數(shù)，這是因為不斷地有節(jié)點進入或移出網(wǎng)絡(luò)N(t)，而且每個節(jié)點的連線數(shù)目在時間區(qū)間[a,b]內(nèi)也會變化，從而說明圖G(t)不等同于圖論中的圖，稱它為動態(tài)圖 (dynamic graph).但對固定時刻t0，G(t0)就是圖論中的拓撲圖.對t∈[a,b]，G(t)的一個節(jié)點u的度是與它所連接的線的數(shù)目，記為degG(u,t)，且degG(u,t)>0.如果degG(u,t)等于正常數(shù)c，則說u是穩(wěn)定點 (stable node).對t10，當(dāng)G(t0)的特性和結(jié)構(gòu)確定后，就可以用它來刻畫或估測每一個G(t)的結(jié)構(gòu)及其特性，t∈(t0-δ,t0+δ).為研究無標(biāo)度網(wǎng)絡(luò)N(t) (t∈[a,b]) 中不同類型的節(jié)點，尋找N(t)的“核圖”，給出如下的概念：

定義3[16-18]稱連通圖G的一個頂點子集S?V(G)L(G)為平衡集 (balanced set)，若對圖G的任何2棵生成樹Ti和Tj，總有

|L(Ti)|-|S∩L(Ti)|=|L(Tj)|-|S∩L(Tj)|

(3)

當(dāng)S≠V(G)時，稱S為真平衡集 (proper balanced set).

有關(guān)網(wǎng)絡(luò)模型中生成樹的構(gòu)造算法、生成樹的數(shù)目等結(jié)論在文獻[19-26]和文獻[16]中均有研究報道.特別地，文獻[16]介紹了PRESUB graph-算法，它是BREADTH-FIRST SEARCH algorithm的一個改進，PRESUB graph-算法可以找到網(wǎng)絡(luò)模型中具有最多葉子的生成樹.

2.3 網(wǎng)絡(luò)崩潰度定義

在文獻[27]中，Yao等為了刻畫網(wǎng)絡(luò)的堅韌性，給出了網(wǎng)絡(luò)模型崩潰的定義.一個連通圖H的頂點子集X使得刪點圖H-X不連通，刪點圖H-X有ω(H-X)>1個分支，稱頂點子集X為連通圖H的頂點割 (cut set).

定義5[15]在網(wǎng)絡(luò)模型N(t)=(p(u,k,t),u(t),UG) (t∈[a,b])中，如果它的邊集E(G(t))的一個子集E*使得刪邊網(wǎng)絡(luò)模型N(t)-E*不連通，W1,W2,…,Wm是刪邊圖N(t)-E*的分支，網(wǎng)絡(luò)模型N(t)的邊崩潰度 (edge-collapsed rank) 定義為

(4)

(5)

顯然有0≤Ce(N(t)-E*)<1和0≤Cv(N(t)-V*)<1.實驗表明，可以用邊崩潰度和點崩潰度來描述網(wǎng)絡(luò)模型N(t)的拓撲性質(zhì)：(i)當(dāng)Ce(N(t)-E*)和Cv(N(t)-V*)較大時，N(t)的連通性較高，穩(wěn)定性也高；(ii) 當(dāng)Ce(N(t)-E*)和Cv(N(t)-V*)較小時，N(t)的崩潰性較??；(iii) 當(dāng)Ce(N(t)-E*)和Cv(N(t)-V*)接近1時，N(t)的穩(wěn)定性高，此時，N(t)離無標(biāo)度性也遠.經(jīng)過實驗，下面定義6中的真優(yōu)化割集在網(wǎng)絡(luò)模型的崩潰性研究中有著重要的地位.

定義6[15]稱連通圖H的一個頂點割B*為真優(yōu)化割集 (proper optimal cut set, POC-set)，如果它滿足：

(i) 對任何頂點子集X?V(H)，總有分支數(shù)ω(H-B*)≥ω(H-X)；

(ii) 對任何頂點割Y?V(H)，且2個分支數(shù)ω(H-Y)=ω(H-B*)，總有 |B*|≤|Y|；

(iii) 分支數(shù)ω(H-B*)滿足 |B*|≤ω(H(B*).

Yao等從連通圖H的生成樹入手，來尋找連通圖H的真優(yōu)化割集.顯然，這是一個純圖論問題.

2.4 物聯(lián)網(wǎng)定義

Yao 等在文獻[26]中用圖論的技術(shù)給出物聯(lián)網(wǎng)模型的定義.

定義7一個物聯(lián)網(wǎng)的拓撲功能網(wǎng)絡(luò) (topological network) 定義為Io(t)=(d(p,u,t),G(t),UD) (t∈[a,b]).拓撲功能網(wǎng)絡(luò)Io(t)中的每個頂點u的度數(shù)為degIo(u)=d(p,u,t)s(u,t)，其中d(p,u,t)叫做連接函數(shù) (linking function)，是t時刻在確定的規(guī)則 (rule)p下與頂點u關(guān)聯(lián)的邊數(shù)目，值為0，1的s(u,t)是活動函數(shù)(active function)，當(dāng)s(u,t)=0，說頂點u是睡眠的，當(dāng)s(u,t)=1，說頂點u是活動的.一條邊uv是物聯(lián)網(wǎng)Io(t)的顯邊 (expressed edge)，若s(u,t)=s(v,t)=1，此外，稱它為隱邊 (implied edge)；一條路P=u1u2…un上的每個頂點ui均是活動的；G(t)是拓撲圖 (topological graph)，G(a)是初始圖，UD是拓撲功能網(wǎng)絡(luò)Io(t)的底圖 (underlying graph)，它包含了拓撲功能網(wǎng)絡(luò)在時間段[a,b]內(nèi)所有的頂點和邊.

拓撲網(wǎng)絡(luò)Io(t)是連通的，也就是說它的任何一對頂點被一條由活動邊構(gòu)成的路連接.如果拓撲網(wǎng)絡(luò)Io(t)是無標(biāo)度的，規(guī)則p服從冪律度分布p～k-α.通常，一個物流網(wǎng) (logistic network) 是物理網(wǎng)絡(luò)(physical network)和信息網(wǎng)(information network)的合成.

定義8一個物聯(lián)網(wǎng)的數(shù)據(jù)功能網(wǎng)絡(luò) (data functional network)定義為Fu(t)=(g(u,t),F(t)，UF) (t∈[a,b])，其中g(shù)(u,t)=ddFu(t)s(u,t)是數(shù)據(jù)功能網(wǎng)絡(luò)Fu(t)中頂點u的連接函數(shù)，物數(shù)據(jù)度 (thing-data degree)ddFu(t)=|Da(u,t)|是t時刻頂點u所擁有的物數(shù)據(jù)集 (thing-data set)Da(u,t)的模，值為0，1的s(u,t)是傳感函數(shù) (sensor function)，當(dāng)s(u,t)=0時，頂點u既不接受數(shù)據(jù)，也不發(fā)射數(shù)據(jù)，除此外，頂點u是接發(fā)受數(shù)據(jù)的.如果Da(u,t)∩Da(v,t)≠?，頂點u與頂點v是數(shù)據(jù)相鄰 (data adjacency)；數(shù)值jdF(uv,t)=|Da(u,t)∩Da(v,t)|叫做邊uv∈E(Fu(t))的邊數(shù)據(jù)度 (edge-data degree)；如果Fu(t)包含一條路P=x1x2…xn，其中jdF(xjxj+1,t)≥1和j=1, 2, …,n-1，則說頂點x1和頂點xn是由P物數(shù)據(jù)連通的 (thing-data connected)；如果Fu(t)的每對頂點是由P物數(shù)連通的，則稱Fu(t)是數(shù)據(jù)連通的；F(t)是Fu(t)在t時刻的拓撲結(jié)構(gòu)圖 (topological structure)，F(xiàn)(a)是初始值 (initialvalue)；UF是數(shù)據(jù)功能網(wǎng)絡(luò)Fu(t)的底圖 (underlying graph)，它包含了Fu(t)在時間段[a,b]內(nèi)所有的頂點和邊.

相鄰性、連通性 (adjacency and connectivity)：根據(jù)定義8，在Fu(t)中如果有Da(u,t)?Da(v,t)，則說頂點u和頂點v是全數(shù)據(jù)相鄰的 (all-data adjacent)，用一條實邊 (solid edge) 連接它們；如果有Da(u,t)?Da(v,t)和Da(u,t)∩Da(v,t)≠?，則說頂點u和頂點v是條件數(shù)據(jù)相鄰的 (conditional data-adjacent)，用一條虛邊 (dot edge) 連接它們.如果一條路P=x1x2…xn滿足|Da(xi,t)∩Da(xj,t)|≥k>0 (i≠j)，則說頂點x1和頂點xn是強k-數(shù)據(jù)連通的 (stronglyk-data-connected)；如果 |Da(xi,t)∩Da(xi+1,t)|≥k>0 (i=1,2，…，n-1)，則說頂點x1和頂點xn是奇異k-數(shù)據(jù)連通的 (singularlyk-data connected).

定義9對一個物聯(lián)網(wǎng)IoT的數(shù)據(jù)功能網(wǎng)絡(luò)Fu(t)=(g(u,t),F(t)，UF) (t∈[a,b])，每條邊uv∈E(Fu(t))的行為定義為

(3) 如果頂點u和v互不控制對方，則邊uv保持不變，說頂點u,v均有0-行為. 如果u=v，即邊uv是自環(huán) (self-edge, loop), 也說頂點u,v均有0-行為.

定義10一個物 (thing) 有它自己的web-語義、確定的行為 (determined behaviors) 和唯一的web-識別，它具有定義9的k個行為中的一個行為 (k∈{0,1-, 1+, 2}).一個物聯(lián)網(wǎng) (Internat of Things)是物的集合，他們被定義7中的拓撲功能網(wǎng)絡(luò)和定義8中的數(shù)據(jù)功能網(wǎng)絡(luò)以及控制函數(shù)網(wǎng)絡(luò)這3個網(wǎng)絡(luò)的合成連接成一個整體.

上面的定義10表明，物聯(lián)網(wǎng)正是谷歌團隊的圖網(wǎng)絡(luò).

3 確定型網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)

自1999 年以后，研究無標(biāo)度網(wǎng)絡(luò)的文章如井噴，無標(biāo)度網(wǎng)絡(luò)的分支數(shù)不勝數(shù)，本文的內(nèi)容是作者根據(jù)自己的經(jīng)驗和認識來選擇介紹圖論技術(shù)，不一定是圖論研究無標(biāo)度網(wǎng)絡(luò)研究的全貌或研究主流，讀者可提出意見或按照自己的選擇來學(xué)習(xí)、研究無標(biāo)度網(wǎng)絡(luò).

稱一個網(wǎng)絡(luò)模型是連通的，如果任何一對頂點通過路徑連接.如果沒有特別的聲明，這里提到的網(wǎng)絡(luò)模型均是連通的.現(xiàn)實世界的動態(tài)網(wǎng)絡(luò)很多是無標(biāo)度網(wǎng)絡(luò)，或是小世界網(wǎng)絡(luò) (small world network)，或是層次網(wǎng)絡(luò) (hierarchical network)，或是這幾種網(wǎng)絡(luò)的混合體.

3.1 無標(biāo)度網(wǎng)絡(luò)模型

在復(fù)雜網(wǎng)絡(luò)研究中，Barabasi等[14]首次使用詞語“無標(biāo)度”(scale-free) 來描述他們的發(fā)現(xiàn)：許多大型網(wǎng)絡(luò)具有一個共同的性質(zhì)，即網(wǎng)絡(luò)的頂點連線服從冪率度分布

P(k)=Pr(x=k)～k-α, 0<α

(6)

具有這種性質(zhì)的網(wǎng)絡(luò)和網(wǎng)絡(luò)模型統(tǒng)稱為無標(biāo)度網(wǎng)絡(luò)或BA-模型 (BA-model).

盡管無標(biāo)度網(wǎng)絡(luò)得到廣泛的認可[13,28-31]，Bollobas等[32]指出：“在網(wǎng)絡(luò)圖模型中，從來就沒有‘無標(biāo)度’的準(zhǔn)確定義，關(guān)于無標(biāo)度圖的研究結(jié)果極大程度上是探索式的，或者是具有極少嚴格數(shù)學(xué)方式的實驗性質(zhì)的研究；時常發(fā)生與探索式的結(jié)論既肯定又相矛盾的情形.”

Barabasi等[33]發(fā)現(xiàn)，少數(shù)高連通網(wǎng)頁將整個 WWW 支撐連接在一起，其中80%的網(wǎng)頁平均只有4個連接，占總網(wǎng)頁數(shù)目 0.01 的網(wǎng)頁每個卻有不小于1 000個的連接.基于圖結(jié)構(gòu)分析，文獻[15]討論了動態(tài)網(wǎng)絡(luò)中的一些問題.

無標(biāo)度網(wǎng)絡(luò)具有嚴重的異質(zhì)性，其各節(jié)點之間的連接狀況 (度數(shù)) 具有嚴重的不均勻分布性：網(wǎng)絡(luò)中少數(shù)稱之為 Hub 點的節(jié)點擁有極其多的連接，而大多數(shù)節(jié)點只有很少量的連接.少數(shù) Hub 點對無標(biāo)度網(wǎng)絡(luò)的進化起著主導(dǎo)的作用.從廣義上說，無標(biāo)度網(wǎng)絡(luò)的無標(biāo)度性是描述大量復(fù)雜系統(tǒng)整體上嚴重不均勻分布的一種內(nèi)在性質(zhì).

Newman 在文獻[34-35]中給出研究復(fù)雜網(wǎng)絡(luò)的各種數(shù)學(xué)方法，他的著作《網(wǎng)絡(luò)導(dǎo)引》有784頁，他發(fā)表了150多篇關(guān)于網(wǎng)絡(luò)研究的文章，如：隨機超圖及其應(yīng)用、隨機無圈網(wǎng)絡(luò)、網(wǎng)絡(luò)中的子圖，及包含子圖的任意分布的隨機圖等.

3.2 無標(biāo)度網(wǎng)絡(luò)模型的拓撲性質(zhì)

無標(biāo)度網(wǎng)絡(luò)模型是一個機制模型，也就是說它不是描述互聯(lián)網(wǎng)、WWW或者細胞網(wǎng)絡(luò)的模型，它只是用來解釋一個網(wǎng)絡(luò)的無標(biāo)度特性背后的機制.真實世界的網(wǎng)絡(luò)比理論模型復(fù)雜得多，真實網(wǎng)絡(luò)的冪指數(shù)值從0到8不等.由無標(biāo)度機制生成的網(wǎng)絡(luò)，它們的度分布無法用一個萬能公式來解釋.單純的冪律只出現(xiàn)在簡單的理想化的模型中，僅僅由生長機制和優(yōu)先連接 (偏好依附) 驅(qū)動，并且不受其他因素干擾[36].文獻[37]指出，得到BA-模型的過程必須有以下3個要點：

(1)生長模型和優(yōu)先連接 (growth and preferential attachment) 機制.給網(wǎng)絡(luò)N(t-1)添加一個新頂點u(growth)，在優(yōu)先連接 (preferential attachment) 概率∏i=ki/∑jkj下，將新頂點u與網(wǎng)絡(luò)N(t-1)中的m個頂點x1,x2,…,xm分別用邊連接.

(2)動態(tài)方程 (dynamic equation, rate equation).建立動態(tài)方程?ki/?t=m∏i，用初始條件ki(ti)=m從動態(tài)方程中解得度函數(shù)ki(t).

(3)度分布 (degree distribution).利用時刻ti時的一致密度函數(shù)f(ti)=(ti+m0)-1來計算度分布

(7)

和方程(6)中的冪率度分布P(k)～k-α(0<α<3).

上述過程演變成有力的數(shù)學(xué)方法，在研究具有BA-模型的動力學(xué)規(guī)律的系統(tǒng)中得到了各種形式的改變和應(yīng)用.隨之而來的問題是，方程 (6) 中的冪律度分布是判斷一個網(wǎng)絡(luò)是否為無標(biāo)度網(wǎng)絡(luò)的方法，人們期望知道類似的判斷方法以及構(gòu)造無標(biāo)度網(wǎng)絡(luò)模型的算法.

3.3 無標(biāo)度網(wǎng)絡(luò)模型的新動態(tài)方程

隨著時間的推移，動態(tài)復(fù)雜網(wǎng)絡(luò)的范圍變得越來越復(fù)雜，頂點和邊緣的數(shù)量迅速增加，其空間結(jié)構(gòu)將變得更加復(fù)雜.沒有什么網(wǎng)絡(luò)會永遠不停的成長.經(jīng)過一段較長的時間后，網(wǎng)絡(luò)本身會趨于穩(wěn)定或衰變.文獻[38]對動態(tài)演化過程進行了研究，創(chuàng)新性地在每個時間步驟中包含了輸入和移除的頂點、生成和移除的邊以及來自外部的大量干擾，設(shè)計出5個特性函數(shù)來建立新的動態(tài)方程[39-40]：

(1) 添加新頂點函數(shù)f(t)=f(p1(t)m,t,ki(t), ∑∏1j(ki))是在t時刻給N(t-1)添加新頂點，使得新頂點ja與N(t-1)中的m個頂點相連，奉獻p1(t)m(0

(2) 移去頂點函數(shù)g(t)=g(p2(t)b,t,ki(t), ∑∏2j(ki)) 表明，在t時刻有p2(t)b(0

(3) 添加新邊函數(shù)h(t)=h(p3(t)r,t,ki(t), ∑∏3j(ki)) 是在t時刻給N(t-1)中某些沒有邊的頂點對添加p3(t)r(0

(4) 刪去舊邊函數(shù)z(t)=z(p4(t)s,t,ki(t), ∑∏4j(ki)) 是在t時刻將N(t-1)中的p4(t)s(0

(5) 外部干擾函數(shù)φ(t)表明網(wǎng)絡(luò)進化的過程將承受外界不可避免的干擾.

假定有m0個頂點的初始網(wǎng)絡(luò)模型N(0)是連通的，則t時刻網(wǎng)絡(luò)模型N(t)中頂點度為ki(t)的偏微分方程是

(8)

偏微分方程(8)就是新的動態(tài)方程，它的解為

ki(t)=θ(t,ti,α1,α2,…,αr)

(9)

其中，式子 (9) 中的參數(shù)αi(i=1, 2, …,r) 與時刻t和ti關(guān)聯(lián)，立得

P(ki(t)θ-1(ki(t),t,β1,

β2,…,βr))

(10)

上式(10)中的參數(shù)βi(i=1, 2, …,r)也與時刻t和ti關(guān)聯(lián).所以，網(wǎng)絡(luò)模型N(t)中度數(shù)為k的頂點的概率為

t,β1,β2,…,βr))

(11)

進一步，Ma等在文獻[38]中建立了一個社會網(wǎng)絡(luò)模型，使之適應(yīng)新動態(tài)方程 (8)，并采用3種不同的擇優(yōu)概率∏whole(ki), ∏local(ki)和∏random(ki)來合成主優(yōu)先連接概率

∏(ki)=∏whole(ki)+∏local(ki)+

令A(yù)1=α1am(1-p1),A2=2(1-p1)am+ap1,A3=α1amp1,A4=2(1-p1)(m0-am)+p1(n0-a),B1=α2am(1-p2),B2=2(1-p2)am+ap2,B3=α2amp2,B4=2(1-p2)(m0-am)+p2(n0-a).當(dāng)t→∞時，得到

(12)

其中,C=B3A2+B2A3+mA2B2α3.在初始條件ki(ti)=m下，方程 (12) 的解為

(13)

其中,D=-c/(B1A2+B2A1),β=(A2B1+A1B2)/A2B2.根據(jù)方程 (13)，度為ki(t) (小于k,P(ki(t)

(14)

假定以概率P(ti)=1/(m0+ti)在相等時間段添加新頂點，則度分布P(k)為

(15)

按照方程(15)，社會網(wǎng)絡(luò)模型N(t)服從冪律度分布P(k)～k-γ，其中指數(shù)γ=1+1/β是可調(diào)的.類似的結(jié)論可在文獻[41-42]中看到.

3.4 動態(tài)網(wǎng)絡(luò)的連通性

在文獻[2]中，Battaglia 等問到：“如果一個對象在圖網(wǎng)絡(luò)中分裂成多個碎片，代表該對象的節(jié)點也應(yīng)該被分割成多個節(jié)點.如何在計算過程中自適應(yīng)地修改圖網(wǎng)絡(luò)結(jié)構(gòu)?在一個圖網(wǎng)絡(luò)被分裂后，如何描述這個圖網(wǎng)絡(luò)?如何對合成后的圖網(wǎng)絡(luò)的底圖的結(jié)構(gòu)進行變化，如何從合成后的圖網(wǎng)絡(luò)來重建原來的圖網(wǎng)絡(luò)?”

文獻[43-45]的作者從圖論的角度給出下面撕裂型連通的概念，其中的頂點撕裂運算可以回答“如果一個對象在圖網(wǎng)絡(luò)中分裂成多個碎片，代表該對象的節(jié)點也應(yīng)該被分割成多個節(jié)點”，頂點重合運算可以實現(xiàn)“重建原來的圖網(wǎng)絡(luò)”.

頂點撕裂與重合運算 (vertex-divided operation andvertex-coincident operation).設(shè)圖H有2個不相鄰的頂點u′和頂點u″，這2個頂點的鄰集滿足Nei(u′)∩Nei(u″)=?.將頂點u′和頂點u″重合成一個頂點u=u′°u″，所得到的圖記為G=H(u′°u″)，且記H=Gu.由H得到G的過程叫做頂點重合運算 (vertex-coincident operation)，見圖6(a)和6(b)；反之，由G得到H的過程叫做頂點撕裂運算 (vertex-divided operation)，見圖6(b)和6(a).

邊撕裂與重合運算 (edge-divided operation and edge-coincident operation).設(shè)圖H有2條無公共頂點的邊u′v′ 和邊u″v″，且4個頂點的鄰集滿足Nei(u′)∩Nei(u″)=?和Nei(v′)∩Nei(v″)=?.將頂點u′和頂點u″重合成一個頂點u=u′°u″，將頂點v′ 和頂點v″ 重合成一個頂點v=v′°v″，將邊u′v′ 和邊u″v″ 重合成一條邊uv=u′v′⊕u″v″，所得到的圖記為G=H(u′v′⊕u″v″)，且記H=Guv.由H得到G的過程叫做邊重合運算 (edge-coincident operation)，見圖6(d)和6(b)；反之，由G得到H的過程叫做邊撕裂運算(edge-divided operation)，見圖6(b)～6(d).在圖6中，不難看到，6(b)→6(a)→6(c)→6(d) 也是邊撕裂運算.

圖6 解釋撕裂、重合運算的示意圖Fig.6 A scheme for illustrating divided and coincident operations

上面的頂點、邊撕裂運算導(dǎo)致下面的撕裂連通度概念：

頂點撕裂連通度 (v-divided connectivity).頂點撕裂k-連通圖L滿足：頂點撕裂圖L是不連通的，其中V*={x1,x2, …,xk}是V(L)的一個頂點子集，L的每個分支Lj至少有一個頂點wj?V*,且有|L和|E(L使得頂點撕裂圖L不連通的最小的整數(shù)k叫做圖L頂點撕裂連通度，記為κd(L).

邊撕裂連通度 (e-divided connectivity).邊撕裂k-連通圖F滿足：邊撕裂圖F是不連通的，其中E*={e1,e2, …,ek}是E(F)的一個邊子集，F(xiàn)的每個分支Fj至少有一個頂點wj不是E*中的任何一條邊的端點，且有

|V(F

|E(F

使得邊撕裂圖F不連通的最小的整數(shù)k叫做圖F邊撕裂連通度，記為κ′d(F).

Wang 等在文獻[45]中證明了：

引理1一個圖G是k-連通的，當(dāng)且僅當(dāng)它是頂點撕裂k-連通的，即是κd(G)=κ(G).

利用引理1可得下面的結(jié)論：

定理1如果k-連通圖有一個與k-連通度關(guān)聯(lián)的性質(zhì)，則對應(yīng)的頂點撕裂k-連通圖也有此性質(zhì).

定理2任意一個連通圖G的頂點撕裂連通度κd(G)和它的邊撕裂連通度κ′d(G)滿足κ′d(G)≤κd(G)≤2κ′d(G)，且上、下界可達.

令ndis(G)是頂點撕裂圖GX的分支數(shù)目最大者，有下面連通圖的結(jié)構(gòu)刻畫：

定理3設(shè)連通圖G有一個頂點子集X使得圖G-X不連通，n(G-X)是不連通圖G-X的分支數(shù)目.則n(G-X)=ndis(G)的充分必要條件是不連通圖G-X的每個分支是一個完全圖Km(m≥2).

定理4連通圖G的一個頂點子集X?V(G)，使得n(G-X)=ndis(G)=p的充分必要條件是存在連通圖G的子圖Q1,Q2, …,Qp, 使得每一個圖Qj-Yj(Yj=V(Qj)∩X)是一個完全圖Km(m≥2).換句話說，頂點撕裂圖GX是不連通的，且它的分支恰為Q1,Q2, …,Qp.

上面的引理、定理可得到下面的事實：

(1)在實施頂點撕裂運算后，新的圖網(wǎng)絡(luò)H=Gu的邊數(shù)和原來的圖網(wǎng)絡(luò)G的邊數(shù)相同，只是增加了頂點的個數(shù).將原來頂點u上的賦值或?qū)傩运毫殉?個，頂點重合運算再將2個子賦值或子屬性合成一個，從而達到“重建原來的圖網(wǎng)絡(luò)”.如果采用圖論中刪頂點的技術(shù)，則使得新的圖網(wǎng)絡(luò)比原來的圖網(wǎng)絡(luò)要少邊和頂點，更為重要的是，頂點和其關(guān)聯(lián)的邊上賦值或?qū)傩匀肯?，給“重建原來的圖網(wǎng)絡(luò)”帶來困難，甚至是在有效時間段內(nèi)不可修復(fù)原來的圖網(wǎng)絡(luò).

(2)在定理3中給出連通圖結(jié)構(gòu)的一個刻畫，也是圖網(wǎng)絡(luò)堅韌性的一種度量.

(3)利用頂點撕裂運算可以證明具有q條邊的連通歐拉圖能夠被撕裂成一個具有q個頂點的哈密爾頓圈[45-46].

(4)重合一對不相鄰且無公共鄰頂點的過程叫做保邊收縮運算 (keep-edge concentrate operation).如果不能對圖G做保邊收縮運算，則稱圖G為不可收縮圖.當(dāng)圖G是k-可著色的，所有對圖G實施頂點撕裂運算得到的圖均是k-可著色的.

3.5 拓撲圖運算下的網(wǎng)絡(luò)模型

設(shè)計、構(gòu)造網(wǎng)絡(luò)模型的目的：為實際的網(wǎng)絡(luò)建設(shè)提供理論依據(jù)和具體的高效網(wǎng)絡(luò)模型，深入探究網(wǎng)絡(luò)的更多的性質(zhì)，挖掘其實際應(yīng)用的潛力.

3.5.1 拓撲圖運算

文獻[21]的作者建立了2類拓撲圖：廣義梯子圖 (generalized ladder-graph) 和正則輪圖 (regular wheel-graph).他們用圖的連接運算 (link-Operation) 和融合運算 (merge-Operation) 對廣義梯子圖、正則輪圖的生成樹的數(shù)目進行計算，得到了生成樹數(shù)目的精確公式.

文獻[22]用圖論的運算構(gòu)造了廣義自相似非平面圖，創(chuàng)新設(shè)計了一種特殊矩陣運算，用它建立了一個稀疏網(wǎng)絡(luò)空間 (sparse network space)，并驗證了此空間的稀疏性 (sparsity)、小世界性，以及指數(shù)標(biāo)度特征 (exponential-scale feature)P(k)～α-k.

圖論的正三角增長運算 (upright triangle growth operation) 和倒三角增長運算 (inverted triangle growth operation) 在文獻 [23] 中得到應(yīng)用，并建立了一類頂點-邊增長的小世界網(wǎng)絡(luò)模型，證實了這類模型具有自相似和層次結(jié)構(gòu)特征 (self-similar and hierarchical characters).圖7給出正三角增長運算和倒三角增長運算的解釋.

圖7 正三角增長運算和倒三角增長運算

Fig.7 A scheme for understanding upright triangle-growth operation and inverted triangle-growth operation

Ma等在文獻[25]中構(gòu)造了2類Fibonacci-模型.主要技術(shù)手段是新定義了頂點速度δv(t) =Ft+Ft+1，其中{Ft}是斐波納契序列 (Fibonacci sequence)，并利用圖的三角增長運算來產(chǎn)生Fibonacci-模型.Ma等證實了Fibonacci-模型有著優(yōu)秀的拓撲性質(zhì)，十分有利于在實際應(yīng)用中采用此模型來建立優(yōu)質(zhì)的動態(tài)網(wǎng)絡(luò).

文獻[44]給出構(gòu)造自相似樹網(wǎng)絡(luò)的幾個算法，其中，有斐波納契邊算法 FIBONACCI-EDGE algorithm 和斐波納契頂點算法 FIBONACCI-VERTEX algorithm.圖8和圖9給出一個自相似樹網(wǎng)絡(luò)的前4個時刻t=1,2,3,4的進化狀態(tài).自相似性的數(shù)學(xué)定義是

θ(r)=αθ(r)，或θ(r)～α

(17)

圖8 自相似樹網(wǎng)絡(luò)

Ma 等在文獻[47]中利用拓撲圖的交運算 (join operation)、笛卡爾積運算 (Cartesian operation)、分形運算 (fractal operation) 等運算構(gòu)造了無標(biāo)度網(wǎng)絡(luò)模型，并刻畫了它們的拓撲性質(zhì).

3.5.2 菱形擴縮運算系統(tǒng)

王宏宇[48]設(shè)計了菱形擴縮運算系統(tǒng)(rhombus expanded-contracted operation system)，該系統(tǒng)以K3為初始運算對象，通過反復(fù)使用圖10中的兩種擴縮運算，生成一個4-可著色的極大平面圖(maximal planar graph).

圖9 在時刻t=4的自相似樹網(wǎng)絡(luò)N4043(t)

Fig.9 The self-similar Hanzi-networkN4043(t) shown at the forth stept=4

菱形擴縮運算系統(tǒng)可以應(yīng)用到網(wǎng)絡(luò)模型的構(gòu)造.例如，在一個網(wǎng)絡(luò)模型N(t-1)中選取一條2長的路xyw(圖10(a))，將中間的頂點y撕裂成2個頂點y′和y″，使得2個頂點的鄰集Nei(y)=Nei(y′)∩Nei(y″)，x,w∈Nei(y′)，這里允許Nei(y″)=?，然后添加3條新邊y′y″、xy″和wy″，得到一個菱形xy′wy″，產(chǎn)生的新網(wǎng)絡(luò)模型記作N(t) (見圖10(b)).

圖10 菱形擴縮運算[48]Fig.10 The rhombus expanded-contracted operation cited from Ref.[48]

3.5.3 Peterson 網(wǎng)絡(luò)模型

Peterson 網(wǎng)絡(luò)模型 (Peterson model) 在文獻[24]中作為物聯(lián)網(wǎng)的模型得到了研究，Peterson 網(wǎng)絡(luò)模型具有較高的平均度，較強的中心性，無標(biāo)度的冪律度分布、累積度分布，較高的聚類分布等良好的拓撲性質(zhì)，證明Peterson網(wǎng)絡(luò)模型具有強堅韌性，是適合于物聯(lián)網(wǎng)建設(shè)的可靠的網(wǎng)絡(luò)模型之一.

3.6 超網(wǎng)絡(luò)模型 (hypernetwork models)

定義復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)的主度分布 (main degree distribution)Pmain(k) 如下：

(18)

其中?iP(k)是社區(qū)Gi(t)的度分布，也稱為復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)的第i個偏度分布 (ith partial degree distribution).

如果每個偏度分布服從冪律度分布

?iP(k)～k-γi(i=1, 2,…,n)，

顯然，復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)的主度分布Pmain(k)遠不是Ncd(t)的度分布P(k).而且，主度分布Pmain(k)僅僅是各個社區(qū)的度分布的線性組合，沒有關(guān)聯(lián)到基Base(t)的度分布，也沒有關(guān)聯(lián)到運算“(t)”.在特殊情形下，絕對值|Pmain(k)-P(k)|將會變得很小.

在文獻[49]中，Su等取復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)中的基為Apollonian 網(wǎng)絡(luò)模型，每個社區(qū)為 Sierpinski網(wǎng)絡(luò)模型，從基Apollonian 網(wǎng)絡(luò)模型的控制集中取頂點的概率為p(t)=1，控制集中的頂點替換成社區(qū)后的相鄰頂點的社區(qū)連接運算是圖的交運算，建立了2類復(fù)合控制網(wǎng)絡(luò)模型，并研究了他們的部分拓撲性質(zhì).

復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)中以控制集Dom(t)作為活動頂點集，可以選取Dom(t)為Hub點集，或者其他類型的頂點.也可以將控制集Dom(t)換成一個基Base(t)的一個子圖，叫做活動子圖 (active subgraph).由于基Base(t)中的任何一個頂點要么在控制集Dom(t)中，要么它與控制集Dom(t)中的某個頂點相鄰.所以，復(fù)合控制網(wǎng)絡(luò)模型Ncd(t)的拓撲性質(zhì)可以由基和社區(qū)來近似估計或度量.

設(shè)M(t)是一個網(wǎng)絡(luò)模型，I(t)是M(t)的一個核，L(t)={Li(t): 1≤i≤n}是生成元集合，每個Li(t)是一個網(wǎng)絡(luò)模型，O={Oi,j: 1≤i,j≤m} 是時間[a,b]段上的二元運算集合.復(fù)合網(wǎng)絡(luò)CM|I,L,O(t)是將I(t)的邊xy的2個端點分別換為Lx(t)和Ly(t)，對Lx(t)和Ly(t)實施二元運算Ox,y, 將頂點u∈V(M(t))V(I(t))與Lv(t)的一個頂點用一條邊連接，其中Lv(t)對應(yīng)I(t)的頂點v，邊uv∈V(M(t)).圖11給出2個復(fù)合網(wǎng)絡(luò)CM|I,L,O(t)的示例.

圖11 2個復(fù)合網(wǎng)絡(luò)CM|I, L, O(t))

3.7 半隨機網(wǎng)絡(luò)模型

Yao等在文獻[50]中介紹了幾種圖運算算子，以及收縮邊運算、頂點邊剖分運算等.他們的隨機算子 (random operator) 是概率p(0

圖12 一個動態(tài)確定型網(wǎng)絡(luò)模型

(a) 2個圖算子; (b) 初始確定型網(wǎng)絡(luò)模型N(0); (c) 確定型網(wǎng)絡(luò)模型N(1); (d) 確定型網(wǎng)絡(luò)模型N(2)

圖13 兩個半隨機網(wǎng)絡(luò)模型

從網(wǎng)絡(luò)模型N(2)中以概率prem=1/2隨機地移走18條邊后得到左圖(e)，以概率padd=1/2隨機地給左圖添加9邊后得到右圖(f)

圖14 另外兩個半隨機網(wǎng)絡(luò)模型

從網(wǎng)絡(luò)模型N(2)中以概率prem=1/3隨機地移走12條邊后得到左圖(g)，以概率padd=2/3隨機地給左圖添加16邊后得到右圖(h)

3.8 構(gòu)建最優(yōu)網(wǎng)絡(luò)模型

在文獻[51]中，Lambiotte等為突破傳統(tǒng)復(fù)雜網(wǎng)絡(luò)建模的局限性，根據(jù)奧卡姆剃刀原則，好的模型即便是在高階的條件下也應(yīng)使用最少的假設(shè)，推導(dǎo)出可泛化的結(jié)論，從而使得模型的適用范圍超過最初建模的情景.他們提出高階模型可以引入下面幾類的信息來擴展傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)模型：

優(yōu)-1. 傳統(tǒng)的方法認為點與點之間的聯(lián)系可以兩兩之間建模，在高階網(wǎng)絡(luò)中拋棄這個假設(shè).

優(yōu)-2. 傳統(tǒng)的模型假設(shè)點與點之間的聯(lián)系沒有外部性，高階的網(wǎng)絡(luò)通過將網(wǎng)絡(luò)中邊的相互影響引入模型，從而改變傳統(tǒng)模型對節(jié)點重要性，以及網(wǎng)絡(luò)中群落 (社區(qū)) 組成的判定.

優(yōu)-3. 高階網(wǎng)絡(luò)模型將點和點之間的連接分為不同的類型，例如在國際貿(mào)易網(wǎng)絡(luò)中，將民用和軍用的貿(mào)易分開，由于前者受經(jīng)濟規(guī)律影響，而后者受國際政治影響，從而需要以不同的方式對待.

優(yōu)-4. 高階網(wǎng)絡(luò)模型將點與點之間的連接發(fā)生的時間和先后順序引入模型.

優(yōu)-5. 高階網(wǎng)絡(luò)模型會考慮節(jié)點之間關(guān)系對全局的影響，即網(wǎng)絡(luò)中每個點的影響.

優(yōu)-6. 傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)，該文中即初階馬爾可夫模型 (first-order Markov model)，是符合馬爾可夫的獨立性假設(shè)的模型.

Lambiotte等[51]討論了自我中心網(wǎng)絡(luò) (ego network)，時間序列數(shù)據(jù)的建模，高階網(wǎng)絡(luò)與群落檢測，高階網(wǎng)絡(luò)與節(jié)點重要性分析，用圖論中的 de Bruijn 圖對高階因果關(guān)系建模，高階網(wǎng)絡(luò)下的網(wǎng)絡(luò)動力學(xué)，用網(wǎng)絡(luò)對其中實體的相互關(guān)系進行抽象并建模，產(chǎn)生的數(shù)據(jù)又促使機器學(xué)習(xí)發(fā)展針對圖的預(yù)測模型.

4 多部網(wǎng)絡(luò)模型及其偏拓撲性質(zhì)

由于多部網(wǎng)絡(luò)模型與社交網(wǎng)絡(luò)、一般網(wǎng)絡(luò)的社區(qū)有著聯(lián)系，研究它們有助于挖掘網(wǎng)絡(luò)社區(qū)的拓撲性質(zhì).在實際的網(wǎng)絡(luò)中，多部網(wǎng)絡(luò)模型是很自然的.例如，由工人和機器組成的職業(yè)網(wǎng)絡(luò)，股票市場的某些現(xiàn)象，兩個或兩個以上國家的科學(xué)合作.下面將構(gòu)造不同于文獻[52]的多部網(wǎng)絡(luò)模型，并給出其拓撲性質(zhì)，部分內(nèi)容引自文獻[40，53].

4.1 三部網(wǎng)絡(luò)模型

令T(t)是具有頂點集劃分 (X1(t),X2(t),X3(t)) 的三部網(wǎng)絡(luò)模型，故T(t)的頂點集為V(t)=X1(t)∪X2(t)∪X3(t)，且當(dāng)i≠j時，有Xi(t)∩Xj(t)=?，3個子集X1(t),X2(t)和X3(t)均為獨立集，T(t)的任何一條邊的2個端點不在任何一個Xi(t)中.一個三部網(wǎng)絡(luò)模型在圖15中給出.下面的M-算法可以生成具有nv(t)個頂點和ne(t)條邊的三部網(wǎng)絡(luò)模型T(t).

圖15 一個三部網(wǎng)絡(luò)模型T(t)Fig.15 A tripartite model T(t)

構(gòu)造算法-1：M-算法

初始化.T(0)是有n0個頂點和m0條邊的連通圖，它的頂點集

和 |Xi(t)∪Xj(t)|≥m,i≠j滿足1≤i,j≤3.

迭代. 給T(t-1)的每個頂點集Xi(t-1)添加一個新頂點w，1≤i≤3和t≥1，將w與不在Xi(t-1)中的m(1≤m≤n0)個頂點以優(yōu)先連接概率∏i用邊連接，其中

經(jīng)過t次迭代后，T(t)有nv(t)=n0+t個頂點和ne(t)=m0+mt條邊.所以，T(t)的頂點度kj之和∑jkj等于∑jkj=2ne(t)，見圖15的解釋.由于新頂點w進入Xi(t-1)的事件獨立于新頂點w進入Xj(t-1) (j≠i) 或進入Xl(t-1) (l≠i) 這2個事件.按照3個優(yōu)先連接概率∏1, ∏2, ∏3是兩兩獨立的假設(shè)，M-算法能夠建立動態(tài)方程

(19)

在特殊情形下，能夠求得方程(19)的解.假定Xi(t)的頂點的度和為

i=1,2,3, 以及 0

(20)

其中,

進一步，將式(20)代入，得

(21)

這里ni(T(t))是T(t)中度數(shù)為ki(t)的頂點的數(shù)目.根據(jù)在時刻ti的初始條件ki(ti)=m, 方程(20)的解為

它是一個頂點在時刻ti進入網(wǎng)絡(luò)模型的度，其中

此外，使用在時刻ti的一致密度函數(shù)f(ti)=(ti+m0)-1，得到

P(ki(t)R(t))=

1-P(ti≤R(t))=

(22)

其中,

利用文獻[14]和文獻[37]的技術(shù)方法，可以計算出與其他k個頂點有k條邊的概率PT(k)如下

進而，有

其中,

=1+1/A,A(-1)=1

(23)

按照文獻[54]中介紹的網(wǎng)絡(luò)模型的速度定義，三部網(wǎng)絡(luò)模型T(t)的速度為

(24)

所以，T(t)以常量速度m增長、進化.下面推導(dǎo)三部網(wǎng)絡(luò)模型T(t)的冪律度分布P(k)和累計度分布 (cumulative degree distribution)

(25)

(26)

P(ki(t)

(27)

并得到一個公式

上式可推出帶有常數(shù)kmin>0的累計分布

這也是出現(xiàn)在方程(25)中公式的一個證明

許多研究文獻都運用了方程(25)，此方程能夠幫助估算三部網(wǎng)絡(luò)模型T(t)中度數(shù)不小于k的頂點數(shù)目，這些頂點的數(shù)目接近數(shù)nv(t)k.

4.2 多部網(wǎng)絡(luò)模型

一般情形下，需要考慮n-部網(wǎng)絡(luò)模型M(t)，n≥4.構(gòu)造算法如下：對每一時刻t，M(t)的頂點集V(t)=X1(t)∪X2(t)∪…∪Xn(t), 任何2個不同的子集滿足Xi(t)∩Xj(t)=? (i≠j, 1≤i,j≤n)，且每個Xi(t)不包含M(t)的任何一條邊的2個端點.給M(t-1)的頂點子集Xi(t)添加一個新頂點w，在優(yōu)先連接概率

(28)

下，用新邊將新頂點w于其他頂點子集Xj(t-1) (i≠j) 中的頂點用邊分別連接，得到n-部網(wǎng)絡(luò)模型M(t).用∑j∈Xi(t)kj(t)=2ne(t)pi(i=1, 2, …,n) 可以得到n個較為簡單的優(yōu)先連接

(29)

定理5任何一個無標(biāo)度網(wǎng)絡(luò)模型是一個r-部網(wǎng)絡(luò)模型 (r>0).

顯然，對每個無標(biāo)度網(wǎng)絡(luò)模型來說，確定上述定理中r的值是不輕松的.

4.3 偽二部網(wǎng)絡(luò)模型

Szabo等在文獻[52]中介紹了廣義BA-模型的率方程(rate equation).受AB-模型[52]的啟發(fā)，設(shè)計了偽二部網(wǎng)絡(luò)模型NPB(t)，它的頂點集劃分為2個不交的子集X(t)和Y(t)，使得V(t)=X(t)∪Y(t).下面的偽-算法可以產(chǎn)生具有nv(t)個頂點和ne(t)條邊的偽二部網(wǎng)絡(luò)模型.

構(gòu)造算法-2：偽-算法.

初始化. 偽二部網(wǎng)絡(luò)模型NPB(0)至少有m個頂點和m0≥m-1條邊，以及V(0)=X(0)∪Y(0),X(0)∩Y(0)=?.

迭代. 給偽二部網(wǎng)絡(luò)模型NPB(t-1)的頂點子集X(t-1) (t≥1) 添加一個新頂點u，在優(yōu)先連接概率

給頂點子集Y(t-1)添加一個新頂點w，其中py滿足 0≤py≤1.偽-算法能夠產(chǎn)生下面的動態(tài)方程

(30)

這是因為∏X(ki)和∏Y(ki)相互獨立，其中p*滿足0≤p*≤1.設(shè)置

和

來解動態(tài)方程(30).進而，得到一個較為簡單的動態(tài)方程

(31)

其中,

(32)

基于方程 (31)，可以計算出下面的和式

(33)

其中,NPB(t)是M(t)中具有度數(shù)ki(t)的頂點的個數(shù).接下來，在初始條件ki(ti)=m下，動態(tài)方程(31)的解是

在時刻ti，用一致密度函數(shù)f(ti)=(ti+m0)-1來計算

PB(ki(t)M(t))=

(34)

且

進一步，偽二部網(wǎng)絡(luò)模型NPB(t)中具有k條邊的頂點的概率PB(k)可由下面的式子計算

(35)

以及

且

θ=1+1/L,L(θ-1)=1

(36)

通過調(diào)整式(36)中L里的參數(shù)p,p*,px和py的值，不難使得偽二部網(wǎng)絡(luò)模型NPB(t)成為BA-模型.注意到，偽二部網(wǎng)絡(luò)模型NPB(t)有nv(t)=nv(0)+t個頂點和ne(t)=ne(0)+mt條邊.按照文獻[54]中關(guān)于模型速度的定義，NPB(t)的速度等于

(37)

這說明，偽二部網(wǎng)絡(luò)模型NPB(t)以常量速度而穩(wěn)定地增長和進化.

4.4 多部網(wǎng)絡(luò)模型中的確定型增長網(wǎng)絡(luò)模型

一些多部模型是確定型、非隨機型的，用他們來認識、理解復(fù)雜的網(wǎng)絡(luò)比較容易些.對于解釋經(jīng)驗觀測的現(xiàn)象以及證明具有某些性質(zhì)的網(wǎng)絡(luò)的存在，確定型網(wǎng)絡(luò)模型是有獨到之用的.確定型增長網(wǎng)絡(luò)可以通過算法來構(gòu)造，按照某些確定的要求(優(yōu)先連接)來添加新頂點，并將新頂點連接到網(wǎng)絡(luò)模型中的節(jié)點，然后不斷的重復(fù).確定型網(wǎng)絡(luò)模型的度數(shù)分布、聚類系數(shù)、平均最短路徑長度、頂點、邊緣累積分布、速度、隨機步行中心性等相關(guān)網(wǎng)絡(luò)指標(biāo)都可以得到分析和驗證.

圖16 隨機K-模型

圖17 一致K-模型NU3(2)Fig.17 A uniform K-model NU3(2)

步驟U2 一致K-模型NUm(t)是對NUm(t-1)的每一個Km-組頂點xi1,xi2,…,xim，給隨機選取的頂點子集Xs(t-1)添加一個新頂點u，使得xij?Xs(t-1) (1≤j≤m)，然后用邊將新頂點u與每一個頂點xij(1≤j≤m) 連接在一起.

現(xiàn)在討論具有nv(t)個頂點和ne(t)條邊的確定型增長網(wǎng)絡(luò)模型N(t).首先考慮確定型增長網(wǎng)絡(luò)模型N(t)滿足線性增長(linear growth) 方程組

nv(t)=avt+bv,ne(t)=aet+be

(38)

其中，av,bv,ae,be均為正整數(shù).已知BA-模型滿足方程 (38)，偽二部網(wǎng)絡(luò)模型NPB(t)和前面章節(jié)介紹的T(t)、M(t)均滿足方程 (38).通常，一個非線性增長(exponential growth) 方程組是

nv(t)=avrt+bv,ne(t)=aest+be

(39)

其中|r|≠1和|s|≠1，av,bv,ae,be均為正整數(shù).此外，按照方程 (38) 和方程 (39)，網(wǎng)絡(luò)模型N(t)的速度Vel(N(t))[54]等于

(40)

或者

(41)

進一步，得

(42)

當(dāng)方程(39)中s=r時，有

nv(t)=avrt+bv,ne(t)=aert+be

(43)

其中|r|≠1，并且

(44)

存在滿足方程(43)的確定型增長網(wǎng)絡(luò)模型，例如，Sierpinski-模型S(t) (r=3)[60]，遞歸樹模型R(t) (r=q+1,q≥2)[59]，以及阿波羅模型A(t) (r=m(d+1))[62]，以及矩形增長網(wǎng)絡(luò)模型r=4[19].可以將滿足方程(43)和方程(44)的確定型增長網(wǎng)絡(luò)模型用速度來分類，稱它們?yōu)閞-級模型.這里，Sierpinski-模型S(t)的增長速度小于遞歸樹模型R(t)和阿波羅模型A(t).文獻[63]介紹的四部網(wǎng)絡(luò)模型和文獻[64]中介紹的三部網(wǎng)絡(luò)模型均是2-級模型.

不幸的是，我們沒有發(fā)現(xiàn)滿足方程(39)中的情形s≠r的確定型增長網(wǎng)絡(luò)模型.顯然，存在不同于方程(38)和方程(39)的其他網(wǎng)絡(luò)模型，它們的頂點數(shù)目和邊數(shù)目是不能夠用形如方程(38)和方程(39)來表示的.

4.5 多部網(wǎng)絡(luò)模型的討論和問題

前面的小節(jié)提出了模擬真實網(wǎng)絡(luò)的多部網(wǎng)絡(luò)模型，并討論了出現(xiàn)在現(xiàn)實生活中的偽二部網(wǎng)絡(luò)模型，所得到的結(jié)果可以總結(jié)出具有nv(t)個頂點和ne(t)條邊的BA-模型N(t)的基本特征如下：

特征-1兩種機制.增長機制nv(t)>nv(t-1),ne(t)>ne(t-1)和優(yōu)先連接機制∏i(t).

特征-2動態(tài)方程

(45)

其中，函數(shù)f由6個基本要素構(gòu)成：n個新頂點和m條新邊，時刻t，度ki(t)，α個移走的頂點，β條移走的邊，以及優(yōu)先連接概率∏i(t).

特征-4冪律度分布P(k)～k-γ和累計度分布Pcum(k)～k1-γ滿足方程

(46)

(47)

特征-6網(wǎng)絡(luò)N(t)是稀疏的[58]，即它的平均度k接近一個常數(shù)，或者

ne(t)～O(nv(t)ln[nv(t)])

(48)

對于一般的網(wǎng)絡(luò)模型N(t)，去掉它的社區(qū)內(nèi)部的邊，就是多部網(wǎng)絡(luò)模型N-e(t).當(dāng)多部網(wǎng)絡(luò)模型N-e(t)的性質(zhì)研究清楚了，給N-e(t)添加邊，重構(gòu)原來的網(wǎng)絡(luò)模型N(t)，這是一種研究一般網(wǎng)絡(luò)的方法.

5 控制集、控制圖、拓撲矩陣

圖論的控制集在圖論的理論研究中有著重要的地位.同樣，控制集與網(wǎng)絡(luò)的生成樹、連通性、拓撲結(jié)構(gòu)有著緊密的聯(lián)系，尤其在無標(biāo)度網(wǎng)絡(luò)中，控制集包含網(wǎng)絡(luò)的許多Hub (路由器) 點、無標(biāo)度頂點.

5.1 控制集、控制圖

已知具有最多葉子的生成樹Tmax可以運用到確定網(wǎng)絡(luò)中節(jié)點的類型，確定控制集與尋找網(wǎng)絡(luò)中生成樹Tmax緊密相關(guān).

定義11圖H的一個頂點子集X叫做控制集 (dominating set)，如果H中的每個頂點在X中，或者與X中的某個頂點相鄰.

若控制集X的導(dǎo)出圖H[X]是連通的，則稱X為連通控制集 (connected dominating set).圖H的最小連通控制集S使對圖H的任何連通控制集X，總有|S|≤|X|成立.

文獻[65]證明：連通圖G的一個最小連通控制集S和Tmax滿足|G|=|S|+|L(Tmax)|, 這里L(fēng)(T)是一棵樹T的葉子的集合.下面將控制集概念推廣到控制圖.

定義12對于圖H的一個子圖I，記圖H-V(I)的分支數(shù)目為ω(H-V(I)).稱子圖I為H的一個控制圖 (dominating graph), 如果數(shù)目分支ω(H-V(I))≥2，且圖H-V(I)的每一個分支有頂點與I中的頂點相鄰.此外，當(dāng)子圖I是連通圖時，稱I為連通控制圖.若對H的任意一個控制圖J，總有ω(H-V(I))≥ω(H-V(J))，且|E(I)|最小，則稱I為最佳控制圖 (optimal dominating graph).

注意，控制圖與控制集不相同.這是因為一個控制集X外的每個頂點x必須與X中的某個頂點相鄰；刪去一個控制圖I后，余圖的每個分支有部分頂點與I的頂點相鄰，有些I外的頂點y使得距離 d(I,y)≥2.所以，當(dāng)k≤n-2時，n個頂點的K-連通圖必有n個頂點的控制圖.完全圖沒有控制圖，頂點撕裂運算與控制圖存在一定的聯(lián)系.

證明先證明第一個斷言：連通圖G的每一棵生成樹Tmax使得V(Tmax-L(Tmax))是G的一個最小連通控制集.

設(shè)Z是連通圖G的一個最小連通控制集，導(dǎo)出圖G[Z]是連通的，且有葉子最多的生成樹TZ.每一個頂點x∈V(G)與Z=V(TZ)中的一個頂點相鄰，得到圖G的一棵生成樹T*.顯然，V(G)是L(T*)的子集合.對于圖G的每一棵生成樹Tmax，樹Tmax-L(Tmax)的頂點集合S=V(Tmax)-L(Tmax)是圖G的一個連通控制集，且滿足|Z|≤|S|.從而，|L(T*)|≥|L(Tmax)|，說明圖G的生成樹T*滿足|L(T*)|=L+(G).故，|Z|=|S|，第一個斷言成立.

根據(jù)控制集定義和上面的證明，有第二個斷言：每個最小連通控制集導(dǎo)出一棵生成樹Tmax.

5.2 拓撲編碼矩陣

文小剛(3)劉小剛院士的文章“物理學(xué)的新革命——凝聚態(tài)物理中的近代數(shù)學(xué)”中的觀點.指出：“從量子革命以來，我們越來越意識到，我們的世界不是連續(xù)的，而是離散的.我們應(yīng)該用代數(shù)的眼光看世界.”圖的著色和標(biāo)號統(tǒng)稱為拓撲編碼 (topological coding)，他們與圖的賦值略有不同，圖的賦值一般不要求頂點和邊的賦值之間滿足一定的數(shù)學(xué)約束.拓撲圖編碼的定義域涉及到千萬種事物，一個圖將若干個事物連接在一起，在一定的約束條件下，形成一個完整的“故事”.

拓撲編碼與拓撲編碼矩陣 (Topcode-matrix) 緊密相連，帶有編碼的拓撲圖需要拓撲編碼矩陣輸入計算機.反過來，抽象的拓撲編碼矩陣需要用拓撲圖展示給人們.文獻[66]定義拓撲編碼矩陣如下：

定義13[66]一個拓撲編碼矩陣是如下的矩陣

(49)

其中，頂點向量X=(x1x2…xq)、邊向量E=(e1e2…eq) 和頂點向量Y=(y1y2…yq)由非負整數(shù)ei、xi和yi構(gòu)成，稱xi和yi為ei的端點，i=1,2, …,q.此外，如果有函數(shù)f使得ei=f(xi,yi)(i=1,2, …,q)，則稱拓撲編碼矩陣Tcode是值關(guān)聯(lián)的 (evaluated).

下面的矩陣A是一個拓撲編碼矩陣

(50)

這個拓撲編碼矩陣A對應(yīng)的部分拓撲圖形編碼在圖18中給出.由于拓撲編碼矩陣對應(yīng)的拓撲圖不唯一，這就極大地限制了破壞者的進攻，相應(yīng)地，增大了拓撲編碼矩陣在網(wǎng)絡(luò)安全中的應(yīng)用潛力.

圖18 (a)-(f)具有撕裂奇優(yōu)美著色的拓撲圖形編碼，每一個都對應(yīng)于矩陣(50)

Fig.18 (a)-(f) are Topsnut-gpws with (splitting) odd-edge-magic coloring and the Topcode-matrix A

Yao等在文獻[66]中定義了拓撲編碼矩陣的撕裂連通性，利用代數(shù)的線性方程組給出漢字矩陣，并證明了頂點撕裂連通度與圖的連通度是相互等價的.注意到，一個拓撲編碼矩陣可以對應(yīng)多個著色的圖 (見圖18)，也就是對應(yīng)多個相鄰矩陣，因此，深入挖掘拓撲編碼矩陣的性質(zhì)是一項有意義的工作.拓撲編碼矩陣不同于圖的鄰接矩陣 (adjacent matrix)、拉普拉斯矩陣 (Laplacian matrix) 等，它們是代數(shù)方法在圖論中的應(yīng)用.下面是有向拓撲編碼矩陣的定義：

(51)

盡管有向圖與實際應(yīng)用最為融合，有向拓撲編碼矩陣和有向拓撲圖形編碼的研究報道卻十分稀少，絕大部分的研究都以無向圖作為研究模型.Jensen等[67]的著作是學(xué)習(xí)和研究有向圖的力作之一.

6 網(wǎng)絡(luò)研究中的問題

王建方(4)中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院研究員.指出：“信息科學(xué)技術(shù)的發(fā)展給人類社會的各個領(lǐng)域都產(chǎn)生了并繼續(xù)產(chǎn)生著巨大的影響，也為創(chuàng)建、發(fā)展新數(shù)學(xué)提供了難得的機遇、源泉和動力.”下面給出部分由網(wǎng)絡(luò)研究產(chǎn)生的圖論、數(shù)學(xué)問題.

6.1 各種類型的累計分布

除了累計度分布和累計邊分布外，下面是其他類型的累計分布：

(1)Yao等[20,54,68]定義了：(1-1) vd-累計分布

(52)

其中，N(k′,t)是在t時刻網(wǎng)絡(luò)N(t)中度為k′ (>k)的頂點的數(shù)目.

(1-2) d-累計分布 (d-cumulative distribution)

(53)

其中，nd(t)是t時刻網(wǎng)絡(luò)N(t)中度數(shù)為d的頂點個數(shù)，1

(2)Wang等在文獻[68]中定義了下面的混合型累計分布 (mixed cumulative distributions)：

(54)

(55)

(56)

并用它們驗證了Comellas的遞歸樹模型、Sierpinski網(wǎng)絡(luò)模型和Apollonian網(wǎng)絡(luò)模型的無標(biāo)度性質(zhì).

通過修改式(54)～(56)，Wang等[68]又定義了下面的一組混合型累計分布

(57)

(58)

(59)

(60)

(3)Newman在文獻[34]中證明了下面的累計分布函數(shù) (cumulative distribution function)

(61)

其中，Pr(k′)是網(wǎng)絡(luò)中頂點度數(shù)不小于k的概率.

(4)Su等在文獻[69]中定義了d-累計度分布(d-cumulative degree distribution)

(62)

其中，nd(i)是在時刻i時，網(wǎng)絡(luò)N(i)中度數(shù)為d的頂點數(shù)目.

(5)Dorogovtsev等在文獻[70]中定義了聚類系數(shù)累計分布 (cumulative distribution of the clustering coefficient)

(63)

且γ=1+ln 3/ln 2，其中ξ和ξ′是離散譜的點，mc(ξ′,t)是具有聚類系數(shù)ξ′ 的頂點的數(shù)目.

(6)Yao等在文獻[54]中定義了Beta-距離累計度分布.先給出Beta-距離平均度的定義：

(64)

(65)

其中，X(u,t,β) 是在t時刻，與頂點u的距離為β的頂點之集，也叫做頂點u的Beta-距離控制集[27].當(dāng)β=1 時，則有k1=k=2ne(t)/nv(t).Beta-距離累計度分布的定義為

(66)

它是對網(wǎng)絡(luò)N(t)的一個整體度量，集合Yu(t,β，k′)是在t時刻與頂點u的距離為β的度數(shù)為k′的頂點之集.對網(wǎng)絡(luò)N(t)的一個頂點u，其局部Beta-距離累計度分布為

(67)

6.2 有關(guān)圖論的問題

圖-1. 再刻畫無標(biāo)度圖定義，擴展深化無標(biāo)度圖理論的研究.

圖-2. 刻畫無標(biāo)度極大平面圖.

圖-3. Sierpinski網(wǎng)絡(luò)模型是無標(biāo)度的歐拉圖，刻畫無標(biāo)度歐拉圖.

圖-5. 求最小正整數(shù)m，用翻轉(zhuǎn)運算來翻轉(zhuǎn)一個極大平面圖的m條邊后，得到一個無標(biāo)度極大平面圖.

圖-6. 連通刻畫圖G，使得圖G的每一個頂點都是圖G的某個具有最多葉子的生成樹Tmax的葉子.

圖-7. 確定圖的Beta-距離控制集 ((64)，(65)，β≥1) 及其應(yīng)用.

圖-8. 給出連通圖有真優(yōu)化割集 (定義6) 的條件，并找出其真優(yōu)化割集.

圖-9. 求圖的邊崩潰度 (4) 和點崩潰度 (5) 及其極值.

圖-10. 一個具有n個頂點的圈經(jīng)過頂點重合運算后，可以得到多少個互不同構(gòu)的歐拉圖?

圖-11. 頂點不可收縮圖是任何一對不相鄰頂點都有公共的鄰點，刻畫頂點不可收縮圖，發(fā)掘頂點不可收縮圖的應(yīng)用.

圖-12. 刻畫圖的控制集、控制圖與圖的頂點連通、頂點撕裂連通之間的關(guān)系及其應(yīng)用.

圖-13. 確定圖的平衡集和真平衡集 (見定義3)，探索這2個特殊集合與無標(biāo)度圖之間的聯(lián)系.

6.3 有關(guān)網(wǎng)絡(luò)拓撲性質(zhì)的問題

以下設(shè)網(wǎng)絡(luò)模型N(t)具有nv(t)個頂點和ne(t)條邊.集合Property的元素為：平均度 (average degree)，平均距離 (average distance),冪律度分布 (power-law distribution), 聚類分布 (clustering distribution), 累積度分布 (cumulate distribution), 累積邊分布 (edge-cumulate distribution)，中心度 (K-shell) 和介數(shù) (betweenness)，聚類系數(shù)累積分布 (cumulative distribution of the clustering coefficient)，度相關(guān) (degree correlation)，特征值累積分布(cumulative distribution of eigenvalues)，中介中心性 (betweenness centrality).

網(wǎng)絡(luò)-1. 無標(biāo)度網(wǎng)絡(luò)N(t)一定是稀疏的網(wǎng)絡(luò)嗎？即它的平均度k接近一個常數(shù)，或者N(t)的邊數(shù)目ne(t)等價于O(nv(t) ln[nv(t)])，nv(t)是頂點數(shù)目.馬飛用圖論中的線圖構(gòu)造出具有稠密性質(zhì)的無標(biāo)度網(wǎng)絡(luò)模型，王曉敏用圖的交運算構(gòu)造了稠密的無標(biāo)度網(wǎng)絡(luò)[71].

網(wǎng)絡(luò)-2. 文獻[2]的作者問到：圖網(wǎng)絡(luò)運行中的圖是從哪里來的？此外，許多圖網(wǎng)絡(luò)的底圖是稀疏的，解決圖網(wǎng)絡(luò)稀疏性這個公開問題.

網(wǎng)絡(luò)-3. 無標(biāo)度網(wǎng)絡(luò)的具有最多葉子的生成樹是無標(biāo)度樹嗎?

網(wǎng)絡(luò)-4. 文獻[54]、[68]均猜測到：無標(biāo)度網(wǎng)絡(luò)滿足

P(k)～Pcum(k)～Pecum(k)，

其中，累計邊分布[20],[54]定義為

這里，E(k′,t)是t時刻網(wǎng)絡(luò)N(t)中與度為k′(>k)的頂點關(guān)聯(lián)的邊的總數(shù)目.這個猜測已經(jīng)在Sierpinski網(wǎng)絡(luò)模型，Apollonian網(wǎng)絡(luò)模型和Comellas的遞歸網(wǎng)絡(luò)模型以及其他幾個確定型網(wǎng)絡(luò)上得到證實.

網(wǎng)絡(luò)-5. 研究網(wǎng)絡(luò)的其他類型的累計分布.

網(wǎng)絡(luò)-6. 構(gòu)造網(wǎng)絡(luò)模型，使得其頂點度為ki(t)的偏微分方程為(8).

網(wǎng)絡(luò)-7. 網(wǎng)絡(luò)模型的邊崩潰度(4)和點崩潰度(5)可否用來刻畫網(wǎng)絡(luò)模型的拓撲性質(zhì)?

網(wǎng)絡(luò)-8. 深化研究無標(biāo)度網(wǎng)絡(luò)在集合Property中的拓撲性質(zhì).

網(wǎng)絡(luò)-9. 表征復(fù)合控制網(wǎng)絡(luò)模型在集合Property中的拓撲性質(zhì).

網(wǎng)絡(luò)-10. 再探討物聯(lián)網(wǎng)的定義，刻畫其性質(zhì)和構(gòu)造.如何將物聯(lián)網(wǎng)的功能結(jié)構(gòu)網(wǎng)絡(luò)(定義7)和數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)(定義8)以及控制函數(shù)網(wǎng)絡(luò)這3個網(wǎng)絡(luò)整合在一起?

網(wǎng)絡(luò)-11. 構(gòu)造滿足方程(39)中s≠r情形的確定型增長網(wǎng)絡(luò)模型.

網(wǎng)絡(luò)-12. 利用Beta-距離平均度(64)和(65)來表征頂點在網(wǎng)絡(luò)中的地位和影響力.

網(wǎng)絡(luò)-13. 改進、再刻畫動態(tài)網(wǎng)絡(luò)變化的速度公式(24).

網(wǎng)絡(luò)-14. 用圖論、概率統(tǒng)計、偏微分方程等技術(shù)來刻畫動態(tài)網(wǎng)絡(luò)的社區(qū).

網(wǎng)絡(luò)-15. 數(shù)學(xué)學(xué)科可以構(gòu)成一個物聯(lián)網(wǎng)嗎?

致謝：感謝王宏宇、劉霞、王曉敏、馬飛、蘇靜、孫慧這 6 位博士和作者一起學(xué)習(xí)、研究網(wǎng)絡(luò)，并做出各自的網(wǎng)絡(luò)研究成果.作者對網(wǎng)絡(luò)研究團隊的張明軍、姚明、謝建民、楊超、趙梅梅、孫宜蓉、楊思華、張小慧等老師們的辛苦討論和艱苦工作致以感謝.