王 艳， 熊淑华， 梁 云

（①四川大学 电子信息学院，四川 成都 610064；②西南电子电信技术研究所，四川 成都 610041）

0 引言

现实世界中包含着各种类型的复杂网络[1]，例如，科技文献引用关系网络、社会关系网络等。通常人们采用关系网络图的方式对网络中的各种关系进行描述。关系网络图由一组点和线构成，点代表网络中存在的各种实体，线则代表实体与实体之间的相互作用、社会关系等。寻找和发现复杂网络中的组织，有助于更加有效地理解和掌握网络的结构和功能[2]。

Girvan和Newman把Freeman[3]提出的点介数（Vertex Betweenness）由点推广到了边，提出了基于边介数（Edge Betweenness）的组织发现算法[4]，文中称之为Betweenness算法。一条边的边介数表示任意两节点对之间最短路径中，有几条路径经过了该边。Girvan和Newman发现组织与组织之间边的边介数远远高于组织内部边的边介数，依据这一点，Betweenness算法通过逐步移走边介数最大的边来实现组织发现。Betweenness算法简单易懂，但是却存在两点不足：①计算速度慢。Girvan和Newman在文献[5]中指出，最简情形下Betweenness算法的计算复杂度为O( m2n)，其中m、n分别为网络中的边数和顶点数；②由于Betweenness算法并不能明确指出组织发现过程应当在何时结束，这就需要事先知道网络中的组织总数。然而，在发现所有组织之前确定网络包含的组织总数是很难的，这就进一步限制了Betweenness算法的适用范围。

Ulrik Brandes提出了一种Betweenness的快速算法[6]，文中称之为Brandes算法。Brandes算法的基本思想是：任选一个顶点为中心，找到该点到图中其他顶点的最短路径，根据这些最短路径来计算每条边的边介数，然后改变中心点，再重复这个过程，直到每个顶点都被选做中心一次为止，这样对每条边的边介数都计算了两次。……