王 頎 王銀河

（廣東工業(yè)大學(xué)自動化學(xué)院 廣州 510006）

1 引言

近些年來，符號網(wǎng)絡(luò)一直是復(fù)雜網(wǎng)絡(luò)研究的熱點對象之一。符號網(wǎng)絡(luò)是指連接邊具有正號和負(fù)號屬性的網(wǎng)絡(luò)，社會學(xué)領(lǐng)域的學(xué)者最早使用這樣的網(wǎng)絡(luò)模型［1］，而后逐漸應(yīng)用到了其他的領(lǐng)域中。在社會網(wǎng)絡(luò)中，正連接邊通常表示友好關(guān)系，負(fù)連接邊通常表示反對關(guān)系［2～5］。

在符號網(wǎng)絡(luò)中，占據(jù)結(jié)構(gòu)洞（Structural hole）的洞主（Broker）是一種特殊的節(jié)點。結(jié)構(gòu)洞理論是由美國社會學(xué)家Burt 于1992 年在他的著作《結(jié)構(gòu)洞：競爭的社會結(jié)構(gòu)》中首次提出的［6］。隨后，結(jié)構(gòu)洞的概念被廣泛地應(yīng)用在社會學(xué)［7～8］、經(jīng)濟(jì)學(xué)［9～10］等領(lǐng)域中。在結(jié)構(gòu)洞理論中，Burt［6］指出占據(jù)結(jié)構(gòu)洞的節(jié)點相比于網(wǎng)絡(luò)中的其他節(jié)點更加具有競爭優(yōu)勢，由此產(chǎn)生了洞主（Broker）的概念。

目前，從現(xiàn)有的研究可以看出，洞主已經(jīng)成為了網(wǎng)絡(luò)的關(guān)鍵節(jié)點之一［11～13］。從控制信息資源的角度看，網(wǎng)絡(luò)中洞主的存在往往會造成網(wǎng)絡(luò)中個體獲得資源能力的不平衡。 因此，也有很多學(xué)者通過對網(wǎng)絡(luò)施加控制作用，使得網(wǎng)絡(luò)中的洞主逐漸消失，從而使得網(wǎng)絡(luò)達(dá)到某種平衡［14～16］，這種平衡的典型代表就是結(jié)構(gòu)平衡網(wǎng)絡(luò)［1，14～15］，它是一種特殊的無洞主網(wǎng)絡(luò)。文獻(xiàn)［16］基于結(jié)構(gòu)洞和洞主的概念，提出了無洞主的網(wǎng)絡(luò)，其研究結(jié)果表明，無洞主網(wǎng)絡(luò)的節(jié)點可以被分為若干個陣營，使得陣營內(nèi)的節(jié)點之間的連接關(guān)系為正值，陣營之間的連接關(guān)系為非正值。

從控制信息資源的角度看，無洞主網(wǎng)絡(luò)所特有的拓?fù)浣Y(jié)構(gòu)體現(xiàn)了網(wǎng)絡(luò)中個體對于信息控制的均等性，同時也表明這種均等性隱含個體的可分類性。顯然，一般的網(wǎng)絡(luò)由于洞主的存在而導(dǎo)致其并不具有這種分類性質(zhì)。因此，網(wǎng)絡(luò)洞主的數(shù)目對于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有重要的影響。一個值得關(guān)注的問題是，具有非零數(shù)目洞主的網(wǎng)絡(luò)具有何種形式的拓?fù)浣Y(jié)構(gòu)，這種拓?fù)浣Y(jié)構(gòu)具有何種功能？ 對于上列問題的回答將有助于揭示符號網(wǎng)絡(luò)的結(jié)構(gòu)與功能的本質(zhì)，目前還鮮有這方面的報道。本文針對連接關(guān)系為全體實數(shù)的廣義符號網(wǎng)絡(luò)（復(fù)雜網(wǎng)絡(luò)）上列問題的一個特殊情況，即網(wǎng)絡(luò)中每個節(jié)點都是洞主的情況，我們提出了全洞主網(wǎng)絡(luò)的概念，并給出了一種構(gòu)成方法，最后對這樣的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析。

2 基本概念

定義3［16］（無洞主網(wǎng)絡(luò)） 對于復(fù)雜網(wǎng)絡(luò)Σ=(V E)而言，如果網(wǎng)絡(luò)中不包含洞主，則稱該網(wǎng)絡(luò)為無洞主網(wǎng)絡(luò)。

定義4［16］（可分類網(wǎng)絡(luò)）對于復(fù)雜網(wǎng)絡(luò)Σ=(V E)而言，如果該網(wǎng)絡(luò)包含m個陣營，則稱該網(wǎng)絡(luò)是可以m分類的。

定義5（鄰居集）對于一個復(fù)雜網(wǎng)絡(luò)Σ=(V E)而言，節(jié)點i的鄰居集是指與其有正連接關(guān)系的所有節(jié)點組成的集合，記為Si。

定義6（洞數(shù)）在節(jié)點i的鄰居集Si中，結(jié)構(gòu)洞的數(shù)目稱為節(jié)點i的洞數(shù)，記為hi。

3 主要結(jié)論

引理1［16］復(fù)雜網(wǎng)絡(luò)Σ=(V E)為無特權(quán)網(wǎng)絡(luò)的充分必要條件是它是可分類網(wǎng)絡(luò)（節(jié)點可分類）。

從引理1 可以看到，如果網(wǎng)絡(luò)中不包含洞主這種結(jié)構(gòu)時（無特權(quán)網(wǎng)絡(luò)）網(wǎng)絡(luò)的節(jié)點具有可分性，也就是說，含有N個節(jié)點的復(fù)雜網(wǎng)絡(luò)可以被分為a個陣營（1 ≤a≤N）。但是，一旦網(wǎng)絡(luò)中出現(xiàn)了洞主，陣營將會相互重疊，從而破壞了節(jié)點的可分類性。

推論1 對于復(fù)雜網(wǎng)絡(luò)Σ=(V E)而言，它是無特權(quán)網(wǎng)絡(luò)的充要條件是對于任何節(jié)點i都滿足hi=0。

證明：必要性假設(shè)復(fù)雜網(wǎng)絡(luò)Σ=(V E)是無特權(quán)網(wǎng)絡(luò)，那么在該網(wǎng)絡(luò)中任取三個節(jié)點i，j，k，它們之間的連接關(guān)系只有三種，如圖1所示。

圖1 無特權(quán)網(wǎng)絡(luò)中的三角連接關(guān)系

結(jié)合洞數(shù)以及鄰居集的定義，圖1 中的三種結(jié)構(gòu)中對于任意節(jié)點而言，它們的洞數(shù)都為零，因此對于整個網(wǎng)絡(luò)Σ=(V E)而言，任意節(jié)點i都滿足hi=0。

充分性使用反證法。若復(fù)雜網(wǎng)絡(luò)Σ=(V E)不是無特權(quán)網(wǎng)絡(luò)，則在網(wǎng)絡(luò)中存在圖1 中所示的洞主結(jié)構(gòu)，在上述結(jié)構(gòu)中，顯然對于節(jié)點i而言，不滿足hi=0。與命題矛盾，因此，該網(wǎng)絡(luò)為無特權(quán)網(wǎng)絡(luò)。證畢。

推論2 在無特權(quán)網(wǎng)絡(luò)中，當(dāng)節(jié)點i和節(jié)點j處于不同的陣營中時，有Si∩Sj=?（空集）。

證明：由于節(jié)點i和節(jié)點j處于不同的陣營中，記節(jié)點i處于陣營Σi=(Vi Ei)中，節(jié)點j處于陣營Σj=(Vj Ej) 中，由陣營的定義可知，Σi=(Vi Ei)是節(jié)點i的鄰居集Si，Σj=(Vj Ej)節(jié)點j的鄰居集Sj。由于該網(wǎng)絡(luò)是無特權(quán)網(wǎng)絡(luò)，陣營之間有清晰的界限，因此Si∩Sj=?（空集）。證畢。

從上面的討論中可以看出，無洞主網(wǎng)絡(luò)節(jié)點具有可分類的性質(zhì)。與之相反的全洞主網(wǎng)絡(luò)，目前換未見相關(guān)報道。我們討論如下。

定義7（全洞主網(wǎng)絡(luò)）對于一個復(fù)雜網(wǎng)絡(luò)Σ=(V E)而言，如果網(wǎng)絡(luò)中的任意一個節(jié)點都是洞主，則將該網(wǎng)絡(luò)稱為是全洞主網(wǎng)絡(luò)。

定理1 對于一個具有節(jié)點數(shù)目為偶數(shù)N（N=2k，k≥2）的無向復(fù)雜網(wǎng)絡(luò)，若每一個節(jié)點有且只有一個非正連接對象節(jié)點，則該網(wǎng)絡(luò)中每個節(jié)點都是洞主。

證明：利用數(shù)學(xué)歸納法進(jìn)行證明。

當(dāng)k=2 即N=4 時，此時網(wǎng)絡(luò)中包含四個節(jié)點，記四個節(jié)點分別為a，b，c，d。首先確定這些節(jié)點之間的連接方式。由于每個節(jié)點有且只有一個非正連接對象，不妨設(shè)節(jié)點a和b之間的連接邊非正，由已知條件可知與節(jié)點a和節(jié)點b相連接的其他連接邊均為正。進(jìn)一步地，由于節(jié)點c和節(jié)點a，b之間的連接邊均為正，則節(jié)點c與節(jié)點d之間的連接邊必須是非正的。因此，可知節(jié)點a，b，c，d分別在三角關(guān)系Δacd，Δbcd，Δcab，Δdab結(jié)構(gòu)中成為洞主。

假設(shè)當(dāng)k=k1即N1=2k1時，上述定理成立。記該網(wǎng)絡(luò)為Σ=(V E)，其中V={i|i=1,2,…,2k1} 表示的是網(wǎng)絡(luò)中有序節(jié)點的集合；E={pij|i,j∈V,i≠j}表示不同節(jié)點之間的連接邊。

則當(dāng)k=k1+1 即N=2(k1+1)時，也就是說在原來的網(wǎng)絡(luò)Σ=(V E)中增加兩個節(jié)點，假設(shè)新增加的節(jié)點為x，y，現(xiàn)在的復(fù)雜網(wǎng)絡(luò)變?yōu)榱甩病?(VˉEˉ)，其中，Vˉ=V∪{x,y}，Eˉ=E∪Ex∪Ey，Ex，Ey分別表示節(jié)點x，y與新網(wǎng)絡(luò)中其他節(jié)點之間連接邊的集合。由于當(dāng)N=2k=2k1時，上述定理成立，也就是說，對于原網(wǎng)絡(luò)Σ=(V E)而言，V中所有節(jié)點均有且只有一條非正連接邊存在，所以新的節(jié)點x，y與原網(wǎng)絡(luò)Σ=(V E)中所有節(jié)點的連接邊均為正，進(jìn)一步地，為滿足定理中的條件，只可能存在節(jié)點x，y之間的連接邊為非正的情況，因此新增節(jié)點x與y之間的連接邊必然為非正的，而x，y與原網(wǎng)絡(luò)Σ=(V E) 中節(jié)點的連接全部為正。在原網(wǎng)絡(luò)中選擇節(jié)點i與j，使得其滿足pij∈E≤0。對于全連接的復(fù)雜網(wǎng)絡(luò)Σˉ=(VˉEˉ)而言，由于節(jié)點x，y與原網(wǎng)絡(luò)中節(jié)點i，j之間的連接邊pix,pjx∈Ex和piy,pjy∈Ey一定為正，則一定存在Δixj和Δiyj，使得滿足pix,pjx,piy,pjy＞0，pij≤0。

則根據(jù)洞主的定義可知，在復(fù)雜網(wǎng)絡(luò)Σˉ=(VˉEˉ)中，節(jié)點x與y為洞主。又因為原網(wǎng)絡(luò)Σ=(V E)中的所有節(jié)點均為洞主，則新的復(fù)雜網(wǎng)絡(luò)Σˉ=(VˉEˉ)中所有節(jié)點均為洞主。

定理2 對于一個具有節(jié)點數(shù)目為奇數(shù)N（N=2k+1，k≥1）的無向復(fù)雜網(wǎng)絡(luò)，若其中2k個節(jié)點都有且只有一個非正的連接對象，而另外一個節(jié)點與網(wǎng)絡(luò)中的其他節(jié)點的連接都為正，則該網(wǎng)絡(luò)中每個節(jié)點都是洞主。

證明：記該網(wǎng)絡(luò)為Σ=(V E) ，其中，V={i|i=1,2,…,2k+1} 表示的是網(wǎng)絡(luò)中有序節(jié)點的集合；E={pij|i,j∈V,i≠j} 表示不同節(jié)點之間的連接邊。記該網(wǎng)絡(luò)中2k個節(jié)點以及它們之間的連接邊構(gòu)成的子網(wǎng)絡(luò)為Σ?=(V?E?) ，其中，V?={i|i=1,2,…,2k}表示的是子網(wǎng)絡(luò)中有序節(jié)點的集合；E?={pij|i,j∈V?,i≠j} 表示子網(wǎng)絡(luò)中不同節(jié)點之間的連接邊。當(dāng)子網(wǎng)絡(luò)Σ?=(V?E?)中的節(jié)點都有且只有一個非正的連接對象時，根據(jù)定理1 可以知道，網(wǎng)絡(luò)Σ?=(V?E?)中的所有節(jié)點都是洞主。對于第2k+1個節(jié)點而言，由定理2中的條件可知，它與其他2k個節(jié)點的連接邊都是正的。網(wǎng)絡(luò)中一定存在三角形結(jié)構(gòu)Δijk，滿足pij,pik＞0，pjk≤0，根據(jù)洞主的定義可知，在復(fù)雜網(wǎng)絡(luò)Σ=(V E)中，節(jié)點i為洞主。

4 數(shù)值仿真

本節(jié)中，我們使用文獻(xiàn)［16］中的方法2 生成了一個無特權(quán)網(wǎng)絡(luò)，同時也使用本文的方法生成一個全洞主網(wǎng)絡(luò)，然后將兩個網(wǎng)絡(luò)進(jìn)行對比，以便顯示兩個具有極端洞主數(shù)（最少與最多）的網(wǎng)絡(luò)在可分類性方面的差異性。

首先應(yīng)用文獻(xiàn)［16］中的方法，生成一個無特權(quán)網(wǎng)絡(luò)。其中，取4 組非零同符號數(shù)據(jù)（節(jié)點狀態(tài)），每組包含mi個元素，mi∈[5,10]。使得每組數(shù)據(jù)都在區(qū)間(-8,0)∪(0,8)?？梢缘玫綀D6 所示的結(jié)果。

從圖2 中可以看出，對于無洞主網(wǎng)絡(luò)而言，它的節(jié)點被分為4 個陣營，且陣營之間的界限是清楚的。處在同一個陣營中的節(jié)點之間的連接關(guān)系為正，而不同陣營之間的連接關(guān)系為非正值。

圖2 無洞主網(wǎng)絡(luò)（菱形代表節(jié)點，深色線和淺色線分別代表正連接邊和非正連接邊）

上述內(nèi)容產(chǎn)生了一個無洞主網(wǎng)絡(luò)，下面我們使用本文提出的方法，產(chǎn)生全洞主網(wǎng)絡(luò)。

假設(shè)復(fù)雜網(wǎng)絡(luò)Σ=(V E) 包含8 個節(jié)點，即N=8。

步驟1：首先對這些節(jié)點進(jìn)行編號，記為i=1,2,…,N。令V={i|i=1,2,…,N}表示節(jié)點集合。使用rand函數(shù)對每個節(jié)點賦值，使其值在區(qū)間(0,10)內(nèi)，記為ai。

步驟3：從第二個節(jié)點開始，在剩余未連接的N-3 個節(jié)點（不包括自己、已有連接的第一個節(jié)點以及已有非正值連接關(guān)系的節(jié)點j）中，任意選擇一個節(jié)點，假設(shè)為l，則產(chǎn)生第二個節(jié)點與第l個節(jié)點之間的連接關(guān)系p2l=-|a2al|，第二個節(jié)點與其他節(jié)點g之間的連接關(guān)系p2g=|a2ag|，g∈V,g≠1,2,j,l。直到網(wǎng)絡(luò)的所有連接關(guān)系全部產(chǎn)生。

步驟4：使用文獻(xiàn)［16］中的方法產(chǎn)生節(jié)點的坐標(biāo)。

通過上述的方法，我們將該網(wǎng)絡(luò)繪制在一個三維空間內(nèi)，如圖3。

從圖3 中，粗線的連接關(guān)系將每個洞主所占據(jù)的結(jié)構(gòu)洞繪制出來，我們可以看到此時復(fù)雜網(wǎng)絡(luò)中的每個節(jié)點都是洞主。此時，網(wǎng)絡(luò)中的每一個節(jié)點的鄰居集都包含6 個元素，且各節(jié)點的洞數(shù)都為3。

圖3 偶數(shù)節(jié)點的全洞主網(wǎng)絡(luò)（菱形表示節(jié)點，粗線代表節(jié)點占據(jù)結(jié)構(gòu)洞的三角結(jié)構(gòu)，細(xì)線代表其余的節(jié)點之間的正連接關(guān)系）

對于奇數(shù)節(jié)點的復(fù)雜網(wǎng)絡(luò)，例如N=9，首先生成一個8 個節(jié)點的全洞主網(wǎng)絡(luò)，然后再增加一個節(jié)點，并保證該節(jié)點與其他節(jié)點之間的連接關(guān)系都為正值，就可以保證生成的復(fù)雜網(wǎng)絡(luò)為全洞主網(wǎng)絡(luò)，如圖4。

從圖4 中我們可以看到，對于白色的節(jié)點，它的鄰居集有8 個元素，它的洞數(shù)有4 個。對于其他的節(jié)點，它的鄰居集有7 個元素，而這些節(jié)點的洞數(shù)有3 個。圖3 和圖4 分別生成了一個偶數(shù)節(jié)點和奇數(shù)節(jié)點的全洞主網(wǎng)絡(luò)。從圖3～4 中可以看到，網(wǎng)絡(luò)中每一個節(jié)點都是洞主。

圖4 奇數(shù)節(jié)點的全洞主網(wǎng)絡(luò)（菱形及白色圓形表示節(jié)點，粗線代表節(jié)點占據(jù)結(jié)構(gòu)洞的三角結(jié)構(gòu)，細(xì)線代表其余的節(jié)點之間的正連接關(guān)系）

從圖2～4 可以看出，圖2 中的無洞主網(wǎng)絡(luò)節(jié)點是可以被分類的，它可以被分為4 個界限清晰的陣營，使得每個陣營內(nèi)部的連接關(guān)系都為正，而陣營之間的連接關(guān)系為非正值。然而，當(dāng)網(wǎng)絡(luò)中出現(xiàn)洞主時，網(wǎng)絡(luò)節(jié)點的這種可分類性質(zhì)逐漸消失。從圖3～4 中看出，當(dāng)網(wǎng)絡(luò)為全洞主網(wǎng)絡(luò)時，網(wǎng)絡(luò)中的陣營完全消失。

5 結(jié)語

本文針對復(fù)雜網(wǎng)絡(luò)，首先回顧了網(wǎng)絡(luò)中結(jié)構(gòu)洞和洞主兩個基本結(jié)構(gòu)的概念，提出了節(jié)點的鄰居集和洞數(shù)的概念。之后我們回顧了當(dāng)復(fù)雜網(wǎng)絡(luò)中不包含洞主（無特權(quán)網(wǎng)絡(luò)）時，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點可分類的性質(zhì)。然而，對于網(wǎng)絡(luò)中的節(jié)點處處是洞主的情況卻沒有討論過。因此，本文首先將這樣的網(wǎng)絡(luò)稱為全洞主網(wǎng)絡(luò)，并給出了偶數(shù)節(jié)點和奇數(shù)節(jié)點全洞主網(wǎng)絡(luò)的構(gòu)成方法。之后我們使用本文提出的鄰居集和洞數(shù)等指標(biāo)對全洞主網(wǎng)絡(luò)進(jìn)行了分析，并與之前提出的無特權(quán)網(wǎng)絡(luò)在網(wǎng)絡(luò)節(jié)點可分類性質(zhì)方面進(jìn)行對比。今后，我們將在本文的基礎(chǔ)上，探究全洞主網(wǎng)絡(luò)具有怎樣的結(jié)構(gòu)性質(zhì)。