1.5　社團結構的網絡

近年來對眾多實際網絡的研究發現，它們存在一個共同的特征，稱之為網絡中的社團結構。它是指網絡中的節點可以分成組，組內節點間的連接比較稠密，組間節點的連接比較稀疏^[25]，見圖1-5。社團結構在實際系統中有著重要的意義:在社會網絡中，社團可能代表具有類似興趣愛好的人群;在引文網^[26]中，不同社團可能代表了不同的研究領域;在食物鏈網中，社團可能反映了生態系統中的子系統;在萬維網中，不同社團反映網絡的主題分類。

圖1-5　一個小型的具有社團結構性質的網絡

總之，分析大型網絡中的社團結構有很大的潛在價值，因為屬于同一社團結構的點往往具有某些相同的屬性，這便于人們發現隱藏在網絡中個體連接背后的信息。因此，對網絡中社團結構的研究是了解整個網絡結構和功能的重要途徑，網絡社團結構的劃分與度量成為新的熱點。

關于網絡中的社團結構，目前還沒有被廣泛認可的唯一的定義，較為常用的是基于相對連接頻數的定義:網絡中的節點可以分成組，組內連接稠密而組間連接稀疏。這一定義中提到的“稠密”和“稀疏”都沒有明確的判斷標準，所以在探索網絡社團結構的過程中不便使用。因此人們試圖給出一些定量化的定義，如提出了強社團和弱社團的定義。強社團的定義為:子圖H中任何一個節點與H內部節點連接的度大于其與H外部節點連接的度。弱社團的定義為:子圖H中所有節點與H內部節點的度之和大于H中所有節點與H外部節點連接的度之和。此外，還有比強社團更為嚴格的社團定義——LS集^[27]。LS集是一個由節點構成的集合，它的任何真子集與該集合內部的連邊都比與該集合外部的連邊多。另一類定義則是以連通性為標準定義的社團，稱之為派系^[28]。派系是指由3個或3個以上的節點組成的全連通子圖，即任何兩點之間都直接相連。這是要求最強的一種定義，它可以通過弱化連接條件進行拓展，形成n-派系。例如，2-派系是指子圖中的任意兩個節點不必直接相連，但最多通過一個中介點就能夠連通;3-派系是指子圖中的任意兩個節點，最多通過兩個中介點就能連通。隨著n值的增加，n-派系的要求越來越弱。這種定義允許社團間存在重疊性^[29]。所謂重疊性是指單個節點并非僅僅屬于一個社團，而是可以同時屬于多個社團。社團與社團由這些有重疊歸屬的節點相連。有重疊的社團結構問題有很好的研究價值，因為在實際系統中，個體往往同時具有多個群體的屬性。

上述社團的定義來自文獻[27]，除這個定義外，還有多種其他定義方式，文獻[6]進行了更為詳細的介紹。