基于洞主的廣義符號網絡拓撲結構分析*

王 頎 王銀河

（廣東工業大學自動化學院 廣州 510006）

1 引言

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

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

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

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

2 基本概念

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

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

定義5（鄰居集）對于一個復雜網絡Σ=(V E)而言，節點i的鄰居集是指與其有正連接關系的所有節點組成的集合，記為Si。

定義6（洞數）在節點i的鄰居集Si中，結構洞的數目稱為節點i的洞數，記為hi。

3 主要結論

引理1［16］復雜網絡Σ=(V E)為無特權網絡的充分必要條件是它是可分類網絡（節點可分類）。

從引理1 可以看到，如果網絡中不包含洞主這種結構時（無特權網絡）網絡的節點具有可分性，也就是說，含有N個節點的復雜網絡可以被分為a個陣營（1 ≤a≤N）。但是，一旦網絡中出現了洞主，陣營將會相互重疊，從而破壞了節點的可分類性。

推論1 對于復雜網絡Σ=(V E)而言，它是無特權網絡的充要條件是對于任何節點i都滿足hi=0。

證明：必要性假設復雜網絡Σ=(V E)是無特權網絡，那么在該網絡中任取三個節點i，j，k，它們之間的連接關系只有三種，如圖1所示。

圖1 無特權網絡中的三角連接關系

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

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

推論2 在無特權網絡中，當節點i和節點j處于不同的陣營中時，有Si∩Sj=?（空集）。

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

從上面的討論中可以看出，無洞主網絡節點具有可分類的性質。與之相反的全洞主網絡，目前換未見相關報道。我們討論如下。

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

定理1 對于一個具有節點數目為偶數N（N=2k，k≥2）的無向復雜網絡，若每一個節點有且只有一個非正連接對象節點，則該網絡中每個節點都是洞主。

證明：利用數學歸納法進行證明。

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

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

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

則根據洞主的定義可知，在復雜網絡Σˉ=(VˉEˉ)中，節點x與y為洞主。又因為原網絡Σ=(V E)中的所有節點均為洞主，則新的復雜網絡Σˉ=(VˉEˉ)中所有節點均為洞主。

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

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

4 數值仿真

本節中，我們使用文獻［16］中的方法2 生成了一個無特權網絡，同時也使用本文的方法生成一個全洞主網絡，然后將兩個網絡進行對比，以便顯示兩個具有極端洞主數（最少與最多）的網絡在可分類性方面的差異性。

首先應用文獻［16］中的方法，生成一個無特權網絡。其中，取4 組非零同符號數據（節點狀態），每組包含mi個元素，mi∈[5,10]。使得每組數據都在區間(-8,0)∪(0,8)。可以得到圖6 所示的結果。

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

圖2 無洞主網絡（菱形代表節點，深色線和淺色線分別代表正連接邊和非正連接邊）

上述內容產生了一個無洞主網絡，下面我們使用本文提出的方法，產生全洞主網絡。

假設復雜網絡Σ=(V E) 包含8 個節點，即N=8。

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

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

步驟4：使用文獻［16］中的方法產生節點的坐標。

通過上述的方法，我們將該網絡繪制在一個三維空間內，如圖3。

從圖3 中，粗線的連接關系將每個洞主所占據的結構洞繪制出來，我們可以看到此時復雜網絡中的每個節點都是洞主。此時，網絡中的每一個節點的鄰居集都包含6 個元素，且各節點的洞數都為3。

圖3 偶數節點的全洞主網絡（菱形表示節點，粗線代表節點占據結構洞的三角結構，細線代表其余的節點之間的正連接關系）

對于奇數節點的復雜網絡，例如N=9，首先生成一個8 個節點的全洞主網絡，然后再增加一個節點，并保證該節點與其他節點之間的連接關系都為正值，就可以保證生成的復雜網絡為全洞主網絡，如圖4。

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

圖4 奇數節點的全洞主網絡（菱形及白色圓形表示節點，粗線代表節點占據結構洞的三角結構，細線代表其余的節點之間的正連接關系）

從圖2～4 可以看出，圖2 中的無洞主網絡節點是可以被分類的，它可以被分為4 個界限清晰的陣營，使得每個陣營內部的連接關系都為正，而陣營之間的連接關系為非正值。然而，當網絡中出現洞主時，網絡節點的這種可分類性質逐漸消失。從圖3～4 中看出，當網絡為全洞主網絡時，網絡中的陣營完全消失。

5 結語

本文針對復雜網絡，首先回顧了網絡中結構洞和洞主兩個基本結構的概念，提出了節點的鄰居集和洞數的概念。之后我們回顧了當復雜網絡中不包含洞主（無特權網絡）時，網絡的拓撲結構和節點可分類的性質。然而，對于網絡中的節點處處是洞主的情況卻沒有討論過。因此，本文首先將這樣的網絡稱為全洞主網絡，并給出了偶數節點和奇數節點全洞主網絡的構成方法。之后我們使用本文提出的鄰居集和洞數等指標對全洞主網絡進行了分析，并與之前提出的無特權網絡在網絡節點可分類性質方面進行對比。今后，我們將在本文的基礎上，探究全洞主網絡具有怎樣的結構性質。