网络、群体与市场 第三章

网络在现今社会所扮演的重要角色之一，是将系统的局部与全局行为联系起来。研究网络，使人们有可能解释在单个节点与边的层次发生的简单过程波及开来在整体层面产生复杂效果的现象。本章主要围绕以下几个问题来讨论一些基本的社交网络概念：信息如何通过社交网络传播；不同的节点如何在这一进程中发挥独特作用；这些结构性因素怎样影响网络本身的演化。关于这三个问题的讨论将贯穿全书，在接下来的章节中以不同形式出现。本章将以社会学的一个著名假说“弱联系的力量”[190]作为切人点展开讨论。

首先从一些背景知识和一个启发性问题人手。20世纪60年代末期，在马克•格兰

马克•格兰诺维特（MarkGranovetter)，美国斯坦福大学人文与科学学院教授，曾任该校社会学系主任，他是20世纪70年代以来全球最①诺维特①

知名的社会学家之一，主要研究领域为社会网络和经济社会学。——译者

准备博士论文期间，他采访了一批最近更换工作的人，以了解他们是如何找工作的[191]。在采访中发现，多数人都是通过私人关系介绍或获取信息找到现在的工作的。其中，更加值得注意的是，参与采访的人们所描述的私人关系对象，往往只是熟人，而非亲密的朋友。这个发现让人有些惊讶：一般来说，在找工作期间，你亲密的朋友应该是最愿意向你提供帮助的人，但为什么帮助你找到新工作的人往往是那些跟你关系一般的“熟人”呢？

格兰诺维特教授提出的这个问题的答案，将远距离友谊的两个不同角度连接起来——一种注重结构，关注点在于友谊关系在整个社交网中穿越的方式；而另一种注重关系本身，其关注点从两人之间的情谊出发，单纯考虑其关系的局部后果。从这个角度来看，该问题的答案巳经超越了找工作本身，它给人们提供了一个思考社交网络结构的更为普遍的方法。为了更好地掌握这一视角，我们首先学习一些有关社交网络的基本原则及其演化历史，然后再回来讨论格兰诺维特问题。

3.1三元闭包

第2章主要针对社交网络的静态结构进行了讨论，分析了在某一特定时间点上，节点和边的相互关系。然后在同一前提下，又学习了路径、连通分量、距离等相关概念。这种分析方式构成了思考社交网络问题的基础。事实上，许多数据集本身是静态的，为我们提供的仅是社交网络某一时刻的快照。而在针对社交网络的研究中，思考网络如何随时间的推移而演变同样具有积极意义。其中特别重要的，是导致节点的到达和离开，以及边的形成和消失的机制。

关于该问题的确切答案需要具体问题具体分析，其中，以下为最基本的原则：

在一个社交圈内，若两个人有一个共同的朋友，则这两人在未来成为朋友的可能性就会提高[347]。

我们将上述原则称为三元闭包（triadicclos（a）re)，如图3.1所示。如果节点B和节点C有一个共同的朋友A，则B和C之间一条边的形成就产生了图中三个节点（A、B和C)彼此相连的情形。在网络中，称该结构为三角形结构。“三元闭包”名称的由来，源于&C边在该三角结构中为起到“闭合”作用的第三条边，因此也称为“三元闭合”。当观察同一社交网在不同时间点的两个网络快照，则通常会发现在后来的块照中，有相当数量通过三元闭包产生的新边出现，即两个在前一张快照中有共同朋友的人，在后来的快照中也成为朋友。图2所表示的是我们可能看到的图3.1中的社交网经过一段时间后所产生的新边。

1.聚集系数

三元闭包现象对人们形成社交网络中的一些测度具有启发性，尤其是那些体现趋势的简单测度，其中之一称为聚集系数(TheCl（a）steringCoefficient)[320,411〕。节点A的聚集系数定义为A的任意两个朋友彼此也是朋友的概率。换句话说，A的聚集系数即为与A相邻的节点之间边的实际数与A相邻节点对的个数之比。例如，图3.2(a)中节点A的聚集系数是1/6(因为与A相邻的6个节点对B~C、B-D、B~E、C-D、C-E和D~E中，仅有一个边C-D),而在图3.2(b)中所示的网络快照中，该系数增加至1/2(因为在同样的6个节点对中，已有3个边B-C、C-D和EKE出现h通常，一个节点的聚集系数范围在0(该节点的朋友中没有人互相认识）和1(该节点的所有朋友彼此也都是朋友）之间，且该节点附近的三元闭包过程越强，其聚集系数就倾向于越大。

2.三元闭包的由来

三元闭包是一种非常直观和自然关系的描述，几乎所有人都能从自己的生活经历中找到相关的例子。不仅如此，经验还揭示了该关系运作的基本原因。当B和C有一个共同的朋友A，他们成为朋友的几率就会增加。原因之一在于，他们和A的关系，直接导致他们彼此见面几率的增加：如果A花时间同时与B和C在一起，则

B和C很可能因此认识彼此，并成为朋友。另一个相关的原因是，在友谊形成的过程中，B和C都和A_是朋友的事实（假定他们都知道这一点）为他们提供了陌生人之间所缺乏的基本的信任。

第三个原因是基于A有将B和C撮合为朋友的动机：如果A同时与B和C都是朋友，则若B与C不是朋友的事实可能成为A与B和C友谊的潜在压力。这个认识的基础是早期社会心理学研究提出的相关理论〔217]，而且它也以一种自然却有些令人担忧的方式在公共卫生数据中有所体现。举例来说，贝尔曼（Bearman)和穆迪(Moody)发现[48]，在社交圈中聚集系数较低的少女相比于该系数较高的人群更容易出现自杀倾向。

3.2弱联系的力量

那么，如上所述的这些理论，又如何与马克_格兰诺维特的面试问题相关联，显示出“较远的连接关系相比紧密的连接关系，更能帮助人带来新的工作机会”呢？事实上，三元闭包正是解释该现象的重要思想之一。 1.桥和捷径

首先需要明确几个前提：好的工作机会信息相对稀缺，某些人从别人那里听到一个有前途的工作机会表明他们有获取有用信息的来源。现在，让我们考虑图3.3所示的一个简单社交网络状况。

如图所示，A有4个朋友，而其中的一段朋友关系与其他的有本质不同：A和C、D和E的关系为一个闭合图形，其中每个人都与组中的其他人相连接；而A与B的关系似乎拓展到了另一个不同的社交网。我们可以就此推测，A与B关系的结构特点将给A的日常生活带来不同以往的转机：在A的闭合朋友圈中，C、D和E 有较大可能提供类似角度的意见和相近的工作机会信息，而A和B的关系则可能使他有机会接触完全不同的观点和信息。

为了更明确表示例子中A-B关系的特别，我们介绍以下定义。一个图中，巳知A和B相连，若去掉连接A和B的边会导致A和B分属不同连通分量，则该边称为桥（bridge)。换句话说，该边为其两个端点A和B间的唯一路径。

通过在第2章中关于强连通分量和小世界现象的学习，我们可以了解，桥在实际社交网络中是极其罕见的。你可能有一个成长背景与自己完全不同的朋友，似乎友谊是连接你和他的唯一桥梁，但事实是，在这个纷杂的世界中，除了你们的友谊，总还有一些其他难于发现的潜在关联存在。换句话说，如果将图3.3延伸至一个更大的社交网络，则图3.4是比较可能出现的情况。

图3.4中，A-B边并不是连接其端点的唯一路径，尽管A和B也许并没有意识到这一点——它们同时还通过一个较长的路径F、G和H相连。类似这样的结构在真实的社交网络中较之桥更为普遍，我们给出如下定义：若边A-B的端点A和B没有共同的朋友，则称边A-B为捷径（localbridge)。换句话说，删除该边将把A和B的距离增加至2以上（不含2)，则称该边为捷径。我们定义捷径的跨度为该边两端点在没有该边情况下的实际距离[190,407]。因此，图3.4中，A-B边为跨度4的捷径；同时可以查看，该图中没有其他边为捷径，因为在删除该图中的任意其他边后，其顶点的距离均不超过2。注意，捷径与三元闭包在概念上隐含着一种对立：一条边若是捷径，则不可能是三元闭包关系中的任意一边。

捷径，特别是其中跨度较大的捷径，其作用和桥无明显差异，只是不那么极端：其两个端点直接触及社交网的两个不同部分并可通过该方式获取原本离自己很遥远的信息。这是我们找到的第一个用来解释格兰诺维特教授关于找工作问题观察的社交网络结构。我们可以预计到，如果节点A需要获取全新的信息（例如找一份新工作），则对他提供帮助的很可能是(尽管不总是)一位通过捷径连接到的朋友。因为，在你所属的紧密关联的群体内，虽然每个人都热心地想要帮忙，但他们掌握的信息，多数你早已经知道了。

2.强三元闭包性质

当然，接受格兰诺维特教授访问的人并不会说：“我是通过和我以捷径相连的朋友找到现在的工作的。”如果我们认为捷径在人们找工作的例子上被过分强调，我们又怎样认识所观察到的事实，即实际上更多是关系较远的熟人提供新信息呢？ 为了便于讨论，需要区别社交网络中不同关系的强度。在为“强度”下确切定义之前，先明确其所要表达的意思，即关系的强度越大表示友谊越亲密，且互动越频繁。一般来说，关系的强度可以是一定范围内的任意值，然而，为了简化概念，并与我们的朋友/熟人二分原则相匹配，将社交网中的所有关系归为两大类：强联系（较强的关系，相对应朋友关系）和弱联系（较弱的关系，相对应熟人关系）①。

注：①将本来应该是用一个范围来表示的关系强度简化为两类关系（强/弱）已经是粗略了，还有一些其他的微妙之处需要理解。例如，这里所讨论的只适合社会网络的一个“快照”，将其中的关系分为强和弱两种，但实际上社会网络中的关系强度会随时间和情形改变。比如，公司的一个员工被临时安排到另一个部门工作一段时间，她可能会发现原来的社会网络关系的结构基本一样，但与新部门的那些人的关系增强了（因为更频繁地接触），而与老部门的那些人的关系减弱了。类似地，一个高中生可能会发现在赛季他与一个特别运动队的队友的关系变强了，但在赛季外的时候则与某些队友的关系变弱。尽管可以主要考虑到这些因素，但对我们的目的而言，我们总认为在分析过程中的关系分为两类，且不会改变。

一旦决定了按强联系和弱联系将关系分类，就可以来标注社交网络中的每一条边（强或弱）。例如，我们让图3.4所示社交网中各节点报告所相邻节点中哪些算朋

友，哪些算熟人，据此将该图标注，如图3.5所示。

现在将强联系和弱联系的概念应用回三元闭包关系。首先，回顾在讨论三元闭包关系时所包含的几个重要因素：机会、信任、动机。当所涉及的边是强联系时，这三个因素均会发挥更大的功用。由此有以下定性的假设。，

假设：设在社会网络中有A-B边和A-C边。如果这两条边都是强联系，则

很有可能形成B-C边。

为了将以上讨论具体化，格兰诺维特给出了以下更为正式(也较为极端）的定义。

定义：若节点A与节点B和C的关系均为强联系，且B和C之间无任何连接（强或弱），则称节点A违反了强三元闭包性质。否则，称节点A满足强三元闭包性质。

根据如上定义，可以检查图3.5中所有节点均满足强三元闭包性质。而如果将A-F

边性质改为“强联系”，则节点A和F均违反了强三元闭包性质：节点A与节点E和F均为强联系，而节点E和F之间并无E-F边相连;节点F同时与节点A和G强相连，而节点A和G并无直接联系。需要注意的是，根据定义，该囝中节点H也满足强三元闭包性质：事实上，H不可能违反该性质，因为它与相邻节点的关系中仅有一个为强联系。 显而易见，强三元闭包性质的极端性使我们不会指望大型社交网络的所有节点都满足，但它作为将实际问题抽象化的重要步骤，使我们能够进一步推理强联系和弱联系的结构性含义。正如在初级物理课上研究球体飞行时，常忽略空气阻力的影响。同理，在讨论社交网络问题中，一个相对严格的假设可将研究环境简单化，从而有利于问题的分析。现在将顺着已有思路继续讨论，然后回到最初的假设命题，来观察这些概念如何作用于该命题。

3.捷径和弱联系

现在已将网络中的连接关系明确划分为两大类：强联系和弱联系，这是一种纯粹局部的概念。同时，又将社交网中的边区分为捷径和非捷径，这是一种全局的结构性概念。表面上看，这两个概念间并无直接关系，但实际上，通过三元闭包概念，可以在这两者间建立起一种联系，如下所述。

断言：社交网络中，若节点A满足强三元闭包性质，并有至少两个强联系边与之相连，则与其相连的任何捷径均为弱联系。 换句话说，在假设满足强三元闭包性质及充分数目的强联系边存在的前提下，社交网络中的捷径必然为弱联系。

我们可以按照数学的方法来证明该断言，即说明它是可以从定义出发，逻辑上推导出来的结果。这个意义上，该断言有别于第2章中所见的关于全球友谊网络包含强连通分量的陈述。那是一种思辩推断(尽管具备相当的说服力），它首先要求我们相信各种关于人类友谊网的经验性表述，这些经验性表述在经过对社交网络的数据收集和分析后可能被证实，也可能被推翻。这里，我们已经对一些概念进行了数学定义，特别是捷径和强三元闭包性质，因此可在此基础上对上述断言进行论证。

论证过程实际上非常简单。使用反证法，设已知一社交网络及一节点A，满足强三元闭包性质并涉及至少两个强联系边。现在假设A与B之间有一捷径相连，且该捷径为强联系。现需要证明以上假设是不可能成立的，其中的要点如图3.6所示。首先，因为A至少涉及两个强联系边，于是B只是其中之一，则A必与另外的某节点（称为C)以强联系相连。试问：B和C间是否有边相连？因为A、B间的边为捷径，则A和B必没有共同的朋友，则&C边不存在。但由强三元闭包性质可知，由于A-B边和A-C边均为强联系边，则B-C边必然存在，两者相悖。由此可知，这样一条同为捷径和强联系的边是不可能存在的。

图3.6若A-B边是一个强联系，則B和C之间必须有一条边，于是A-B边不能是一个捷径

该断言在网络中的局部属性(联系的强度）和全局属性（捷径与否）之间建立了一个联系，同时也为我们提供了一种将纯人际关系和网络结构相关联的新型思考方式。然而，由于该论证基于一个很强的假设（主要指强三元闭包性质），在此有必要对这种简化假设对于研究该类问题所起到的重要作用略作说明。 首先，简化假设有助于从实际例子中获取定性结论，即使假设条件不够严谨。例如，数学论证也可以用生活化的语言来总结为：节点A和B间的捷径必须是弱连接，否则，根据三元闭包原理，就很可能会形成另外的短路径将A和B连接起来，从而使A-B边不成其为捷径了。我们仍可以通过初级物理课的内容来进行类比。虽然推导出小球的完美抛物线飞行轨迹的假设在现实世界并不存在，但是使用该假设所推导出的抛物线轨迹却具有非常重要的现实意义。

其次，当假设条件比较明确，就像前面的例子一样，就比较容易用真实数据来测试。在过去的几年中，科研人员就关系强度和网络结构在人数众多的社交网中的定量关系进行了研究。研究表明，先前所描述的结论在实际中也是近似成立的。下节将讨论与之相关的一些结果。

最后，该分析为一些一开始看上去令人不知所措的问题提供了一个具体的思考框架，就好比一个新的工作机会往往藏匿在与某个不太常联系的熟人关系中。该论点想要说明的是，这些为我们带来新的信息资源和机会的社交关系，其在社交网

中的“跨度”概念（捷径属性)事实上和它们作为“弱社交联系”有着直接的联系。这种联系虽然是弱的，但很有价值，它将我们引人了社交网络中难于达到的部分，这正是弱联系所带来的惊人力量。

3.3在大规模数据中的联系强度与网络结构

社会网络的结构特性与边的联系强度之间的关联，产生了关于现实生活中社会网络组织的有趣理论推测。然而，自格兰诺维特首次提出联系强度这一观念之后的很多年，由于很难找到可靠地反映现实中大规模社会网络中联系强度的数据，这些推测一直没有得到大范围的社会网络验证。

随着数字通信的出现，这种状态迅速得到改变。这种“谁和谁讲话”的网络数据显示出两个要素：两两通信的人们之间形成的网络结构，以及通过两人谈话的一些情况看出他们的关系强度的指标，例如在观察期间谈得越久，表明关系强度越大。这些正是对弱联系假说进行实验性评估所需的。

以此种方式进行综合研究，翁内拉等人通过覆盖全国人口20%的手机通信量，来研究“谁和谁讲话”网络[334]。其中，节点即手机使用者，在18周的研究期内，如果两个手机经常通话，那么就形成了由这两个手机使用者作为节点组成的一条边。由于手机在普通人中更广泛地用于私人通信(而不是用于商务目的）；又由于不存在手机号码的总目录，意昧着手机号码通常是在已经相互认识的人之间交换，于是这其中隐含着的网络可被视为在一个国家社会网络中发生谈话的一个合理样本。此外，该数据显示了在第2章中所讨论的大型社会网络的许多结构特性，包括超大连通分量，即拥有网络中大多数个体(大概84%)的一个连通分量。

1.弱联系与捷径概念的推广

前几章中的理论基于两个定义，强调明确的二分法：即一条边要么表示强联系，要么表示弱联系；要么是捷径，要么不是。当我们考察大量真实数据时，对这两种定义进行一定程度的平滑处理会更有用些。

我们前面刚指出一种如此处理联系强度的思路:可以将一条边的强度数值化，设定为这条边两端通电话的分钟总数。一旦数值化，就可以将边按照其关系强度排序。这样，对于一条指定边，我们就可以问它排在所有边中的前百分之几。 由于手机通话数据中只有很少的边是捷径，我们可以放松该定义，将某些边看成是“差不多是捷径”。由此，定义一条边（A-B)的邻里重叠度（neighborhoodoverlap)如下式：

与A、B均为邻居的节点数 与A、B寸至少一个为邻居的节点数

其中，分母部分不包括A和B本身。以图3.4为例，考虑A-F边。A-F邻里重叠度的分母取决于6个节点B、C、D、E、G和J，因为它们至少是A或F的邻居。但只有节点C既是A的邻居也是F的邻居。所以，A-F的邻里重叠度为1/6。

图3.7边的邻里重叠度作为所有边按照关系强度排序的百分位的函数 该定义的一个关键特性是，当分子为0时，这个比率为0，对应的边是捷径。捷径的概念包含在该定义中，即捷径是邻里重叠度为0的边，因此我们可以把邻里重叠度很低的边粗略视为捷径。（直觉上我们可以想到，邻里重叠度很低的边对应的节点所涉及的“社交圈”很少有共同节点。）例如，按照该定义评价图3.5中的边，A-F要比A-E更接近捷径，这也是和直觉相符的。

关系强度与邻里重叠度的实验结果

用这些定义，我们可以基于格兰诺维特的理论预测，提出一些基础性的定量问题。首先，我们可以问一条边的邻里重叠度与它的强度的相关性。弱联系的强度预测说邻里重叠度随着关系增强而增加。

实际上，这种相关性十分清晰地体现在数据0中。将网络中的边按它们的联系强度排序，图3.7表明了它们的邻里重叠度与其在排序中的百分位之间的函数关系。这样，x轴越往右，边的强度就越大，并且因为这条曲线以醒目的线性方式增长，也就对应有越来越强的邻里重叠度。这两个量之间的关系从而与理论预测相当一致①。

图3.7反映出来的测量描绘了关系强度和局部网络结构（节点的邻居）的一种联系。考虑如何用这种数据来评估理论预测的全局性结果也是很有意思的。所谓全局性结果指的是弱联系起到将包含大量强联系的紧密社区连接起来的作用。此处，欧尼拉（Ormela)等人给出了一种间接的分析，如下所述。首先，从强度最强的关系开始，按序逐一从网络中进行边删除。由于节点间连接的删除，超大强连通分量会随之逐渐变小。然后，他们做同样的操作，但是从强度最弱的关系开始，按强度的升序进行边的删除。在这种情形下，他们发现超大连通分量缩小得更加

迅速；而且，一旦一个临界数量的弱联系被删除，其残余部分会突然。这个结果是与理论预测是一致的，即弱关系在不同社区之间提供了更加关键的连接结构，将分散的社区连接起来，保持了超大连通分量全局结构的完整。

毕竟，这仅是在这种规模的网络数据上评估联系强度理论的第一步，它说明了一些固有的挑战：对于这种规模和复杂性的网络，我们不能只是简单地观其结构，试图“看其中有些什么”。一些间接的测量一定是需要的，因为人们对任何特定节点或边的含义或重要性都知之甚少。总结出更加丰富和详细的结论，依然是一个挑战。

3.4联系强度、社会媒体和被动参与

如今越来越多的社交活动在线进行了，我们一直维护和利用社会网络的方式也开始改变。例如，使用社会网络工具的用户都知道，人们将大量朋友的信息作为自己个人信息的一部分显式记录在那些站点中。以往不是这样，朋友圈相对来说是隐含的，即便是列举或者想一遍自己的朋友，对一个人来讲都是相对困难的[244]。这种情况对社会网络的结构有怎样更广泛的影响？理解这种由技术形式带来的变化是一种挑战，早在互联网在公众中流行的初期，巴瑞•威尔曼(BarryWellman)等研究人员就提出了这样的问题[413,414]，并且一直以来不断扩大其范畴。 联系强度在这类问题上表现出其重要性，它提供了一种语言，让人们可以问在线社会活动是怎么分布在不同类型的连接上的，特别是如何分布在不同强度的连接上的。当看到人们在社会网络站点上维护上百人的好友连接时，我们不禁会问这些连接中有多少对应强联系，即彼此经常联系；有多少对应弱联系，即相对交往很少。

①当然，注意到图3.7中的最右的边偏离了这种趋势也是有意思的，那些边具有最大的关系强度^对于这种偏差形成的原因不是很清楚，但很可能是，这些关系强度极强的边与用特别方式打手机的人们有关系。

1.脸谱（)的联系强度

研究者已经开始利用来自最活跃的社会媒体站点的数据来分析关系强度这类问题。在脸谱公司，卡梅伦•马龙（CameronMarlow)和他的同事们分析了记录中每个用户资料的友情链接，希M了解每个链接实际用于社交活动的程度，这已超出记录中的内容[286]。换言之，一个用户的朋友之间存在的强联系体现在哪些方面？为了用现有的资料进行精确的分析，基于一个月观察期用户的使用情况，他们定义了以下三个类型的连接。

•表示互相联系的连接。在观察期内，如果用户不仅发出信息给连接另一端的朋友，也收到来自他们的信息。

•表示单向联系的连接。如果用户向另一端连接的朋友发出一个或多个信息（不考虑对方是否有回复）。

•表示保持关系的连接。如果用户关注连接另一端朋友的消息，不考虑是否有实际的信息往来，“关注对方消息”在这里表示要么通过的新闻提醒服务（即提供朋友的更新信息）点击有关内容，或者至少两次访问朋友的信息概要。

注意，这三个类型不是相互排他的。例如，属于互相联系的连接，也总是属于单向联系连接的集合。

这种按照使用情况对连接分层的方式，让我们理解，像这样的站点，如何将所声明的好友关系，转化为大致对应于较强联系的实际社会交互的模式。通过作为一个反映这些不同交互模式的相对比例，图3.8表明—个样本用户的网络邻里，包括该用户的所有朋友，以及朋友间的所有联系。该图左上方表明用户资料中的被其承认的所有友情的集合;其他三个图分别表示保持关系、单向联系和互相联系这三个关系类型，其中的联系一个比一个稀疏。此外，当到较强联系时，网络邻里的某些部分变弱的过程比其他部分更快。例如，图3.8例中用户的邻里，可以看到两个有大量三元闭包的区域：一个在图的上半部，一个在图的右侧。然而，当限定连接仅为联系或保持关系，可以看到在图的上半部存活连接要比右边部分存活得多许多。那么，可以猜想右边部分表示用户的一些比较早期朋友的集合(或许是高中同学），他们彼此是朋友，但不是经常联系；另一方面，上半部分则包括较近期经常联系的朋友（或许是同事）。

我们可以通过图3.9的曲线来定量表达不同类型连接的相对份量。x轴表示用户声明的朋友总数，曲线分别表示一种连接类型的数量。下面有几个有趣的结论。首先，此图确认了，即便用户在自己资料页公布的朋友总数很大（500人左右），但实际联系的总数在10〜20人之间，他们关注的人(例如阅读他们的资料)数量不到50人。但在这个观察之外，马龙和他的同事们得到了一个进一步的结论，认为类似这样的媒介能够促进这种被动参与（passiveengagement),即人们通过阅读关于朋友的新闻来保持联系，即使没有通信。他们认为，这种被动网络处在一个非常有趣的中间地带，即处在保持时常交流的最强联系与很久不联系的最弱联系之间，后者常常仅存在于社会网络资料页的列表里。他们写道：“互相联系与被动参与的最明显不同表明了如信息订阅服务等技术带来的影响，如果要求这些人通过电话联系彼此，我们可能会发现类似互相联系网络的情况，即每个人只联系少数个体。但在一个大家都被动参与的环境，某些事件，例如某家有

新生儿或某人订婚了，会通过紧密联系的网络快速传出去。”

2.Twittei网站上的关系强度

人们最近在社交媒体Twitter网站上也进行了类似的研究,用户利用最多140字的简短公开消息（称为“即时消息”，tweets)参与微博这种社交活动。该网站同样具有社会网络的特性，也可以分辨出强联系和弱联系。每个用户都可以指定一组他希望追随的用户（从而可以看到他们发出的消息），也可以直接发送消息给特定的某人（在后面这种情况中，所发的消息依然是公开的，但会标注它是给特定某人的）。因此，第一种类型的互动定义了一个比较被动和弱关系的社会网络，用户很容易去追随许多人的消息而勿须直接和他们交谈。而第二种类型的互动，特别是对直接发送多条消息给其他人的用户来说，对应于一种较强的关系。 以类似马龙等人的方式，胡博曼、罗慕洛和吴分析在Twitter[222]网站的两种连接的强度比。具体来说，他们考虑每个用户在观察期他/她直接发送至少两条消息的那些用户。图3.10表明了强联系个数相对于追随对象个数的函数关系。如同在上看到的，即使有大量在线弱联系的用户，但强联系的数量也是相对不大；在这个例子中，稳定在50人以下，即使有超过1000的被追随者。

另外有一种考虑在和Twitter这样的环境下容易形成连接但强联系相对稀缺问题的方式。根据定义，每个强联系需要持续的时间投入和长期的坚持，而且即便愿意花费很多精力去建立强联系的人，最后所能实际维持的数也会达到一个极限，即受限于每天可利用的时间。弱联系形成的条件则宽松得多，只需要开始的建立，而没必要持续维护，从而一个人可以积累很多。在第13章中，当我们考虑社会网络从结构上是怎样不同于信息网络（如万维网）的时候，也会看到这种区别。

在线媒体对于维护和使用社会网络的效果是一个复杂的问题，有关研究还只是刚刚开始。但这些初步研究已经表明了，在线情况下，即使弱联系是大量的，强联系仍相对稀少，也显示了在线媒体的特性如何影响不同类型的连接传递信息的方式。

3.5闭包、结构洞和社会资本

到目前为止的讨论说明了一个观察社会网络的一般方法，即社会网络是用弱联系连接起来的若干紧密群体。这种分析主要关注于网络中不同边在结构上充当的角色：多数边在某些致密联系的模式中，少数边跨越在几个不同群体之间。

分析结构中不同节点担当的角色，也可以得到许多进一步的认识。在社会网络中，并不是所有节点都有同等机会利用到那些跨群体的边:某些节点处在多个群体交界的位置，可以用到跨越边界的边，

而另外的节点都在单一群体内部。这种差别有什么影响呢？跟随包括罗纳德•伯特(RonB（a）rt)在内的一些社会网络研究人员的思路[87]，我们可以将这个问题的答案形式化，看成是节点在网络中的不同体验。以图3.11的网络为例，特

别关心节点A和B的体验，前者在一个关系紧密群体的中心，后者在多个群体交界处。

1.嵌入性

先来看节点A。节点A所属网络邻里有很强的三元闭包特征，它有很高的聚集系数。我们记得，一个节点的聚集系数即它的邻居中两两相互为邻居的情形在所有可能中的占比。

为了分析节点A周围的结构，下面这个附加定义是有用的。我们定义网络中一条边的“嵌入性”为其两个端点共同的邻居的数量。例如，A-B边的嵌人性为2，因为节点A和B有共同的两个邻居节点E和F。该定义与前面的两个概念相关。首先，一条边的嵌人性，等于3节中定义的邻里重叠度的分子。其次，捷径就是那些嵌入性为0的边，因为按照定义，捷径是两个端点没有共同邻居的边。 图3.11的例子中，节点A的突出之处就是和它相关的边都有明显的嵌人性。社会学的一系列研究都试图论证，如果两个个体由嵌人性很高的边相连，他们就比较相互信任，他们就会对之间所发生的交往（社会、经济或其他）的诚实性有信心[117,118.193,194，395]。的确，共同朋友的存在，将两个人的交往行为“展现在”社会中了，即便那些行为是在私底下发生的。如果交往的一方行为不端，潜在就会有来自共同朋友的社会制裁和信誉后果。正如格兰诺维特教授所说：“对于背叛好友的愧疚，即使没有被发现也仍旧存在。当一个朋友发现的时候，这种愧疚感可能会增加。而当我们共同的朋友发现这种欺骗背叛而告诉另一个人时，这会使你更加难以承受。”[194].

对嵌人性为0的边来说,由于没有那么一个人同时认识交往的双方，就没有这种潜在的威胁。在这个意义上，节点B与节点C和D的交往，就要比与节点A的交往有风险。此外，节点B的行为就会比较复杂，因为她涉及到对她具有不同预期的群体，导致她的行为准则具有潜在的矛盾性[116]。

2.结构洞

到目前为止，我们一直在讨论图3.11中节点A的优势，由于其网络邻里的闭包，以及由此而产生的许多嵌入边，而自然增长。但社会学的一些相关研究（特别是B（a）n的具有影响力的工作)认为，网络中节点B所处的位置，虽然在大量捷径的末端，但同样也有一些基础性的优势。

这个论点的标准场景是代表一个组织或公司的社会网络，其中的人们一方面为共同的目标而合作，另一方面为个人职业生涯的发展暗自竞争。注意，尽管我们可

以考虑在组织机构中的正式的层次结构（包括上下级关系等），但我们更关心那些非正式的人与人之间的沟通，谁认识谁，哪些人之间经常有交谈。对大型企业的经理们的实证研究表明，一个人在公司的成功与他们对捷径的利用有关[86,87]。更一般地说，这些研究的中心论点也得到了我们一直讨论的网络原理的支持。下面进一步探讨。

回到图3.11的网络，把网络想象成表示在大型公司内部管理者之间的交往和合作。用B（a）rt的话说，节点B用与她有关的多条捷径跨越了组织里的一个结构洞（str（a）ct（a）ralhole)。结构洞看起来就是存在于网络中两个没有紧密联系的节点集合之间的“空地”。（与有严格数学定义的“捷径”不同，这里的“结构洞”是非形式化的。）下面要说明的是节点B所处的位置在多个方面要比节点A的位置优越。根据前几节的观察，第一种优势在于信息方面：节点B可以更早地获得来自网络中多个互不交叉部分的信息。每个人投入在维护组织中联系的精力有限，节点B通过积极联系多个不同的群体(而不是仅限于某个群体)更有效地投入自己的精力。

第二种优势在于，处在捷径的一端对其创造性有放大功能[87]。许多领域的经验表明，创新常常源自多个观点的意外合成，这里的每个观点本身或许是人们熟知的，但只是在不同且不相关的专业领域内部所熟知。因此，位于三个无交互群体交界处的节点B，不仅可以得到这些群体的所有信息，还有机会整合来自不同群体的信息。

最后，网络中节点B的位置意味着某种社交“把关”的机会，该节点不仅可以控制节点C和D访问她所属的群体，还可以控制她所属的群体从节点C和D的群体获取信息。这样，这个位置给予B—种权力资源。可以想象，在这种情况下，某些人会试图阻止围绕他们所在的捷径形成三角形，例如从节点C或D产生一条到达B所在群体另一节点的边，很有可能会削弱B的社交“把关者”的地位。 这最后一点表明了节点B的利益不一定与其所属的群体整体的利益一致。对于组织机构而言，促进不同群体间的信息交流是有益的，但联系桥梁的建立会有损B自身在这些群体边界的权力。需要强调的是，我们这里对结构洞的分析主要是静态的，即研究网络在一个时间点上捷径的影响。进一步的问题是，这些捷径可以存在多久（因为有一种围绕它们形成三元闭包的力量，从而使它们不复存在）？一个组织中的人们在多大程度上有意识地寻找捷径并试图保持它们？这些都还不是很清楚，是人们正在研究的课题[90,188,252,259]。

总之，节点A和B的相对位置各有利弊。节点B在群体间交界的位置，说明她的交往不是嵌入在单一群体里，于是也很少得到网络邻居们的保护。另一方面，

这种较冒风险的位置为她提供了访问多个群体信息的机会，可以控制信息流和重新整合这些信息。

3.作为社会资本形式的闭包和桥梁

所有这些论点，都是围绕从一个社会结构（社会网络）中推导个体和群体的利益的框架展开的，这很自然地与社会资(socialcapital)的概念相关[117,118,279,342,344]。社会资本是一个已被广泛应用的术语，但其定义却十分困难[138]。波特斯教授①在他的综述文章中说:“在文献中关于社会资本的共识正在提高，它代表着执行者通过在社会网络或其他社会结构中的成员地位保障其利益的能力。”[342] “社会资本”一词的表述方式使它成为一系列不同形式资本的一种，都是作为有形或无形的资源，可以动员来完成一些任务。詹姆斯•科尔曼②和一些人在谈论物理资本(physicalcapital，帮助完成任务的技术等）和人力资本（h（a）mancapital,个人实现目标的技能和才能)时讲到过社会资本[118]。皮埃尔•布迪厄③提出了一种相关但不同的分类，他从与经济资本(economiccapital)与文化资本（c（a）lt（a）ralcapital)关系的角度考虑社会资本。经济资本包括金融和有形资源，而文化资本则是一种文化的积累，其存在超出了任何个体的社会圈子，通过教育和其他大众社会机构传承[17,75]。

博尔加蒂、琼斯和埃弗里特[74]在总结社会学界讨论的时候，观察到术语“社会资本”在使用中含义变化的两个重要来源。其一，有时社会资本被视为一个群体的特性，将某些群体比其他群体的运行状态好的原因归诸于它们的社会结构或网络的优势。有时也被视为个体的特性，认为一个人拥有的社会资本与他或她在社会结构或网络的位置有关。其二，术语的变化来源在于看“社会资本”到底是纯粹属于某一群体内在的特性（仅基于群体成员间的社会交互），还是也基于群体与外界的交互。

这种一般性的看法并没有说明哪种网络结构对于创造社会资本是最有效的，本节之前提到过该问题的几个不同方面。科尔曼和其他学者关于社会资本的著作，强调了三元闭包和嵌人边的优势：它们可以强化行为准则和信誉的影响，因而能够保护社会与经济来往的诚信。另一方面，波特讨论社会资本的时候，将它看成是“闭包”（clos（a）re)和“中介”(brokerage)之间的一种张力：前者即指科尔曼的概念，后者则指由于处于不同群体交界处，跨越结构洞的中介能力所带来的好处。 除了这些方面的结构性区别外，它们的对比也解释了群体和个体的不同关注，以及群体内部的活动和它与更大群体的接触的不同。这种对比与罗伯特•普特南所说的契结资本(bondingcapital)与桥接资本（bridgingcapital)C3443的二分法有关

联，而这些术语的意思大致上分别相当于从联系紧密的群体内以及不同群体间的连接所产生的社会资本。

由此，社会资本的概念就提供了一种框架，基于它我们可以将社会结构看成是个体和群体有效行动的助推器;社会资本的概念也提供了一种讨论不同结构带来不同方面好处的方式。网络是这些研究的中心，其中既有紧密关联的群体，人们可以相互比较信任；也有不同群体间的连接，使得来自这些不同群体的信息得到融合。

①波特斯(Alejandro Portes)，美国著名移民社会学家。——译者注 ②詹姆斯•科尔曼(James Coleman),美国著名社会学家。——译者注 ③皮埃尔•布迪厄(Pierre Bo（a）rdie（a）)，法国社会学家、人类学家和哲学家。——译者注

3.6深度学习材料：之间关系的度量和图的划分

这是全书中一系列标注“深度学习材料”的第一节。“深度学习材料”出现在有关章节的最后部分，以数学的语言探索前面讲过内容的一些更高级的方面。这些内容仅是可选的，后面章节不会用到它们。同时，尽管这些章节涉及许多技术内容，但它们也是自封的，除了某些特别的数学背景外，这些必要的背景通常会在有关“深度学习材料”一节的开始部分指明。

在本章中，我们对前面提到的若干基本概念给出具体的数学定义。本章的讨论阐明了一种考虑网络的方式，即联系紧密区域和它们之间的弱联系。我们已经给出了一些概念的准确定义，例如聚集系数和捷径。在这个过程中，我们没有尝试去精确地讲什么叫“联系紧密区域”这类概念，以及怎样形式化地刻画这类区域。 到目前为止，就我们的目的而言，能够比较通俗地谈论联系紧密区域是非常有用的。根据所存在的背景不同，这个概念的准确含义也会不同，因此灵活性是有帮助的。但是，也有些场合，需要比较准确和形式化的定义。特别是，如果我们面对一个真实网络的数据，希望识别出那些稠密连接群体中的节点，形式化的定义就很关键。

因此，这里我们要来描述一种方法，它将一个网络分成一组关系紧密的区域，以及这些区域之间稀疏的互连。我们称此为围划分（graphpartitioning，又称图分割）问题，称网络经过分割得到的组成部分为“区域”（regions)。设计一种图分割方法隐含地需要给出一组有关概念的定义，既在数学上可以处理又能实际应用于真实数据集。

为了得到这样一个方法的感性认识，来看两个例子。第一个例子如图3.12所示，

画的是在网络研究方面一些物理学家和应用数学家为共同作者的关系网络[322]。回想第2章讨论的共著网络，是一种表达专业群体内合作关系的方式。从图中可以清楚地看到，这个社区中存在一些关系紧密的群体，某些人处在他们所在群体的边界上。的确，这看起来像是在一种大尺度范围内，类似于图3_11那种若干紧密群体的一些弱联系的情形。在我们视觉直觉之外，是否有一般的方法将这些群体从网络数据中抽取出来？

第二个例子如图3.13所示，是在第1章提到的怀恩•扎卡利研究过的一个空手道俱乐部的社会网络[421]:在俱乐部的负责人(节点34)和教练（节点1)之间的不和导致成两个对立的倶乐部。图3.13表现了这种网络结构，其中用灰度和白色节点分别表现了后的两个俱乐部。现在，一个自然的问题是，是否这结构自身包含足够的信息来预测分界线？也就是说，是否这种沿着两个联系紧密区域的弱界面发生？不同于图3.12的网络或本章之前的一些例子，这里两个有矛盾的群体之间依然有相当的联系。所以，要辨别这种情况下的划分，我们需要找出更加微妙的信号，反映连接两个群体的边出现在较低“密度”的部分。我们会看到事实上这是可能的。

3.6.1图划分的一种方法

有许多不同的方法来划分一个图，将其分成一些联系紧密的区域。许多方法都很有效，它们在细节上可能相当不同，我们来看一些启发这些方法设计的不同思路。

1.图划分的一般思路

一类方法着重在识别并移出那些在联系紧密区域之间的“跨接边”。一旦移出了这些连接，网络开始成大块的碎片，在这些碎片内部，可以进一步识别出跨接边，如此继续进行。我们称这些方法为图划分的分割法，因为它们不断对网络进行分割。

另一种方法从问题的另一头开始，关注网络中关系最紧密连接的部分，而不是它们交界处的联系。这种方法找到可能属于同一个区域的那些节点，把它们合在一起。这么做之后，网络就由大量组块构成，每个组块包含紧密联系区域的一些种子；然后，找出组块可以进一步融合的组块，.这样区域就“由下而上”形成了。我们称这种图分割方法为聚集法(agglomerativemethod),因为它们逐步将节点粘合到区域中来。

为了说明两种方法概念上的区别，让我们来看图3.14（a）示意的简单图。直觉上，如图3.14(b)，在由节点1〜7构成的区域和节点8〜14的区域之间，存在一个很宽的分隔。每个区域里面，都有进一步的分化:左边，分成节点1〜3和节点4〜6;右边，分成节点9〜11和节点12〜14。注意，这个简单的例子是如何说明图分割的过程，可以被视为产生自然嵌套的网络区域：大区域实际包含了很多更小甚至关系更加紧密的区域。这显然是与我们熟悉的日常生活画面一样。例如，将全球人口分成国家的群体，还可以将国家群体按区域进一步分成子群体。

事实上，有不少图分割方法可以找出如图3.14(b)中相嵌区域的集合。方法一般首先从7〜8边开始进行，然后进一步考虑包含节点7和8区域的其他边。聚集的方法，与前一个方法是殊途同归，首先找到4个三角形，然后发现三角本身很自然地成双成对。

现在可以进行比较具体的讨论了，为此我们特别考虑Girvan和Newman提出的一种方法[184，322]。Girvan-Newman方法近些年已被广泛应用，特别是在社会网络数据方面。不过，我们还是需要强调，图划分是一个特别宽的领域，有许多不同的方法都在用。我们讨论的是一个特别漂亮并被广泛应用的方法。然而，理解在不同的情况下哪种方法更适合，依然是一个活跃的研究课题。

2.介数的概念

为了启发图划分的法的设计，我们首先观察图3.14(a)，看看有哪些一般性原则会导致我们首先移除7-8边。

第一个观点由本章之前讨论的内容而来。由于桥和捷径常连接网络中联系不多的部分，所以要先将这些桥和捷径移除掉。实际上这个观点的思路是对的，但是它从两个方面看还不够强。首先，当同时存在几条桥时，没有告知哪条先被移除。正如图3.14所示，5条桥中的某些比其他的能产生更合理的划分。其次，有些图，其中没有捷径，每条边都在一个三角形中，但还是存在一种自然的分割。图3.15是一个简单例子，我们可以看出节点1〜5和节点7〜11分别形成的联系紧密的区域，尽管没有捷径要移除。

然而，如果我们更一般地想想桥和捷径的功能究竟是什么的时候，可以得出Girvan-Newman方法核心的概念。捷径是重要的，因为它们存在于网络不同部分每对节点间的最

图3.15网络可以显示成多个关系紧密的区域，即使在这些区域间没有桥梁或捷

径分隔

短路径中；若没有捷径，许多对节点间的路很可能需要改道了，导致较长的距离。因此，我们给出一种网络“流量”（traffic)的抽象定义，然后寻找承载最多流量的边。如同高速公路系统中的那些关键桥梁和主要干线，我们可以预计那些边连接不同的联系紧密的区域，因而是划分法选择移除的好对象。

流量的概念定义如下。对图中每一对其间存在一条路径的节点A和B，想象有一个单位的流体，要从A流向B(若节点A和B属于不同的连通分支，则它们之间没有路径，因而也没有流体的流动）。从A到B的信息流，将其本身均分在所有可能的最短路径上：假设节点A和B之间有k条最短路径，那么每条路径上有1/k单位的信息流。

定义一条边的介数为其承载信息流的总量，将所有节点对引起的流量都计算在内。例如，我们可以计算出图3.14(a)的每条边的介数如下。

（1）首先分析7-8边。对于图左半边的每个节点A和图右半边的每个节点B，它们之间的流量都要通过7-8边。另一方面，左右两边图内部的每对节点间的信息流都不会用到这条边。因此，7-8边的介数为7X7=49。

（2）3-7边承载了节点1、2、3和节点4〜14之间所有信息流的流量。因此，这条边的介数为3X11=33。6-7边、8-9边和8-12边也适用于这种推算。 （3）1-3边承载了除节点2外的从节点1到每个节点间的信息流。因此，它的介数均为12。根据对称原理可知，5-6边、9-10边和12-14边的介数也均为12。 （4）最后，1-2边仅承载了其两端点间信息流的流量，故介数为1。相同情况的还有4-5边、10-11边和13-14边。

因此，按照介数，选出7-8边是承载信息流最多的边。

实际上，利用介数来识别重要的边，在社会学上巳经有很长的历史了，大多数人认为是林顿•弗里曼（LintonFreeman)首先给出了明确的阐述[73，168，169]。传统上社会学家利用这种观点的时候，着重点在节点而不是边，定义基本上是一样的：一个节点的介数，即该节点所承载信息流的总量，（假设每对节点间的单位信息流，均勻地划分在最短的路径上。）如同高介数的边，髙介数的节点也在网络结构中占据重要的角色。的确，由于承载大量信息流代表其位置在关系紧密群体的交界处，因此介数与我们之前讨论的跨越社会网络结构洞的节点之间存在很清晰的关系[86]。

3.Girvan-Newman理论：不断删除离介数的边

最髙介数的边，即承载所有节点对之间最短路径上流量之和最大的边。基于这些边是连接网络不同区域的“要害”的认识，自然应被最先移除。这也是Girvan-Newman理论最核心的部分，总结如下。

(1)找出一条或多条(是有可能的）介数最髙的边，将它们从图中移除。这有可能导致该图成多个部分。这样，就得到图划分的第一层区域。

（2）重新计算所有的介数，再将介数最高的边移除。这样可能会将一些巳经存

在的部分成更小的部分。这样，就会得到一些嵌套在大区域里的小区域。 （3）用此方法继续移除图中这样的边，每步都重新计算出介数最高的边，将其移除。这样，图首先会成较大的区域，然后大区域成较小的区域，自然形成了关系紧密区域的嵌套结构。如图3.16和图3.17所示，我们看到图3.14(a)和图3.15是如何利用这个原理得到分解的。注意小区域如何通过逐步移除大区域的高介数边后显现出来。

图3.17中的步骤序列实际上展现了这个方法的一些有趣之处。

（1）在第一步的介数计算中，5-7边承载了节点1〜5到节点7〜11所有信息流，其介数为25。另一方面，5-6边仅承载了节点6到每个1〜5节点所有信息流,其介数为5(6~7边也同样)。

（2）—旦移除5-7边，第二步需要重新计算所有介数。这时，所有曾经通过这条被移除边的25个单位的信息流，就会转移到这条包含节点5、6和7的路径上，因此54边（同样6-7边）的介数增至5+25=30，这就是这两条边会在下一步被移除的原因。

在他们最初的报告中，Girvan和Newman说明了该方法如何将一些真实的网络数据集划分成直觉上觉得合理的区域集合。例如，图3.13中扎卡利的空手道倶乐部网络，利用移除边的方法，得到第一次分成两部分的图，除了一人（即图中的节点9)外，它和实际发生在俱乐部的一致。在现实中，节点9加人了教练的俱乐部，而划分后的图的分析则预示他会加入负责人的倶乐部。

扎卡利当初对空手道倶乐部的分析，用的是不同方法，尽管也用到了网络结构。基于对空手道倶乐部内部关系的实际研究，他首先用边与边之间关系强度的数值估算，来补充网络的信息。然后找出一组关系强度最弱的边，将它们删除后使节点1和节点34(对立一方的头)落到了不同的连通分量中，与他的预测相符。扎卡利所用的方法，即移除总联系强度最弱的边，将两个指定的节点分开，称为图的最小切割（minim（a）mc（a）t)问题，这是一个得到广泛研究和应用的课题[8，1，253]。对于空手道倶乐部的网络，这种最小切割方法得到如Girvan-Newmaii方法同样的分割，与实际发生的（除了节点9)一致。这种预言的一致性突显了不同的图划分方法可以得到相似结果。有趣的是，扎卡利追踪了节点9行为的异常性，归结到一个网络结构不能体现的因素：当倶乐部实际的时候，对应于节点9的人还需要三周就可以得到黑带，以此完成他4年来的追求，而这件事他只能随教练（节点1)才能实现。

在Girvan和Newman研究的其他例子中，他们对图3.12的合著网络进行了划分，所建议的顶层区域中的节点由不同的灰度表示。

毕竟，严格地评估图划分方法，形式化地说明一个要比其他方法都好是一个挑战，这不仅由于评估的目标难以形式化，还由于不同的方法对不同类型的网络具有不同的效果。进而，莱斯克弗等人的近期研究表明，在实际社会网络数据上，若网络的规模不大(例如在数百个节点量级），则比较容易从网络中分离出一个关系紧密的区域[275]。对一些不同的社会和信息网络的研究表明，超出了这个规模，要分离出来的那些节点变得比较“无法摆脱”网络的其余部分，这表明在这种数据上的图划分方法，对小网络和小区域的效果会不同于大规模图的效果。这是一个

正在发展的研究领域。

在本章的剩余部分，我们讨论最后一个重要的问题：为了运用Girvan-Newman方法，如何实际计算介数值？

3.6.2计算介数值

为了实现Girvan-Newman方法，在每步都需要先找出介数最高的边。具体做法是先算出所有边的介数，找出介数值最高的那条边。较难处理的部分是，介数的定义涉及每对节点间所有最短路径的集合。由于最短路径可能会有很多，能否有效地计算的介数，但无需列出所有这样的路径？这对于在计算机上实现能处理像样规模数据集的方法是很关键的。

事实上，有一种更聪明的介数计算方法[77，317]，它基于2.3节中先宽搜索的概念。我们从一个节点的角度来看图。对每个给定的节点，计算发自该节点的信息流在到达其他所有节点的过程中是如何分布到边上的。若对每个节点都这样计算，对于一条边来说，简单地把通过它的各个节点的信息流加起来，就得到它的介数。 我们来分析如何确定图中一个节点到其他节点的信息流。以图3.18（a）为例，特别关注节点A到其他节点的信息流。有下面三个高层步骤，后面会有更详细的解释。

(1)从节点A开始，执行先宽搜索。

(2)确定节点A到其他每个节点的最短路径的数量。

(3)基于这些数据，确定从节点A到其他所有节点的信息流量。

其中，第(1)步是先宽搜索，将一个图划分成由指定节点开始的若干层(这里的指定节点就是A)，所有在d层的节点到节点A的距离都为d。此外，从节点A到

位于d层的节点X的最短路径也就是从节点A向下向X移动所经过的路径，也就是用d步。图3.18(b)说明从图中节点A开始的先宽搜索的结果，各个层次从节点A开始向下水平放置。这样，可以看到，从节点A到F有两条最短路径(每个长度为2)：一个包含节点A、B和F，一个包含节点A、C和F。

1.计算最短路径

现在来分析第(2)步，即计算出从节点A到其他每个节点的最短路径的数量。我们有一个顺着先宽搜索向下展开的非常简明的方法。

为了体会这个方法，考虑图3.18(b)的节点I。所有从节点A到I的最短路径，在最后一步必须通过上一层的节点，即要么经过节点F，要么经过节点G。（为简化术语，如果在先宽搜索中，节点X所在层为节点Y所在层的前一层，且节点X和Y之间有边，则称节点X在节点Y上面。）而为了找出到节点I的最短路径，这条路径首先必须通过节点F或G，然后以节点I为终点。那么，从节点A到I的最短路径的数量，恰好是从节点A到F的最短路径的数量，加上从节点A到G的最短路径的数量。

我们把这个视为计算节点A到所有其他节点最短路径数量的一般方法，如图3.19所示。在第一层的每个节点都是A的一个邻居，所以它们只有一条从节点A开始的最短路径也就是从节点A到它的边。因此，每个这样的节点的值为1。现在，先宽搜索逐层向下移动，我们运用上述推理可知从A到每个节点的最短路径的数量应为先宽搜索中到“上面”那些节点最短路径数量的和。通过逐层向下移动，我们就得到从A到每个节点最短路径的数量，如图3.19所示。注意，随着这个过程进展到较深的层次，通过视觉的检查可能并不那么容易算出这些数。例如，直接列出从节点A到K的6条不同的最短路径就要费点工夫。但如此一层层做下去，就相对容易了。

2.计算出信息流的值

最后我们来分析第（3)步，如何计算从节点A到其他每个节点的信息流在边上的分布。

这里还是需要用到先宽搜索结构，但这次是从最底层开始计算。首先通过图3.20的例子来说明基本思想，然后讲述一般过程。

•首先从底部的节点K开始。一个单位的信息流到达节点K，并且从节点A到K通过节点I和J的最短路径数量相等，这个单位的信息流被等量划分在两条边上。因此可将半个单位的信息流分别放在这两条边上。 •现在开始向上移动，到达节点I的信息流总量，应该是终结在自己的一个单位加上流给K的1/2单位，即总量为3/2。这3/2信息流的总量如何从上层节点（F和G)流下来的，即如何在F-I边和G~I边上划分？从步骤(2)得出，从节点A到节点F的最短路径数是到G的最短路径的两倍，于是从F应该流出两倍的信息流。因此，从F有一个单位的信息流出，从G有半个单位的信息流出，如图3.20所示。

•继续用这种方法处理其他每个节点，通过先宽搜索逐层次向上移动。 总体而言，描述这个原理不是很难。当在先宽搜索的层次结构中自底向上进行，到达一个节点X时，将节点X下面的所有边的信息流加起来，再加上终结于节点X自身的信息流1。(由于自底向上，当到达X时，我们已经知道了下面每条边的流)然后将这总流量按到达X的上层各节点最短路径数量的比例,划分在那些节点到X的边上。可以运用这个原理，检查图3.20中的数据。

现在我们基本完成了任务。对于网络中的每一个节点，建立一个从该节点开始的先宽搜索结构，按照这个流程得到发自该节点的信息流的值，然后将这些信息流值加起来，得到每条边的介数值。需要注意的是，对于每对节点X和Y间的信息流，我们计算了两次：一次是从节点X开始进行先宽搜索，一次是从节点Y开始进行先宽搜索。因此，最后我们对所有数据除以2，以消除重复计算的影响。最后，用这些介数值，我们就能够找出介数值最髙的边，并利用Girvan-Newman方法，将它们移除。

3.最后的几点观察

刚描述的方法既可以用于计算边的阶数，又可以用于计算节点的介数。实际上，这已经在第（3)步中出现了。注意到我们不仅记录了通过边的流量，而且也隐含地记录了通过节点的流量，这正是我们计算节点介数所需的。

这里描述的Girvan-Newman方法，基于高介数边的反复移除，体现了从概念上考虑图分割问题的一种很好的方式，也适用于中型网络（可多达几百节点）。而对于大型网络，在每—步重复计算介数值的要求，从计算角度看是非常费时的。

考虑到这点，人们提出了多种不同方法，希望能更加高效地识别类似的关系紧密区域，它们包括对介数的近似[34]，以及相关但更髙效的和聚集法[35，321]。寻找能够快速处理极大规模数据的图划分方法，依然是人们很感兴趣的一个研究主题。

练习

1.用两三句话解释什么是三元闭包，以及它在社会网络形成中的作用。如有必要，可以用图例来说明。

2_分析图3.21中的图，其中每条边，除了连接b和c的边，以强联系（s)或弱联系（w)进行了标注。根据强联系和弱联系的理论，采用强三元闭包假设，你预计连接b和c的边该如何标注？请用1〜3句话简明地进行解释。

3.如图3.22所示的社会网络，每条边的属性不是强联系就是弱联系，哪些节点满足第3章中讲述的强三元闭包特性？哪些不满足这个特性？请解释你的答案。

4.如图3.23所示的社会网络，每条边的属性不是强联系就是弱联系，哪两个节点满足强三元闭包特性？请解释你的答案。

5.如图3.24所示的社会网络，每条边的属性不是强联系就是弱联系，哪些节点满足第3章中讲述的强三元闭包特性？哪些不满足这个特性？请解释你的答案。