探討無標(biāo)度網(wǎng)絡(luò)(圖)的平衡集*

劉 霞，姚東任，姚 兵，張婉佳

(1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070; 2.西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

?

探討無標(biāo)度網(wǎng)絡(luò)(圖)的平衡集*

劉 霞1，姚東任2，姚 兵1，張婉佳1

(1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070; 2.西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

無標(biāo)度網(wǎng)絡(luò)的無標(biāo)度性導(dǎo)致其各頂點(diǎn)之間的連接狀況(度數(shù))具有嚴(yán)重的不均勻分布性， 無法給出無標(biāo)度網(wǎng)絡(luò)的具體結(jié)構(gòu)，不能直接觀察信息傳播的具體路徑?；诶蒙蓸鋪硌芯繜o標(biāo)度網(wǎng)絡(luò)(圖)的拓?fù)浣Y(jié)構(gòu)思想，嘗試尋找與時(shí)間和次要節(jié)點(diǎn)無關(guān)的無標(biāo)度網(wǎng)絡(luò)(圖)的普適性結(jié)構(gòu)， 研究與生成樹密切相關(guān)的平衡集，給出一個(gè)尋找具有較多葉子生成樹的算法。

平衡集；連通圖；生成樹；無標(biāo)度網(wǎng)絡(luò)

現(xiàn)實(shí)中的許多網(wǎng)絡(luò)都帶有無標(biāo)度特性，例如因特網(wǎng)，金融系統(tǒng)網(wǎng)絡(luò)，通信網(wǎng)絡(luò) (萬維網(wǎng)和互聯(lián)網(wǎng))，社交網(wǎng)絡(luò)(研究合作作者，電影演員)，生物網(wǎng)絡(luò)(神經(jīng)網(wǎng)絡(luò)，代謝網(wǎng)絡(luò)，蛋白質(zhì)網(wǎng)絡(luò)，生態(tài)和食品網(wǎng))，電話圖表，郵件網(wǎng)絡(luò)，電網(wǎng)和電子電路，軟件組件的網(wǎng)絡(luò)，以及能源景觀網(wǎng)絡(luò)等等。具有無標(biāo)度性的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)。已知大數(shù)據(jù)在執(zhí)法、經(jīng)濟(jì)規(guī)劃、防災(zāi)和災(zāi)后恢復(fù)等方面已有應(yīng)用。一些國家將“大數(shù)據(jù)戰(zhàn)略”上升為最高國策，認(rèn)為大數(shù)據(jù)是“未來的新石油”，可以“挖出商業(yè)金礦”，將對數(shù)據(jù)的占有和控制作為陸權(quán)、海權(quán)、空權(quán)之外的另一種國家核心能力。無標(biāo)度網(wǎng)絡(luò)的無標(biāo)度性是描述大量復(fù)雜系統(tǒng)整體上嚴(yán)重不均勻分布的一種內(nèi)在性質(zhì)，其典型特征是在網(wǎng)絡(luò)中的大部分頂點(diǎn)只和很少節(jié)點(diǎn)連接，極少數(shù)Hub節(jié)點(diǎn)與非常多的節(jié)點(diǎn)連接。這種嚴(yán)重的異質(zhì)性，導(dǎo)致其各頂點(diǎn)之間的連接狀況 (度數(shù)) 具有嚴(yán)重的不均勻分布性，少數(shù)Hub節(jié)點(diǎn)對無標(biāo)度網(wǎng)絡(luò)的運(yùn)行起著主導(dǎo)的作用。但是，“無標(biāo)度網(wǎng)絡(luò)的具體結(jié)構(gòu)無法給出。作為信息存儲(chǔ)的重要載體，節(jié)點(diǎn)通過鏈接實(shí)現(xiàn)信息交互，然而，節(jié)點(diǎn)的信息來源通常難以確定，信息傳播的具體路徑不能直接觀察[1]?！碧接憻o標(biāo)度網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)成為當(dāng)務(wù)之急。

眾所周知，圖論中的生成樹已經(jīng)成功地應(yīng)用到實(shí)際問題，積累了豐富的理論[2-4]。最典型的應(yīng)用之一是 Radia Perlman[5]利用生成樹與網(wǎng)絡(luò)間的結(jié)構(gòu)關(guān)系發(fā)明了廣泛用于網(wǎng)橋、交換機(jī)上生成樹協(xié)議。已有大量運(yùn)用生成樹的算法，例如最小生成樹對電網(wǎng)的優(yōu)化；以及物流運(yùn)輸費(fèi)用在貨物配送過程中對配送區(qū)域的劃分與配送路線的優(yōu)化選擇等。本文利用生成樹來研究無標(biāo)度網(wǎng)絡(luò) (圖) 的拓?fù)浣Y(jié)構(gòu)，嘗試尋找與時(shí)間和次要節(jié)點(diǎn)無關(guān)的無標(biāo)度網(wǎng)絡(luò) (圖) 的普適性結(jié)構(gòu)[6-8]。研究與生成樹密切相關(guān)的平衡集是本研究的一個(gè)關(guān)鍵。稱有p個(gè)頂點(diǎn)和q條邊的圖G為(p,q)-圖，nd(G)是G中度數(shù)為d的頂點(diǎn)數(shù)目。文中論及的圖均為簡單、無向、有限圖，并采用標(biāo)準(zhǔn)的圖論術(shù)語和符號。記號[m,n]表示集合{m,m+1,m+2,…,n}，其中m和n均為整數(shù)， 且滿足0

定義1[8]集合X是連通圖G的平衡集，如果它滿足

(1)

為研究的需要，我們給出如下的幾個(gè)概念。

設(shè)連通圖G的全體具有最多葉子的生成樹為T1max,T2max, …,Ttmax，令

引理1[9]每個(gè)連通(p,q)-圖G滿足

(2)

引理2[6]設(shè)G是連通(p,q)-圖，D(G)是圖G的直徑。

(i)G有一棵葉子最少的生成樹T，使得D(T)=D(G)，且T包含G的一條最長路。

(ii)G包含一棵葉子最多的生成樹Tmax，使得Δ(G)=Δ(Tmax)，n1(Tmax)≤p-D(G)+1。

1 結(jié)論及其證明

命題1 每個(gè)連通(p,q)-圖G含有一棵生成樹Tmax，使得

2+[Δ(G)-2]nΔ(G)≤n1(Tmax)≤p-D(G)+1

(3)

證明 若連通(p,q)-圖G是一棵樹，引理得證。當(dāng)G不是一棵樹，則有如下的算法：

輸入：連通 (p,q)-圖G。

輸出：圖G的一棵生成樹T。

① 打斷圖G的自環(huán)，記余圖為H0;

② 刪去Hi中一個(gè)圈上的一條邊uivi，Hi+1←Hi-uivi，i←i+1;

④ 返回生成樹T。

首先，上述算法的正確性是顯然的。這是因?yàn)閳DG的邊數(shù)目是有限的，且每次只刪去一個(gè)圈上的一條邊；其次，生成樹Tmax的存在性是顯然的。

2+[Δ(G)-2]nΔ(G)(G)

因?yàn)閚1(T)≤n1(Tmax)，再根據(jù)引理2中的結(jié)論(i)，可推出得不等式(3)中的上界。

命題2 若連通圖G的最小平衡集為S，則它的任何連通支撐子圖的最小平衡集亦為S。

證明 因?yàn)檫B通圖G的連通子圖的生成樹也是G的生成樹，由平衡集的定義，本命題得證。

命題3 若連通圖有一個(gè)割點(diǎn)，則它的每一個(gè)平衡集包含此割點(diǎn)。

證明 設(shè)u為連通圖G的一個(gè)割點(diǎn)。因?yàn)镚的任何生成樹包含割點(diǎn)u，且割點(diǎn)u不是任何生成樹的葉子， 本命題得證。

命題4 設(shè)連通圖G的所有葉子的集合記為L(G)，則G有一個(gè)平衡集S=V(G)L(G)。

證明 令L(G)=L。若L=?，顯然結(jié)論成立，下證L≠?，結(jié)論成立。如果L≠?，則由生成樹的定義可知，對G的生成樹T，有L?L(T)，如若不然，至少存在一個(gè)頂點(diǎn)u0∈L，而u0?L(T)，即u0為T中非葉子頂點(diǎn)，這導(dǎo)致u0為G中非葉子頂點(diǎn)，矛盾！下證S=V(G)L(G)為平衡集。

由定義2，對圖G的任意2棵生成樹T和H，有

同理，

說明生成樹T和H滿足(1)式，即S為連通圖G的平衡集。

定理1 若連通圖G含有 Hamilton圈，則它的平衡集只有V(G)。

① 若L∩≠?，那么L∩及其所有子集為圖G的TM-平衡集。

結(jié)論 (1) 成立。

結(jié)論 (2) 成立。

所以，X∪S為圖G的一個(gè)TM-平衡集。定理得證。

我們會(huì)發(fā)現(xiàn)，在一個(gè)無標(biāo)度網(wǎng)絡(luò)N(t)中，當(dāng)t很大時(shí)，N(t)的TM-平衡集必然滿足L∪?V(G)，L∩≠?。也就是說對N(t)的任意TM-生成樹，總有某些點(diǎn)是非葉子節(jié)點(diǎn)，而只是這些點(diǎn)構(gòu)成了網(wǎng)絡(luò)N(t)的骨架，同樣，總有某些點(diǎn)是葉子節(jié)點(diǎn)，而且葉子節(jié)點(diǎn)數(shù)遠(yuǎn)大于非葉子節(jié)點(diǎn)數(shù)。

例1 完全圖不含真平衡集，也不含TM-平衡集，且它的任意2棵具有最多葉子的生成樹同構(gòu)。

證明 設(shè)圖Kn是n個(gè)頂點(diǎn)的完全圖，則易知Kn包含Cn子圖，故不含有真平衡集。我們給出另外一種證明方法。設(shè)Kn的頂點(diǎn)集為{a1,a2, …,an}，可知Kn的生成樹葉子最多為n-1個(gè)，且對任意的Tjmax，有L(Tjmax)=V(Kn){ai}(i∈[1,n])，計(jì)算TM-平衡交集和TM-平衡并集，得

∩L(Tjmax)=∩(V(Kn){ai})=

V(Kn)(∪{ai})=?；

∪L(Tjmax)=∪(V(Kn){ai})=

V(Kn)(∩{ai})=V(Kn)

根據(jù)定理2，完全圖Kn無TM-平衡集。由于完全圖Kn的具有最多葉子的生成樹是星K1, n-1，所以它的任意2棵具有最多葉子的生成樹同構(gòu)。

例2 完全二部圖Km,n不含真平衡集和TM-平衡集，且它的任意2棵具有最多葉子的生成樹同構(gòu)。

∩ijL(Tij)=∩ij(V(Km,n){u,,vj})=

V(Km,n)∩ij{ui,vj}=?

和∪ijL(Tij)=∪ij(V(Km,n){ui,vj})=V(Km, n)。根據(jù)定理2，完全二部圖Km,n不含TM-平衡集，也沒有真平衡集。前面已經(jīng)給出完全二部圖Km,n的具有最多葉子的生成樹均為雙星，也就是說，Km, n的任意2棵具有最多葉子的生成樹同構(gòu)。

要尋找網(wǎng)絡(luò)N(t)的真平衡集及TM-平衡集，我們就必須先找到它的生成樹，針對CDSP (connecteddominating set problem)和MLATP (maximum leaf spanning tree problem)問題，文獻(xiàn)[10]的作者用分治技術(shù)(measure-and-conquer technique)給出尋找n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)生成樹Tmax的時(shí)間為O(1.896 6n)的一個(gè)精確算法。然而，尋找生成樹Tmax是NP困難問題[11]。Barabsi和Bonabeau[12]發(fā)現(xiàn)，少數(shù)高連通網(wǎng)頁將整個(gè)WWW支撐連接在一起，其中80%的網(wǎng)頁平均只有4個(gè)連接，占總網(wǎng)頁數(shù)目0.01的網(wǎng)頁每個(gè)卻有不小于1 000個(gè)的連接。依據(jù)這個(gè)事實(shí)和命題1，我們給出一個(gè)大度搜索優(yōu)先算法，用來尋找具有較多葉子的生成樹。記號N(X)表示集合X的鄰點(diǎn)之集，并令N[X]=N(X)∪X。特別地，當(dāng)X={u}時(shí)，直接寫N(u)和N[u]。

大度優(yōu)先搜索算法 (Largedegree-First Search Algorithm)

輸入：具有頂點(diǎn)v1，v2，…，vn的無標(biāo)度圖G，且dG(vi) ≥dG(vi+1)，i=1, 2,…,n-1，Δ(G)=dG(v1) >1。常數(shù)k滿足δ(G)

③ 如果i

④ 采用BFS算法(Breadth-First Search Algorithm)。Hl是樹或森林。令S←V(Hl)；令R←N(X)；對每一個(gè)頂點(diǎn)x∈S，有l(wèi)(x)←0。

⑤ 如果R=?和S=V(G)，記找到的生成樹為H，轉(zhuǎn)到⑧。如果R≠?，轉(zhuǎn)到⑥；如果R=?且S≠V(G)， 轉(zhuǎn)到⑦。

⑥ 頂點(diǎn)v是R中第一個(gè)頂點(diǎn)，取w∈N(v)(R∪S)，且w滿足dG(w) ≥dG(x) (x∈N(v))；把w放進(jìn)R， 使其成為最后一個(gè)頂點(diǎn)；從R中取出v，然后把它放進(jìn)S；令l(w)←l(v)+1；轉(zhuǎn)到 ⑤。

⑧ 輸出生成樹H。

定理3 大度優(yōu)先算法輸出H是生成樹。

例3 應(yīng)用大度優(yōu)先算法的一個(gè)例子在圖2和圖3給出。在G1中，是選擇常數(shù)k=11滿足δ(G)<11<Δ(G)，使得dG(v1)≥11，dG(v2)≥11，但對v∈V(G){v1,v2}，有dG(v)<11。G1和G2是執(zhí)行大度優(yōu)先算法的前3步； 從G3到G8是執(zhí)行大度優(yōu)先算法的后5步。

圖2 應(yīng)用大度優(yōu)先算法的一個(gè)例子Fig.2 An example of application of the large degree-first search algorithm

圖3 G7 中的頂點(diǎn)u0?V(G)SFig.3 A vertex u0?V(G)S in G7

2 總結(jié)及今后的研究

本文沒有進(jìn)行大度優(yōu)先算法的復(fù)雜度確定，以及估計(jì)所找到的生成樹葉子數(shù)目，這是今后要進(jìn)行的研究。關(guān)于平衡集以及生成樹，要進(jìn)行的工作是：① 挖掘平衡集在無標(biāo)度網(wǎng)絡(luò) (圖) 中的深層次的功能。②在已知圖有平衡集，快速找出所需要的生成樹，如葉子最多或最少的生成樹，最短直徑的生成樹等，探討之間的聯(lián)系性。③在一個(gè)無標(biāo)度網(wǎng)絡(luò) (圖) 中，平衡集中的點(diǎn)對無標(biāo)度網(wǎng)絡(luò) (圖) 的魯棒性和脆弱性有什么影響？④尋找一個(gè)圖的最小平衡集可以按照：(i) 先找出它的所有生成樹，定義一個(gè)二維數(shù)組，用以保存所得生成樹以及它的葉子集；(ii) 去掉原圖中的葉子和割點(diǎn)，求出所剩余集合S的所有子集，定義一位數(shù)組，將所有子集保存；(iii) 用S的任意子集與 (i) 中的樹集進(jìn)行驗(yàn)證，得出最小平衡集。然而，這個(gè)算法是比較復(fù)雜的，但也是通用的算法。對于比較簡單的連通圖，可以根據(jù)這種思路編寫通用的算法，需要做的是證明算法的正確性、可行性及其復(fù)雜性。

最后，提出下面的問題：

問題1 刻畫具有最多葉子的生成樹T1，T2，…，Tt的連通圖G，使得

D(T1)

問題3 猜測“均勻”圖沒有真平衡集的網(wǎng)絡(luò)，它的TM-平衡集也不存在。

[1] 劉大有, 李晶, 楊博. 信息傳播網(wǎng)絡(luò)學(xué)習(xí)方法[J]. 吉林大學(xué)學(xué)報(bào)：理學(xué)版, 2012, 50(4): 767-774.

[2] 范淑艷, 韓衛(wèi)占, 霍永華. MPLS網(wǎng)絡(luò)的綜合接納控制算法[J]. 中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2011, 50 (2): 54-57.

[3] 刁玉平, 廖銘, 刁永平. 互聯(lián)網(wǎng)架構(gòu)關(guān)鍵資源可擴(kuò)展研究[J]. 中山大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011, 50 (6): 53-57.

[4] 黃超, 王國利. 無線傳感器網(wǎng)絡(luò)協(xié)作無信標(biāo)可靠路由協(xié)議[J]. 中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2013, 52 (4): 39-44.

[5] RADIA PERLMAN. Hierarchical networks and the subnetwork partition problem [J]. Computer Networks and ISDN Systems, 1985, 9: 297-303.

[6] YAO B, ZHOU X Q, ZHANG J J, et al. Labellings and invariants of models from complex networks [C]// Proceeding of 2012 International Conference on Systems and Informatics, 2012:1616-1620.

[7] YAO B, CHEN X E, ZHOU X Q, et al. Graphs related with scale-free networks [C]//Proceeding of The 2ndInternational Conference on Electronics, Communications and Control, 2012: 284-287.

[8] YAO B, CHEN X E, YANG C, et al. Spanning trees and dominating sets in scale-free networks [C]// Proceeding of 2012 IET International Conference on Information Science and Control Engineering, 2012: 111-115.

[9] YAO B, ZHANG Z F, WANG J F. Some results on spanning trees [J]. Acta Mathematicae Applicatae Sinica, English Series, 2010, 26(4):607-616.

[10] FERNAU H, KNEIS J, KRATSCH D, et al. An exact algorithm for the maximum leaf spanning tree problem [J]. Theoretical Computer Science, 2011, 412 (45): 6290-6302.

[11] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness [M]. New York : W H Freeman and Company, 1979.

On Balanced Sets in Scale-free Networks (Graphs)

LIUXia1,YAODongren2,YAOBing1,ZHANGWanjia1

(1.College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China; 2.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

The scale-free nature of a scale-free network yields uneven distribution of connections (degrees) between its nodes. As the topological structures of scale-free networks are not exactly figured up to now, people can not observe clearly paths of information dissemination in scale-free networks. Based on the idea of using spanning trees in researching topological structures of scale-free networks, the universal structure of scale-free networks without relating time and sub-nodes are tried to find, and balanced sets that are extensively related with spanning trees in the networks are researched, and furthermore show an algorithm for finding spanning trees with more leaves.

balanced set; connected graph; spanning tree; scale-free network

2014-02-08

國家自然科學(xué)基金資助項(xiàng)目 (61163054， 61163037， 61363060)

劉霞 (1990年生)， 女；研究方向：組合優(yōu)化和圖論；通訊作者：姚兵；E-mail:yybb918@163.com

10.1347/j.cnki.acta.snus.2015.01.005

O

A

0529-6579(2015)01-0019-05