常美琪,肖 婧,許小可
(大連民族大學信息與通信工程學院 遼寧 大連 116600)
社團結構是將網絡中的節點組織成多個節點組集合,其中每一節點組集合中的節點間連接緊密或者共享相似的特征或角色[1]。社團結構作為復雜網絡中介于微觀和宏觀特性之間的重要中尺度特性,廣泛存在于信息、經濟、工程、生物等網絡中[2]。如在蛋白質相互作用網絡中,社團結構代表了功能相關的蛋白質集合[3];在社交網絡中,社團結構代表了某些相同興趣愛好的用戶集合[4];在引文網絡中,社團結構代表了主題相似的文獻集合[5]。社團結構揭示了網絡內在隱藏的結構規律和重要動態特性的結構起源,是網絡結構和功能間相互作用的重要途徑,因此研究社團結構具有重要的理論價值和現實意義。
考慮到社團結構是一種非常重要的中尺度特性,探索社團特性產生的內在原因,尤其是研究網絡的微觀結構特性,如度分布、匹配系數、聚類系數是如何影響網絡社團特性是非常有意義的科學問題。目前研究網絡微觀特性對社團結構影響的主要方式有兩種。一種是將原始網絡與其具有某些相似性質的隨機化網絡的社團結構進行比較,確定社團結構的顯著性,從而分析網絡社團結構特性是否由某種微觀特性衍生[6],研究發現社團結構可由聚類系數主導生成[7]。另一種是在保持網絡平均度或度序列不變的前提下,通過調節網絡中匹配系數的大小[8]或三角形模體數量分布[9-10],觀察網絡的社團數量或模塊度值的變化情況,發現僅在特殊類型網絡中匹配系數對社團結構影響明顯。相比于匹配系數,網絡中三角形結構的數量(聚類系數)變化對社團結構影響更大。
盡管上述研究發現了聚類系數這種微觀特性對于社團結構的巨大影響,但目前還存在以下兩方面的問題。一方面,在定性上無法確定描述三節點關系的聚類系數是否已經完全解釋了各類真實網絡社團性質的起源。另一方面,上述研究中沒有考慮微觀特性間的相互依賴關系,如當改變網絡聚類系數時并沒有保證網絡的匹配系數不變,就直接觀察社團結構特性的變化。網絡社團結構往往是多種微觀性質,如度分布、匹配系數、聚類系數、四節點模體分布(更高階微觀特性)等共同作用的結果,尚無法確定解耦后量化出每一種微觀結構對于社團特性貢獻程度的具體數值。此外,當前在分析網絡微觀結構對社團特性影響的研究中,所采用的實證網絡數量和類型均較為有限,導致所得的結論是否具有通用性還需要進一步驗證。
為了解決以上問題,本文從定性和定量角度出發,基于各類實證網絡構建解耦分析網絡微觀結構對社團特性影響的新框架。為了使研究結果具有魯棒性、研究結論具有通用性,本文使用了生物、社交、經濟、科技、信息網和交通6 大類不同規模的550 個實證網絡進行了實驗驗證。首先,為了揭示表征三節點關系的聚類系數是否已經可以完全解釋各類真實網絡社團性質的起源,本文基于表征不同階數微觀結構的零模型,并利用統計檢驗方法完成了真實網絡的社團結構顯著性檢測,實現了不同類型網絡微觀結構對社團特性影響的定性分析。其次,為了能夠量化出各種微觀結構對社團特性影響程度,本文提出了基于零模型和中介效應框架的微觀結構對社團特性影響的解耦分析方法,量化出各微觀結構對社團特性產生的正負影響及貢獻程度。
1)社團結構
根據網絡中節點間連接的緊密程度將網絡劃分為一個個“簇”, 將這種“簇”稱為網絡的社團結構。其中“簇”內的節點之間連接緊密,不同“簇”之間的節點連接較稀疏。
2)評價指標模塊度值Q
模塊度值Q是近年來常用的一種刻畫社團結構強弱的參數,也是一種衡量社團劃分質量的標準[13],它將原始網絡與其具有某些相同性質的隨機化網絡的社團結構進行比較,來度量社團劃分質量與社團結構強度,其定義為:
式中,aij是 實證網絡的鄰接矩陣;ki和kj分別為該網絡中節點i和 節點j的度;Ci與Cj分 別為節點i和節點j在網絡中所屬社團;當兩節點屬于同一社團,δ取值為1,否則δ 取值為0。Q的取值范圍在[0, 1],一般情況下Q越大,社團劃分質量越好,網絡的社團結構特性也越強,但當網絡規模增大時,由于分辨率限制,其對應模塊度值Q也會相應增加。
通常把與一個實證網絡具有某些相同性質的隨機網絡稱為該實證網絡的隨機化副本,這類隨機化網絡在統計學上被稱為零模型[11]。一個好的復雜網絡零模型能為原始網絡提供一個準確的基準,結合統計量指標就可以準確描述出實際復雜網絡的非平凡特性[12]。下面是對1—3 階零模型的構造過程以及與原始網絡的共性與差異進行簡要描述。
1 階零模型是在保持原始網絡度分布不變的前提下,對原始網絡中的邊進行隨機置亂操作。在微觀性質上能保證與原始網絡平均度、度序列相同,而匹配系數、聚類系數、更高階特性不能保證。具體構造過程為:在網絡中隨機選擇兩條邊斷開,隨后將這4 個節點間隨機連接成兩條邊,重連邊后的4 個節點若能與原始網絡4 節點保持相同的度分布,則斷邊重連成功。否則,撤銷先前斷邊重連操作,再重新選擇邊完成同樣的操作。根據網絡的規模與實際需求不斷重復上述操作,每次都需保證置亂前后節點度值不變,最終完成1 階零模型構造。
2 階零模型是在保持原始網絡聯合度分布不變的前提下,對原始網絡中的邊進行隨機置亂操作。在微觀性質上能保證與原始網絡平均度、度分布、匹配系數相同,而聚類系數、更高階特性沒有辦法保證。具體構造過程為:在網絡中隨機選擇兩條邊斷開,隨后將這4 個節點隨機連接成兩條邊,重連邊后的4 節點若能與原始網絡4 節點保持相同的度分布與匹配系數,則斷邊重連成功。否則,撤銷先前斷邊重連操作,再重新選擇邊完成同樣的操作。如果成立則交換邊成功,同樣根據網絡的規模與實際需求不斷重復上述操作,每次都需保證置亂前后網絡聯合度分布不變,最終完成2 階零模型構造。
3 階零模型網絡是在保持原始網絡聯合邊度分布不變的前提下,對原始網絡中的邊進行隨機置亂操作。在微觀性質上能保證與原始網絡平均度、度分布、匹配系數、聚類系數相同,而更高階微觀特性沒有辦法保證。具體構造過程如下:在網絡中隨機選擇兩條邊斷開,隨后將這4 個節點間隨機連接成兩條邊,重連邊后的4 節點若能與原始網絡4 節點保持相同度分布、匹配系數,且重連前后這4 個節點與它們的鄰居節點的三角形模體與非三角形的連通三節點模體數量相同,則斷邊重連成功。否則,撤銷先前斷邊重連操作,再重新選擇邊完成同樣的操作。同樣根據網絡的規模與實際需求不斷重復上述操作,每次都需保證置亂前后網絡聯合邊度分布不變,最終完成3 階零模型構造。
由上述1—3 階零模型構造,可以發現隨著階數的增加,斷邊的約束條件越來越多,原始網絡中滿足條件可進行隨機置亂的邊越來越少,構造出來的零模型在結構與微觀性質上越來越接近原始網絡。
利用零模型和統計檢驗方法對實證網絡社團結構特性進行顯著性分類,實現不同類型網絡微觀結構對社團特性影響的定性分析。
在利用原始網絡與零模型進行模塊度值Q比較來確定原始網絡社團結構顯著性類型時,需要使用到顯著性檢驗方法,本節使用的顯著性檢驗方法為Z 檢驗,相關概念描述如下。
Z 檢驗是一種參數檢驗方法,它利用標準正態分布理論來判斷差異發生概率,從而判斷兩組值的差異是否明顯。在本文中利用Z 檢驗來完成實際網絡與零模型網絡模塊度值Q差異的顯著性檢驗。Zi(Q)具體公式如下:
式中,Qorigin為 原始網絡的模塊度值;
式中, ?(Zi(Q))為標準正態分布。本文Z 檢驗顯著性判斷方法為:當 |Zi(Q)|<1.96 時,Pi>0.05接受原假設,差異不顯著;當 |Zi(Q)|≥1.96 時 ,Pi≤0.05拒絕原假設,差異顯著。
本文首先對各類型實證網絡進行200 次1—3階零模型構造,利用社團檢測算法對實證網絡與零模型進行社團劃分得到模塊度值Q;然后根據顯著性檢驗方法完成實證網絡與其1—3 階零模型模塊度值Q顯著性差異的計算,根據結果實現社團結構顯著性分類;最后實現微觀結構對社團特性影響的定性分析。表1 是根據各階零模型顯著性檢驗結果對社團結構顯著性類型的定義。

表1 社團結構顯著性類型定義表
從表1 中可以看出當實證網絡G 與其1 階零模型G1對應的P1>0.05時,G 與G1的社團結構不存在顯著性差異,此時稱G 不具有社團結構顯著性。當實證網絡G 與其1 階零模型G1對應的P1≤0.05, 而與其2 階零模型G2對應的P2>0.05時,G 與G1社團結構間存在顯著性差異,而與G2社團結構不存在顯著性差異,此時稱G 具有1 階社團結構顯著性。當實證網絡G 與其1 階、2 階零模型G1、G2對應的P1≤0.05、P2≤0.05,而與其3 階零模型G3對應的P3>0.05時,G 與G1、G2社團結構間存在顯著性差異,而與G3社團結構不存在顯著性差異,此時稱G 具有2 階社團結構顯著性。同理,當實證網絡G 與其1—3 階零模型模塊度Q對 應Pi≤0.05(i∈{1,2,3})都 成 立,G 與G1、G2、G3社團結構都存在顯著性差異,此時稱實證網絡G 具有3 階社團結構顯著性。
本文基于網絡社團結構顯著性分類實現微觀結構對社團特性影響定性分析的解釋說明。對于不具有社團結構顯著性的實證網絡G 而言,G 與其1 階零模型G1在社團結構上不存在顯著性差異,而從微觀結構角度來看G 與G1只具有相同的度分布,所以此時度分布即可決定實證網絡G 社團結構的產生,只要保證與G 具有相同度序列構造出來的網絡即可刻畫出與G 非常相近的社團結構。
對于具有1 階社團結構顯著性的實證網絡G 而言,因為G 與其1 階零模型G1在社團結構上存在顯著性差異,與其2 階零模型G2在社團結構上不存在顯著性差異,而G 與G1、G2在微觀結構上具有相同度分布,與G1不同的是G 與G2在微觀結構上還具有相同匹配特性,所以此時可以說度分布并不能刻畫實證網絡G 的社團結構,但匹配特性可以。
對于具有2 階社團結構顯著性的實證網絡G,因為G 與其1 階、2 階零模型G1、G2在社團結構上存在顯著性差異,與其3 階零模型G3在社團結構上不存在顯著性差異,而G3與G2在微觀結構上與原始網絡除了具有相同度分布、匹配特性外,其與G 還具有相同聚類特性,所以此時可以說度分布、匹配特性并不能刻畫實證網絡G 的社團結構,但聚類特性可以。
同理,對于具有3 階社團結構顯著性實證網絡G,因為G 與其1—3 階零模型G1、G2、G3社團結構都存在顯著性差異,而從微觀結構角度來看G3與G 具有相同度分布、匹配特性、聚類特性,此時度分布、匹配特性、聚類特性都不能刻畫其社團結構,需要更高階微觀特性才能刻畫出它的社團結構。
上述過程,實現了微觀結構對社團特性影響的定性分析。
本文從CommunityFitNet 數據庫[13]中選取了6 大類550 個不同規模的具有代表性的實證網絡,進行微觀結構對社團特性影響的定性與定量分析研究。其中,包含了124 個社交網絡、179 個生物網絡、35 個交通網絡、70 個科技網絡、124 個經濟網絡、18 個信息網絡,涵蓋了生活中網絡的大部分類型。網絡的節點規模在[48, 3 353]范圍內,連邊規模在[30, 7 562]范圍內。
在社團檢測算法的選擇上,本文選用基于層次聚類的GN 算法,它是一種基于模塊度最優化為目標進行自頂向下社團劃分的方法。GN 算法基本思想是在初始時將網絡中所有節點都歸入一個大社團,通過不斷切斷網絡中邊介數最大的邊,逐步將網絡分裂為多個社區,進而獲得層次性的社團結構。 GN 算法由于每次迭代都要考慮網絡的全局結構,導致時間復雜度較高,只適用于中小型網絡的社區劃分,但也因為這個原因其社團劃分的準確度會比較高。考慮到本文的重點是各類型實證網絡與其零模型模塊度Q差異的比較,在社團檢測算法的選擇上主要考慮其能否適用于各種類型的網絡,算法的準確度和時間復雜度不是考慮的重點,而GN 算法因其適用的網絡類型較廣泛所以被選取用于社團劃分。此外,使用其他社團檢測算法也可以得到本文類似的結論。
550 個實證網絡社團結構顯著性分類的結果如表2 所示,各類型網絡中社團結構顯著性分布最多的類型加粗標出。

表2 實證網絡社團結構顯著性檢驗統計結果
從表2 可以看出,不具有社團結構顯著性的網絡在各類型網絡中數量都非常少,其只占總體網絡數量的9.3%。對于這些網絡而言,它們的社團結構由度序列即可決定。具有1 階社團結構顯著性的網絡數量在各類型網絡中更少,其只占總體網絡數量的4.5%。對于這些網絡而言,它們的社團結構由匹配特性決定。具有2 階社團結構性顯著性的網絡數量很多,占總體數量的32.2%,且大多數分布在社交網絡中,在124 個社交網絡中有118 個具有2 階社團結構顯著性。對于這類網絡而言,它們的社團結構可以由網絡的聚類系數很好地刻畫出來,聚類系數決定了其社團結構的產生。這與文獻[7]網絡的社團結構可以由3 階度相關特性有效地刻畫(不需要更高階)的結論是一致的。
同時從表2 中也可以看出在各類型網絡中,除社交網絡外(如生物、科技、交通、經濟、信息網絡),具有3 階社團結構顯著性的網絡數量是最多的,其占總網絡數量的72.2%。對于這類網絡而言,聚類系數并不能刻畫出它們的社團結構,它們的社團結構需要更高階的微觀特性才可以刻畫出來,這和以前研究中的結論是不同的。上述結果也說明,盡管聚類系數特性對于網絡社團結構有很強的影響,但并不足以充分揭示除社交網絡之外的其他類型網絡的社團特性的主要起源。
盡管研究發現網絡的社團結構顯著性類型不唯一,但無論何種類型網絡,度序列和匹配系數對社團結構起決定性作用的數量都非常少。對于大多數社交網絡來說,它們的社團結構由3 階度相關特性(聚類系數)決定,無須更高階的微觀特性。對于其他類型網絡(如生物、科技、交通、經濟、信息網絡)來說,它們社團結構大多數并不能由3 階度相關特性決定,而由更高階的微觀特性才能決定。
基于零模型和中介效應分析框架可分辨出社團結構特性是否是由某種微觀結構貢獻,并判斷和量化出這一因素作為中介變量對社團特性的貢獻是正向的還是負向的以及貢獻程度的大小,從而實現微觀結構對社團特性影響的解耦量化分析。
中介效應分析是一個以“因果路徑”概念為中心的統計框架。在分析某一變量X對變量Y產生影響的過程中,如果變量X是通過第三個變量Z來影響變量Y,那此時第三個變量Z就是中介變量,中介變量Z在變量X和變量Y間所發揮的作用(促進/抑制)稱為中介效應。中介效應分析是檢驗變量Z是否成為中介變量,作為中介變量發揮何種中介作用以及中介程度有多大的重要步驟。
圖1 是對單中介模型的簡要介紹。在圖1a 表示自變量X對因變量Y的直接作用,在這里不涉及第三個變量,路徑系數c1代表自變量X作用于因變量Y的總效應。圖1b 表示有中介變量M參與的自變量X對因變量Y的間接作用,其中系數a代表自變量X作用于中介變量M的效應,系數b代表中介變量M作用于因變量Y的效應,兩者構成自變量X和因變量Y間的間接效應。系數c2為考慮在控制中介變量后,自變量X作用于因變量Y的直接效應。那么c1=ab+c2,中介效應分析就是檢驗ab效應是否存在,以及度量出ab效應在總效應中的占比,體現中介效應作用程度的方法。

圖1 單中介模型圖
從微觀結構對社團特性影響定性分析中我們發現隨著零模型階數的增加在微觀性質上與原始網絡越來越相似,模塊度值Q(社團結構)也越接近實證網絡,由此看出微觀結構作為中介變量對網絡社團特性起正向的貢獻作用,也就是說微觀結構對社團特性的強弱起促進作用,接下來對這種促進作用進行量化。
本文通過構造實證網絡的1—3 階零模型,計算實證網絡與零模型網絡、零模型網絡與零模型網絡間模塊度值差異的方式,依次剔除網絡微觀特性(高階特性、聚類系數、匹配系數)對社團結構貢獻,實現各社團結構顯著性類型的多種類型網絡的微觀特性(高階特性、聚類特性、匹配特性)對其社團結構產生貢獻程度的量化。
本文主要分析了匹配系數、聚類系數,以及更高階微觀特性對社團結構影響,沒有考慮度序列對社團結構的貢獻,主要原因是度量實證網絡社團結構強弱的主要指標是模塊度值。在計算模塊度值時,主要是將原始網絡與其對應一階隨機化網絡的社團結構進行比較,在保證兩者度分布序列相同的情況下來度量實證網絡社團劃分質量與社團結構強度。從這個角度看,對社團結構影響起決定性作用的微觀性質是匹配系數、聚類系數和更高階微觀特性,因此本文并沒有將度序列對社團結構貢獻進行量化。
圖2 為基于零模型和中介效應分析的微觀結構對社團特性影響的量化解耦分析框架。

圖2 基于零模型和中介效應分析的微觀結構對社團特性影響量化解耦分析研究框架
如圖2 所示,首先,通過構建實證網絡的3 階零模型剔除掉高階微觀特性,用實證網絡與其3 階零模型的模塊度值Q的差值 ΔQ/(Qorigin-Q3k)量化高階微觀特性對實證網絡社團結構產生的貢獻。其次,通過構建此3 階零模型的2 階零模型剔除掉聚類特性,用3 階零模型與其2 階零模型的模塊度值Q的差值 ΔQ=Q3k-Q2k量化聚類特性對實證網絡社團結構產生的貢獻。之后,通過構建此2 階零模型的1 階零模型剔除掉匹配特性,用2 階零模型與其1 階零模型的模塊度值Q的 差值 ΔQ=Q2k-Q1k量化匹配特性對實證網絡社團結構產生的貢獻。最后,利用剔除各微觀特性的網絡間模塊度值差值ΔQ與實證網絡和其1 階零模型的模塊度值差值做比值即 ΔQ/(Qorigin-Q1k)量化出各微觀特性(高階特性、聚類系數、匹配系數)對各社團結構顯著性類型實證社團結構產生的貢獻比例。
下面利用以上的微觀結構對社團特性影響的量化分析框架,實現各社團結構顯著性網絡的微觀結構特性(高階特性、聚類系數、匹配系數)對其社團特性產生的具體貢獻程度的量化以及相對貢獻程度的量化。對于不具有社團結構顯著性網絡,度序列對其社團結構起決定性作用,考慮到度分布是Q值計算的基礎,匹配系數、聚類系數和更高階特性對社團結構貢獻特別小幾乎為零,本文沒有對它們的貢獻進行量化。
對于具有1 階社團結構顯著性網絡,匹配系數對其社團結構起決定性作用,聚類系數和更高階特性對社團結構貢獻特別小幾乎為零,本文沒有對它們的貢獻進行量化,只需用其2 階零模型與其1 階零模型的模塊度值Q的 差值 ΔQ=Q2k-Q1k量化匹配特性對實證網絡社團結構產生的貢獻。
對于具有2 階社團結構顯著性網絡,聚類系數對其社團結構產生起決定性作用,更高階特性對社團結構產生貢獻特別小幾乎為零,本文沒有對它的貢獻進行量化,使用微觀結構對社團特性量化分析框架,計算出 ΔQ=Q2k-Q1k與 ΔQ=Q3k-Q2k量化出匹配系數、聚類系數對其社團結構產生的具體貢獻數值,再使用 ΔQ/(Qorigin-Q1k)量化出匹配系數、聚類系數對社團結構特性的相對貢獻程度。
對于具有3 階社團結構顯著性網絡,更高階特性分別對其社團結構產生起決定性作用,同理,使用微觀結構對社團特性影響量化分析框架,量化出各微觀特性(高階特性、聚類系數、匹配系數)對具有3 階社團結構顯著性的實證網絡社團結構產生的貢獻具體數值 ΔQ, 再使用 ΔQ與原始實證網絡和其1 階零模型的模塊度差值做除法得到ΔQ/(Qorigin-Q1k)量化出各微觀結構對社團特性相對貢獻程度。
考慮到2 階社團結構顯著性網絡中除社交網絡外其他網絡數量都極少,對少數網絡進行分析可能不具有代表性,本文只對具有2 階社團結構顯著性的118 個社交網絡完成匹配系數、聚類系數對社團結構貢獻的平均比例分布進行分析。實驗結果發現,對于這118 個具有2 階社團結構顯著性的社交網絡而言,其微觀特性中匹配系數比聚類系數對社團結構的貢獻程度更大,約占總貢獻的68%,而聚類系數對社團結構的貢獻只占32%。
圖3 依次為前面的具有3 階社團結構顯著性的10 個信息網絡、93 個生物網絡、27 個交通網絡、57 個科技網絡、106 個經濟網絡的微觀特性(匹配系數、聚類系數、更高階微觀特性)對社團結構貢獻的平均比例分布圖。從圖中可以看出,在具有3 階社團結構顯著性的5 種類型網絡中信息網絡的微觀特性對社團結構貢獻分布較特殊。在信息網絡的微觀特性中聚類系數對社團結構的貢獻最大,其次是更高階微觀特性,最后是匹配系數。但在其他4 類網絡中更高階微觀特性對社團結構的貢獻相對最大,且這種現象在經濟網絡中表現尤為明顯,其更高階微觀特性對社團結構的貢獻占總貢獻的90%左右。除了更高階微觀特性的貢獻外,在這4 類網絡中,生物、科技、交通網絡的聚類系數對社團結構的貢獻是最大的,匹配系數的貢獻非常小。而經濟網絡正相反,除了更高階微觀特性外,匹配系數對社團結構的貢獻最大,聚類系數的貢獻非常小。

圖3 具有3 階社團結構顯著性的各類網絡微觀特性對社團結構產生的貢獻比例分布圖
本文在實驗數據選擇方面使用社交、生物、科技、交通、經濟、信息6 類不同規模的具有代表性的550 個實證網絡進行實驗,從定性和定量角度分析微觀特性對社團結構的影響,大數據集也使結果具有魯棒性、研究結論具有通用性。
本文首先基于零模型和顯著性檢驗方法完成社團結構顯著性檢驗,實現不同類型網絡微觀結構對社團特性影響的定性分析。該結果對此前研究中聚類系數即可刻畫社團結構的結論有所修正,說明盡管聚類系數特性對于網絡社團結構有很強的影響,但是并不足以充分揭示除社交網絡之外的其他類型網絡的社團特性的主要起源。
在具有不同社團結構顯著性的各類型網絡的基礎上,本文提出了基于零模型和中介效應分析的微觀結構對社團特性影響的量化分析方法,量化出各社團結構顯著性類型網絡的各微觀結構對社團特性產生的貢獻具體數值以及相對貢獻程度。這種方法實現了對各階微觀結構對社團特性產生貢獻程度的量化。