（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，164，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中的数据。