基于洞主的广义符号网络拓扑结构分析*

王 颀 王银河

（广东工业大学自动化学院 广州 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 结语

本文针对复杂网络，首先回顾了网络中结构洞和洞主两个基本结构的概念，提出了节点的邻居集和洞数的概念。之后我们回顾了当复杂网络中不包含洞主（无特权网络）时，网络的拓扑结构和节点可分类的性质。然而，对于网络中的节点处处是洞主的情况却没有讨论过。因此，本文首先将这样的网络称为全洞主网络，并给出了偶数节点和奇数节点全洞主网络的构成方法。之后我们使用本文提出的邻居集和洞数等指标对全洞主网络进行了分析，并与之前提出的无特权网络在网络节点可分类性质方面进行对比。今后，我们将在本文的基础上，探究全洞主网络具有怎样的结构性质。