基于洞主的廣義符號(hào)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析*

王 頎 王銀河

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

1 引言

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

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

目前，從現(xiàn)有的研究可以看出，洞主已經(jīng)成為了網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)之一［11～13］。從控制信息資源的角度看，網(wǎng)絡(luò)中洞主的存在往往會(huì)造成網(wǎng)絡(luò)中個(gè)體獲得資源能力的不平衡。 因此，也有很多學(xué)者通過對(duì)網(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é)點(diǎn)可以被分為若干個(gè)陣營(yíng)，使得陣營(yíng)內(nèi)的節(jié)點(diǎn)之間的連接關(guān)系為正值，陣營(yíng)之間的連接關(guān)系為非正值。

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

2 基本概念

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

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

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

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

3 主要結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 數(shù)值仿真

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

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

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

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

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

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

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

步驟3：從第二個(gè)節(jié)點(diǎn)開始，在剩余未連接的N-3 個(gè)節(jié)點(diǎn)（不包括自己、已有連接的第一個(gè)節(jié)點(diǎn)以及已有非正值連接關(guān)系的節(jié)點(diǎn)j）中，任意選擇一個(gè)節(jié)點(diǎn)，假設(shè)為l，則產(chǎn)生第二個(gè)節(jié)點(diǎn)與第l個(gè)節(jié)點(diǎn)之間的連接關(guān)系p2l=-|a2al|，第二個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)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é)點(diǎn)的坐標(biāo)。

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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