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中的步骤序列实际上展现了这个方法的一些有趣之处。