Girvan和Newman社團發現演算法

Girvan和Newman於2002年提出的分裂演算法已經成為探索網路社團結構的一種經典演算法,簡稱GN演算法。由網路中社團的定義可知，所謂社團就是指其內部頂點的連接稠密，而與其他社團內的頂點連接稀疏。這就意味著社團與社團之間聯繫的通道比較少，一個社團到另一個社團至少要通過這些通道中的一條。如果能找到這些重要的通道，並將它們移除，那麼網路就自然而然地分出了社團。Girvan和Newman提出用邊介數（2002）來標記每條邊對網路連通性的影響。某條邊的邊介數是指網路中通過這條邊的最短路徑的數目。兩頂點間的最短路徑在無權網中為連接該頂點對的邊數最少的路徑。由此定義可知，社團間連邊的邊介數比較大，因為社團間頂點對的最短路徑必然通過它們；而社團內部邊的邊介數則比較小。

GN演算法的基本流程如下：

1)計算網路中各條邊的邊介數；

2)找出邊介數最大的邊，並將它移除(如果最大邊介數的邊不唯一，那麼既可以隨機挑選一條邊斷開也可以將這些邊同時斷開)；

3)重新計算網路中剩餘各條邊的邊介數；

4)重複第2)、3)步,直到網路中所有的邊都被移除。

演算法中包括了重複計算邊介數值的環節是十分必要的。因為當斷開邊介數值最大邊後，網路結構發生了變化，原有的數值已經不能代表斷邊後網路的結構，各條邊的邊介數需要重新計算。舉一個形象的例子：假如網路中有兩個社團，它們之間只有兩條邊相連。起初其中一條邊的邊介數最大，而另外一條邊介數較小， 則第一條邊被斷開。如果不重新計算各條邊的邊介數，那麼第二條邊依據其原有邊介數值可能不會被立即斷開。如果重現計算各條邊的邊介數，那麼第二條邊的邊介數可能成為最大值,會被立即斷開。這顯然會對社團結構的劃分產生重大的影響。

1.Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.

摘自百度百科詞條