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

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

1 研究背景、術語、定義

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

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

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

(a) 泛著色泛結構拓撲圖；(b) 飽和烷烴拓撲圖；(c) 物理關聯(lián)知識拓撲圖

圖2 英特網絡

圖3 左右主導的大腦網絡

圖4 引自文獻[10]的一個生物網絡Fig.4 A biological network cited from Ref.[10]

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

1.2 人工智能研究中的拓撲圖應用

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

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

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

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

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

1.3 運用圖論理論和技術到網絡研究中

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

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

2 無標度圖、集散點、崩潰度、物聯(lián)網定義

2.1 無標度圖定義

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

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

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

(1)

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

(2)

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

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

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

圖5 無標度網絡Fig.5 A scale-free network

2.2 集散點定義

注意到，無標度網絡N(t)中的無標度圖G(t)的階數(shù)和邊數(shù)一般情形下不是一個常數(shù)，這是因為不斷地有節(jié)點進入或移出網絡N(t)，而且每個節(jié)點的連線數(shù)目在時間區(qū)間[a,b]內也會變化，從而說明圖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，當G(t0)的特性和結構確定后，就可以用它來刻畫或估測每一個G(t)的結構及其特性，t∈(t0-δ,t0+δ).為研究無標度網絡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)

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

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

2.3 網絡崩潰度定義

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

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

(4)

(5)

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

定義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)網定義

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

定義7一個物聯(lián)網的拓撲功能網絡 (topological network) 定義為Io(t)=(d(p,u,t),G(t),UD) (t∈[a,b]).拓撲功能網絡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關聯(lián)的邊數(shù)目，值為0，1的s(u,t)是活動函數(shù)(active function)，當s(u,t)=0，說頂點u是睡眠的，當s(u,t)=1，說頂點u是活動的.一條邊uv是物聯(lián)網Io(t)的顯邊 (expressed edge)，若s(u,t)=s(v,t)=1，此外，稱它為隱邊 (implied edge)；一條路P=u1u2…un上的每個頂點ui均是活動的；G(t)是拓撲圖 (topological graph)，G(a)是初始圖，UD是拓撲功能網絡Io(t)的底圖 (underlying graph)，它包含了拓撲功能網絡在時間段[a,b]內所有的頂點和邊.

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

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

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

定義9對一個物聯(lián)網IoT的數(shù)據功能網絡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)網 (Internat of Things)是物的集合，他們被定義7中的拓撲功能網絡和定義8中的數(shù)據功能網絡以及控制函數(shù)網絡這3個網絡的合成連接成一個整體.

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

3 確定型網絡、隨機網絡

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

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

3.1 無標度網絡模型

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

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

(6)

具有這種性質的網絡和網絡模型統(tǒng)稱為無標度網絡或BA-模型 (BA-model).

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

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

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

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

3.2 無標度網絡模型的拓撲性質

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

(1)生長模型和優(yōu)先連接 (growth and preferential attachment) 機制.給網絡N(t-1)添加一個新頂點u(growth)，在優(yōu)先連接 (preferential attachment) 概率∏i=ki/∑jkj下，將新頂點u與網絡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ù)學方法，在研究具有BA-模型的動力學規(guī)律的系統(tǒng)中得到了各種形式的改變和應用.隨之而來的問題是，方程 (6) 中的冪律度分布是判斷一個網絡是否為無標度網絡的方法，人們期望知道類似的判斷方法以及構造無標度網絡模型的算法.

3.3 無標度網絡模型的新動態(tài)方程

隨著時間的推移，動態(tài)復雜網絡的范圍變得越來越復雜，頂點和邊緣的數(shù)量迅速增加，其空間結構將變得更加復雜.沒有什么網絡會永遠不停的成長.經過一段較長的時間后，網絡本身會趨于穩(wěn)定或衰變.文獻[38]對動態(tài)演化過程進行了研究，創(chuàng)新性地在每個時間步驟中包含了輸入和移除的頂點、生成和移除的邊以及來自外部的大量干擾，設計出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)表明網絡進化的過程將承受外界不可避免的干擾.

假定有m0個頂點的初始網絡模型N(0)是連通的，則t時刻網絡模型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關聯(lián)，立得

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

β2,…,βr))

(10)

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

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

(11)

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

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

令A1=α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).當t→∞時，得到

(12)

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

(13)

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

(14)

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

(15)

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

3.4 動態(tài)網絡的連通性

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

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

頂點撕裂與重合運算 (vertex-divided operation andvertex-coincident operation).設圖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).設圖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

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

頂點撕裂連通度 (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-連通的，當且僅當它是頂點撕裂k-連通的，即是κd(G)=κ(G).

利用引理1可得下面的結論：

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

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

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

定理3設連通圖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)在實施頂點撕裂運算后，新的圖網絡H=Gu的邊數(shù)和原來的圖網絡G的邊數(shù)相同，只是增加了頂點的個數(shù).將原來頂點u上的賦值或屬性撕裂成2個，頂點重合運算再將2個子賦值或子屬性合成一個，從而達到“重建原來的圖網絡”.如果采用圖論中刪頂點的技術，則使得新的圖網絡比原來的圖網絡要少邊和頂點，更為重要的是，頂點和其關聯(lián)的邊上賦值或屬性全部消失，給“重建原來的圖網絡”帶來困難，甚至是在有效時間段內不可修復原來的圖網絡.

(2)在定理3中給出連通圖結構的一個刻畫，也是圖網絡堅韌性的一種度量.

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

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

3.5 拓撲圖運算下的網絡模型

設計、構造網絡模型的目的：為實際的網絡建設提供理論依據和具體的高效網絡模型，深入探究網絡的更多的性質，挖掘其實際應用的潛力.

3.5.1 拓撲圖運算

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

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

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

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

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

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

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

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

(17)

圖8 自相似樹網絡

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

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

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

圖9 在時刻t=4的自相似樹網絡N4043(t)

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

菱形擴縮運算系統(tǒng)可以應用到網絡模型的構造.例如，在一個網絡模型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″，產生的新網絡模型記作N(t) (見圖10(b)).

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

3.5.3 Peterson 網絡模型

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

3.6 超網絡模型 (hypernetwork models)

定義復合控制網絡模型Ncd(t)的主度分布 (main degree distribution)Pmain(k) 如下：

(18)

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

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

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

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

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

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

設M(t)是一個網絡模型，I(t)是M(t)的一個核，L(t)={Li(t): 1≤i≤n}是生成元集合，每個Li(t)是一個網絡模型，O={Oi,j: 1≤i,j≤m} 是時間[a,b]段上的二元運算集合.復合網絡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)對應I(t)的頂點v，邊uv∈V(M(t)).圖11給出2個復合網絡CM|I,L,O(t)的示例.

圖11 2個復合網絡CM|I, L, O(t))

3.7 半隨機網絡模型

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

圖12 一個動態(tài)確定型網絡模型

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

圖13 兩個半隨機網絡模型

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

圖14 另外兩個半隨機網絡模型

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

3.8 構建最優(yōu)網絡模型

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

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

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

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

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

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

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

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

4 多部網絡模型及其偏拓撲性質

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

4.1 三部網絡模型

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

圖15 一個三部網絡模型T(t)Fig.15 A tripartite model T(t)

構造算法-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用邊連接，其中

經過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是兩兩獨立的假設，M-算法能夠建立動態(tài)方程

(19)

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

i=1,2,3, 以及 0

(20)

其中,

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

(21)

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

它是一個頂點在時刻ti進入網絡模型的度，其中

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

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

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

(22)

其中,

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

進而，有

其中,

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

(23)

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

(24)

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

(25)

(26)

P(ki(t)

(27)

并得到一個公式

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

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

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

4.2 多部網絡模型

一般情形下，需要考慮n-部網絡模型M(t)，n≥4.構造算法如下：對每一時刻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-部網絡模型M(t).用∑j∈Xi(t)kj(t)=2ne(t)pi(i=1, 2, …,n) 可以得到n個較為簡單的優(yōu)先連接

(29)

定理5任何一個無標度網絡模型是一個r-部網絡模型 (r>0).

顯然，對每個無標度網絡模型來說，確定上述定理中r的值是不輕松的.

4.3 偽二部網絡模型

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

構造算法-2：偽-算法.

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

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

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

(30)

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

和

來解動態(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)

且

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

(35)

以及

且

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

(36)

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

(37)

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

4.4 多部網絡模型中的確定型增長網絡模型

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

圖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)條邊的確定型增長網絡模型N(t).首先考慮確定型增長網絡模型N(t)滿足線性增長(linear growth) 方程組

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

(38)

其中，av,bv,ae,be均為正整數(shù).已知BA-模型滿足方程 (38)，偽二部網絡模型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)，網絡模型N(t)的速度Vel(N(t))[54]等于

(40)

或者

(41)

進一步，得

(42)

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

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

(43)

其中|r|≠1，并且

(44)

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

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

4.5 多部網絡模型的討論和問題

前面的小節(jié)提出了模擬真實網絡的多部網絡模型，并討論了出現(xiàn)在現(xiàn)實生活中的偽二部網絡模型，所得到的結果可以總結出具有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個基本要素構成：n個新頂點和m條新邊，時刻t，度ki(t)，α個移走的頂點，β條移走的邊，以及優(yōu)先連接概率∏i(t).

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

(46)

(47)

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

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

(48)

對于一般的網絡模型N(t)，去掉它的社區(qū)內部的邊，就是多部網絡模型N-e(t).當多部網絡模型N-e(t)的性質研究清楚了，給N-e(t)添加邊，重構原來的網絡模型N(t)，這是一種研究一般網絡的方法.

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

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

5.1 控制集、控制圖

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

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

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

文獻[65]證明：連通圖G的一個最小連通控制集S和Tmax滿足|G|=|S|+|L(Tmax)|, 這里L(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中的頂點相鄰.此外，當子圖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.所以，當k≤n-2時，n個頂點的K-連通圖必有n個頂點的控制圖.完全圖沒有控制圖，頂點撕裂運算與控制圖存在一定的聯(lián)系.

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

設Z是連通圖G的一個最小連通控制集，導出圖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|，第一個斷言成立.

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

5.2 拓撲編碼矩陣

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

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

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

(49)

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

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

(50)

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

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

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

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

(51)

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

6 網絡研究中的問題

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

6.1 各種類型的累計分布

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

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

(52)

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

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

(53)

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

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

(54)

(55)

(56)

并用它們驗證了Comellas的遞歸樹模型、Sierpinski網絡模型和Apollonian網絡模型的無標度性質.

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

(57)

(58)

(59)

(60)

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

(61)

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

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

(62)

其中，nd(i)是在時刻i時，網絡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].當β=1 時，則有k1=k=2ne(t)/nv(t).Beta-距離累計度分布的定義為

(66)

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

(67)

6.2 有關圖論的問題

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

圖-2. 刻畫無標度極大平面圖.

圖-3. Sierpinski網絡模型是無標度的歐拉圖，刻畫無標度歐拉圖.

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

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

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

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

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

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

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

圖-12. 刻畫圖的控制集、控制圖與圖的頂點連通、頂點撕裂連通之間的關系及其應用.

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

6.3 有關網絡拓撲性質的問題

以下設網絡模型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)，度相關 (degree correlation)，特征值累積分布(cumulative distribution of eigenvalues)，中介中心性 (betweenness centrality).

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

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

網絡-3. 無標度網絡的具有最多葉子的生成樹是無標度樹嗎?

網絡-4. 文獻[54]、[68]均猜測到：無標度網絡滿足

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

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

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

網絡-5. 研究網絡的其他類型的累計分布.

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

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

網絡-8. 深化研究無標度網絡在集合Property中的拓撲性質.

網絡-9. 表征復合控制網絡模型在集合Property中的拓撲性質.

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

網絡-11. 構造滿足方程(39)中s≠r情形的確定型增長網絡模型.

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

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

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

網絡-15. 數(shù)學學科可以構成一個物聯(lián)網嗎?

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