Girvan和Newman提出用邊介數（2002）來標記每條邊對網路連通性的影響。某條邊的邊介數是指網路中通過這條邊的最短路徑的數目。兩頂點間的最短路徑在無權網中為連線該頂點對的邊數最少的路徑。由此定義可知，社團間連邊的邊介數比較大，因為社團間頂點對的最短路徑必然通過它們；而社團內部邊的邊介數則比較小。
基本介紹
- 中文名：Girvan和Newman社團發現算法
- 外文名：GN community detection method
Girvan和Newman於2002年提出的分裂算法已經成為探索網路社團結構的一種經典算法,簡稱GN算法。由網路中社團的定義可知，所謂社團就是指其內部頂點的連線稠密，而與其他社團內的頂點連線稀疏。這就意味著社團與社團之間聯繫的通道比較少，一個社團到另一個社團至少要通過這些通道中的一條。如果能找到這些重要的通道，並將它們移除，那么網路就自然而然地分出了社團。Girvan和Newman提出用邊介數（2002）來標記每條邊對網路連通性的影響。某條邊的邊介數是指網路中通過這條邊的最短路徑的數目。兩頂點間的最短路徑在無權網中為連線該頂點對的邊數最少的路徑。由此定義可知，社團間連邊的邊介數比較大，因為社團間頂點對的最短路徑必然通過它們；而社團內部邊的邊介數則比較小。
GN算法的基本流程如下：
1)計算網路中各條邊的邊介數；
2)找出邊介數最大的邊，並將它移除(如果最大邊介數的邊不唯一，那么既可以隨機挑選一條邊斷開也可以將這些邊同時斷開)；
3)重新計算網路中剩餘各條邊的邊介數；
4)重複第2)、3)步,直到網路中所有的邊都被移除。
算法中包括了重複計算邊介數值的環節是十分必要的。因為當斷開邊介數值最大邊後，網路結構發生了變化，原有的數值已經不能代表斷邊後網路的結構，各條邊的邊介數需要重新計算。舉一個形象的例子：假如網路中有兩個社團，它們之間只有兩條邊相連。起初其中一條邊的邊介數最大，而另外一條邊介數較小， 則第一條邊被斷開。如果不重新計算各條邊的邊介數，那么第二條邊依據其原有邊介數值可能不會被立即斷開。如果重現計算各條邊的邊介數，那么第二條邊的邊介數可能成為最大值,會被立即斷開。這顯然會對社團結構的劃分產生重大的影響。
