一種度修正的屬性網絡隨機塊模型

鄭憶美 賈彩燕 常振海 李軒涯

1(北京交通大學計算機與信息技術學院 北京 100044)2(交通數據分析與挖掘北京市重點實驗室(北京交通大學) 北京 100044)3(天水師范學院數學與統計學院 甘肅天水 741000)4(百度在線網絡技術(北京)有限公司 北京 100085)(ymzheng@bjtu.edu.cn)

現實世界中各種各樣的人、物及二者之間的聯系構成了諸多復雜系統，這些復雜系統常常以復雜網絡的形式進行刻畫.其中，網絡中的節點表示數據對象，節點之間的邊(節點鏈接)表示數據對象之間的關系，節點度的大小表示對象與網絡中其他對象的交互緊密程度.社交關系網絡、蛋白質交互網絡、文獻引用網絡等都是復雜網絡的典型代表.

人以類聚、物以群分，復雜網絡中同樣存在著聚集現象，常被描述為社區結構.依據網絡的拓撲關系，網絡中社區結構表現為：社區內部節點連接緊密、而社區之間節點連接相對稀疏[1].這種結構也常被稱為同配結構，它具有度大的節點傾向于與網絡中其他度大的節點相連的性質.

在現實世界中，網絡中不僅存在上述傳統的社區結構，也存在其他類型的結構，如與社區結構相對的子圖內連接稀疏而子圖間連接相對緊密的二部圖結構.以英文文章中名詞形容詞搭配網絡為例，名詞和形容詞分別構成二部圖中的一個子圖(社區)，由于名詞、形容詞之間經常搭配出現，而很少自身相鄰，因此2個子圖間往往存在更多的邊.與同配結構相對，我們稱二部圖結構為異配結構(可簡單理解為違背同配結構原理的其他類型網絡結構).除此之外，星形結構、核心-外圍結構、混合結構等都是異配結構的典型代表[2].本文，我們將同配結構及異配結構統稱為廣義結構.

現有許多傳統社區檢測方法僅針對典型社區結構進行，而對真實世界中的網絡，我們往往事先未知網絡中潛在的結構.因此，不限定網絡結構的類型，檢測不同類型網絡中的廣義結構具有重要的理論和現實意義.如社交關系網絡中基于用戶興趣群體檢測進行產品推薦、互聯網中網頁主題預測、蛋白質交互網絡中蛋白質功能分析等.現有的社區檢測方法依據目標函數的不同可以分為：啟發式方法和基于概率模型的生成式方法.

典型的啟發式方法主要包括：基于模塊度優化的FN算法[3]、Louvain算法[4]；基于圖分割的KL算法[5]、歸一化割算法[6]；基于非負矩陣分解的BIGCLAM算法[7]；最小描述長度優化方法Infomap[8]以及最近的多目標演化聚類方法[9]等.這些方法的共同特點是：利用對社區的直觀經驗假設和機器學習中的聚類模型設計度量函數，進而找到近似最優解，一般適用于發現網絡中的經典社區結構.

基于隨機塊模型的概率生成式方法，包括SBM[10]，NMM[11]和DCSBM[12]等.這類方法利用網絡拓撲關系將網絡中的社區分布建模為隱變量，將實際網絡看成以社區分布為隱變量的概率生成過程，從而通過最大化似然函數求解網絡結構.與文本分析中的主題模型(如PLSA[13]，LDA[14]等)類似，該類方法具有較好的可解釋性，數學形式優美.同時由于隨機塊模型的性質，該類方法可以用于檢測相對于經典社區結構更一般的廣義結構，受到了人們的關注.

以上模型都只利用了網絡中鏈接反映的拓撲結構，然而，真實網絡中的節點間除了存在鏈接關系，節點本身還具有描述自身特性的屬性信息.如社交網絡中，對用戶的性別、年齡、學歷等的描述，本文將節點含有屬性信息的網絡簡稱為屬性網絡.在屬性網絡中，網絡節點間的關系可能就是因為節點屬性信息的相似性誘導的.如具有相同興趣且物理地址比較接近的人與人之間更容易形成朋友關系；具有相同研究興趣的學者更有可能在作者合作網絡中形成邊.因此，網絡的鏈接關系和節點的屬性信息之間可能具有一定的一致性和互補性，單純利用一方面的信息會忽略另一方面的影響.已有研究證明：節點屬性信息不但有助于提高網絡社區檢測的準確度，還可以幫助我們更好地理解網絡中存在的結構，對檢測到的網絡結構提供更好的可解釋性[15].

目前越來越多的生成式方法也逐漸面向屬性網絡展開.主要有：PCL_DC[16]，CESNA[17]，PPSB_DC[18]及NEMBP[19]等.其中，PCL_DC和CESNA是面向經典社區結構而設計的，對于網絡中的其他異配結構檢測適應性較差.同時，PCL_DC和PPSB_DC采用了兩階段投影求解方法，我們發現這種求解策略不能保證算法的收斂性[20].而NEMBP學習節點社區與屬性隱含主題之間的關系，需要同時給出網絡中隱含的社區個數和屬性主題個數，且相關研究在實驗中假設二者一致，缺乏廣泛性.

針對以上問題，我們給出了一種融合節點屬性與網絡拓撲信息的生成模型PSB_PG[20].該模型可以檢測網絡中的廣義結構，且在模型參數求解過程中使用了期望最大化(expectation-maximization, EM)算法[21]，具有較好的收斂性.同時該模型只關心社區與節點屬性的關系，允許一個社區中含有多個屬性主題，具有較好的靈活性.但PSB_PG模型在生成過程中沒有考慮真實網絡中節點度的冪律分布規律，不能準確地反映觀測網絡的結構.因此，本文在其基礎上提出了一種度修正的屬性網絡隨機塊模型DPSB_PG，結合節點度信息更好地擬合真實網絡.

DPSB_PG根據隨機塊模型中的塊結構假設和節點屬性的稀疏性假設，令節點之間的鏈接關系和節點屬性的產生都服從泊松分布，但彼此之間獨立(即獨立同分布).同時隱含假設節點的“社區結構”歸屬度和節點屬性的“主題”歸屬度共享隱變量，進而將鏈接與屬性隱性相關聯.并且，我們在該模型中引入了節點的度，通常具有較大度的節點更傾向于與其他節點相連，進而以一定概率影響網絡鏈接的生成.該模型可以反映現實世界中節點度的冪律分布，具有更好的數據擬合能力、可解釋強.最后，我們采用EM算法[21]推斷模型參數，保證了模型求解過程的收斂性.與已有同類方法及PSB_PG模型在多個真實網絡上的實驗對比顯示：所給方法DPSB_PG不但保持了PSB_PG的良好性能：適用于廣義結構檢測、收斂性好、可解釋性強等，且相對于PSB_PG等其他方法在性能上有一定程度的提升，不僅能應用于屬性網絡社區檢測，針對非屬性網絡也具有良好的適用性.

1 相關工作

1.1 基于生成式模型的網絡結構檢測

真實網絡中節點之間的鏈接關系是對網絡拓撲結構最直觀的反映.近年來，有大量的算法僅通過利用網絡中拓撲關系發現其中的“社區”.

2007年Newman等人首先提出了混合模型NMM(Newman mixture model)[11]，在給定社區數目的情況下，對觀測網絡中鏈接的生成構建概率模型，通過最大化似然函數，得到節點所在的社區.該模型定義了節點對社區的隸屬度，其思想被廣泛應用于之后的生成式方法中.同時模擬從某個“社區”中的節點向其他節點(可以來自當前“社區”，也可以來自其他“社區”)發邊的概率構建網絡，具有識別廣義結構的能力.

隨機塊模型(stochastic block model, SBM)[10]是近年來生成式方法中的主流模型.該模型定義了節點所在社區間連邊的概率，其中邊的數量的產生服從泊松分布，進而生成網絡.由于塊結構假設：2個結構間有邊的概率不受節點間差異的影響，只與結構塊有關.因此該類方法可以根據隨機塊矩陣中對角線與非對角線元素的大小識別網絡中多種不同的結構.但由于其中忽略了節點的異質度信息，可能導致與真實網絡不符.2011年Karrer和Newman在標準SBM的基礎上引入了節點期望度對網絡生成過程進行了控制，改善了SBM對真實網絡的擬合效果.并根據節點之間連邊服從泊松分布，設計得到度修正隨機塊模型(degree corrected stochastic block model, DCSBM)[12]，利用基于貪心策略的社區標簽交換思想最大化目標函數，對網絡中社區進行刻畫.

除對隨機塊模型中加入節點度信息進行修正外，許多隨機塊模型的擴展方法相繼被提出.如將節點的混合隸屬度與隨機塊模型結合，設計得到MMSB(mixed membership stochastic blockmodel)模型[22]，以檢測網絡中的重疊社區.2011年Shen等人提出廣義隨機塊模型(general stochastic blockmodel, GSB)[23].該模型假設網絡中產生一條邊的概率與邊的2個端點所在的社區及社區間的連接概率有關.同時，模型結合最小描述長度原則(minimal description length principle, MDL)[24]解決了網絡中社區數量選擇的問題，其提出使得對網絡沒有過多先驗知識情況下也能發現多種網絡結構.

1.2 基于生成式模型的屬性網絡社區檢測

屬性網絡中，除了網絡中鏈接關系能反映社區結構或其他結構外，節點屬性也體現出一定的簇或主題結構.這2種結構具有一定的一致性和互補性，同時利用這2種信息，能夠設計更有效的屬性網絡社區檢測算法.最近提出的Metacode算法[25]，雖然沒有完全利用節點屬性信息提高社區檢測的性能，但其也進一步證明了社區結構與屬性的相關性，推動了屬性網絡社區檢測的進展.

2009年Yang等人認為節點之間的連邊不僅與尾節點所在社區有關，同時也受節點流行度的影響，即尾節點流行度越大，越容易被節點連接，進而對網絡中邊的產生過程進行建模得到PCL(popularity-based conditional link)模型.進一步，在其基礎上引入內容判別模型(discriminative content model, DC)對節點內容進行邏輯回歸分析，通過共享社區和內容主題隸屬度將鏈接的生成過程與節點內容主題的回歸分析過程線性加和，構建了生成模型PCL_DC[16].最后，利用兩階段投影算法對模型求解.但該模型只考慮了尾節點的流行度對網絡生成過程的影響，且較適用于發現傳統社區結構，對網絡中含有二部圖、混合結構等其他異配結構的社區檢測問題適應性較差.

為了解決PCL模型中只考慮一種類型邊的情況，2010年Yang在其模型基礎上針對有向網絡引入節點流行度和生成度，即同時考慮了節點被其他節點連接構成邊以及連接其他節點進而構成邊2種情況，提出了生成模型PPL(popularity and productivity link model)[26].該方法更加充分地考慮了網絡拓撲結構，但同樣只適合于檢測網絡中的傳統社區結構.

之后，Chai等人繼承PPL模型和GSB模型的優點，結合DC模型構建了PPSB_DC模型[18].該模型不僅考慮了節點度的冪律分布，也融合了節點的屬性信息.為解決PCL_DC只能識別傳統社區結構的弊端，模型采用了GSB中的塊結構假設，可以識別網絡中廣義結構.在模型參數求解中，PPSB_DC同樣使用了與PCL_DC類似的兩階段投影算法.但近期研究發現[20]：這種兩階段算法不能保證收斂.

Chen等人2016年在貝葉斯框架下提出了融合節點鏈接與屬性的概率模型BNPA(Bayesian nonparametric attribute model)[27]，以解決社區數量的定義問題.該模型在NMM模型的基礎上引入社區中節點含有屬性的概率，與節點連邊共同構成生成式模型.其繼承了NMM模型的優點，因此能發現網絡中存在的廣義社區結構.并且，該模型利用非參數貝葉斯方法引入先驗信息CRP(Chinese restaurant process)[28]對社區數量進行推斷，在一定程度上解決了大多數方法需要預先定義社區數量的問題.但其可能對網絡社區數量推斷不準確，進而影響廣義結構識別的精度.

近兩年，He等人為進一步探究社區的語義關系，將網絡拓撲與節點內容聯合建模來刻畫社區及社區相關的屬性語義，構建了NEMBP(nested EM algorithm with belief propagation)模型[19].該模型假設社區和屬性主題共享潛在的類結構，對二者之間的關系進行刻畫，同時結合度修正以及多項式分布對邊和屬性的生成過程進行建模，更好地擬合了真實網絡.最后，利用BP(belief propagation)[29]算法和嵌套EM算法對模型參數進行求解.相對單層EM算法，NEMBP模型求解復雜度較高.同樣，該模型可以識別網絡中的廣義結構，但是由于模型對屬性主題的刻畫，其需要預先給定社區和內容主題個數，并在實現過程中假設二者一致，而這往往與真實網絡不符.

2 DPSB_PG模型

在對網絡進行社區檢測的過程中融入節點屬性信息可以在一定程度上改善對網絡的理解.近期我們針對屬性網絡提出了PSB_PG模型[20]，從融合節點屬性與鏈接的角度出發，根據二者之間的潛在關系構建生成式模型.然而，由于真實網絡具有無標度特性，其中節點的度分布符合冪律分布.因此各節點的鏈接情況(節點度數)分布不均勻，一般地，節點的度越大，越傾向于與其他節點相連接.近年來，相關社區檢測算法也逐漸將節點度相關的變量引入網絡生成過程中，以更加準確地擬合真實網絡.

本文主要考慮了節點度對節點間連邊的影響，以進一步提高模型對觀測網絡的擬合能力，進而構建了屬性網絡中含有節點度信息的度修正隨機塊模型DPSB_PG.該模型中網絡結構與節點屬性的生成均服從泊松分布，且二者相互獨立.值得注意的是，本文的DPSB_PG模型是對PSB_PG模型的擴展，其主要差別在于是否引入節點度這一可觀測變量，并在實驗過程中對模型的性能進一步分析.本節我們直接介紹DPSB_PG模型，第3節我們將介紹其EM算法求解過程，并在第4節對實驗進行完善，不僅證明了此改進模型度修正信息引入的有效性，同時對不同的網絡(網絡中是否考慮節點屬性信息)進一步比較，證明了該模型的可擴展性.

2.1 問題定義

為清晰理解模型中各符號的意義，表1展示了模型中的主要參數.

Table 1 Symbol Description of the DPSB_PG Model表1 模型部分符號說明

2.2 節點鏈接生成過程

因此，網絡中任意節點對(i,j)之間是否存在邊不僅與節點的社區隸屬度D、社區間連接概率矩陣Θ有關，同時受節點度的影響.通過節點度對網絡生成過程進行控制，可以更好地擬合真實情況.這里，假設節點對(i,j)間邊的生成是獨立的且服從泊松分布，可以得到節點對(i,j)之間生成一條邊的期望為

其中：

滿足歸一化約束.

與度修正隨機塊模型DCSBM[12]相對應，我們允許生成網絡中包含多邊和自環現象.因此，根據泊松分布過程，當給定參數D，Θ及觀測變量xi后，生成網絡G的概率P(A|D,Θ)為

(1)

以上網絡鏈接的生成過程中結合節點度信息進一步利用了網絡的拓撲結構，對真實網絡結構充分擬合.其中，隨機塊矩陣Θ可以對網絡中隱含的結構類型給出直觀的解釋.當其主對角線元素大且非對角線元素小時，網絡呈現傳統社區結構；當主對角線元素小且非對角線元素大時，對應社區內連接相對稀疏，社區間連接緊密的二部圖結構；其他一般情況可對應于混合社區結構.因此，本模型能在生成過程中對網絡中隱含的結構類型進行判斷，具有識別網絡中廣義結構的能力.同時，網絡中節點可能屬于一個或多個社區，而隸屬度矩陣D可以反映出節點社區的分布情況，可用于識別重疊社區(隸屬度以dir為閾值指派)或非重疊社區(隸屬度最大指派)，PSB_PG中對重疊社區檢測能力進行了比較[20]，本文重點針對非重疊社區進行實驗.

2.3 節點屬性生成過程

針對屬性網絡，通常網絡中每個節點對應的屬性往往是高維的，而對于一個社區而言，其中的節點是否含有公共屬性具有稀疏性.若一個社區中節點的屬性高度相關，也會與網絡拓撲結構一致或互補，進而促進社區的構成.因此，我們假設社區中節點屬性的生成同樣服從泊松分布.

設φrk表示社區Vr含有屬性k的概率，并構成社區相關屬性矩陣Φ=(φrk)c×K.顯然，社區內所含有的屬性信息可以為相關社區提供豐富的語義解釋，挖掘其中的主題分布.類似地，網絡中節點i具有屬性k與節點度xi、社區隸屬度D以及社區相關屬性Φ有關，則期望為

且滿足歸一化約束：

因此根據泊松分布過程，在給定參數矩陣D，Φ后，網絡中生成節點屬性的概率P(W|D,Φ)為

P(W|D,Φ)=

2.4 融合節點屬性的網絡生成過程

設社區屬性隸屬度與節點社區隸屬度共享網絡中的潛在社區，以便對二者之間隱含聯系進行刻畫.假設網絡中節點鄰接矩陣A與屬性矩陣W生成過程彼此獨立，則融合度修正信息的屬性網絡隨機塊模型DPSB_PG的聯合分布形式表示為

相應地，網絡中的鏈接和節點屬性的生成過程可總結為：

1) 以概率dir從社區Vr中抽取一個節點i且以概率djs從社區Vs中抽取一個節點j；

2) 以概率為節點對(i,j)生成一條邊：

3) 以概率φrk在社區Vr中選擇一個屬性k；

4) 以概率為節點i選擇一個屬性k：

對應概率圖模型如圖1所示：

Fig. 1 The probabilistic graph model for DPSB_PG圖1 DPSB_PG概率圖模型

3 DPSB_PG模型EM求解算法

然而，由于式(4)難以直接計算,因此本文利用處理這類問題常用的EM算法[21]求解.EM算法能保證收斂到模型的局部最大值，從而獲得模型最優參數.

根據Jensen不等式E[f(X)]≥f(EX)(f為凸函數，當且僅當X為常數時等式成立)可得到對數似然的下界：

(5)

(6)

(9)

首先，隨機初始化參數D,Θ,Φ，然后重復迭代EM算法，對式(6)和式(7)～(9)不斷更新直至目標函數收斂或達到最大迭代次數，輸出對應的模型參數D,Θ,Φ，對應最優的網絡擬合效果，具體算法過程見算法1.因此，可以通過該算法挖掘網絡中節點的社區分布情況，社區對應的屬性分布以及網絡中廣義社區結構.由于EM算法求解過程，上述參數的形式看起來與PSB_PG中參數結果相差不多，這也表明概率生成模型數學形式的優美.但實質上，節點度xi的引入直觀影響了節點所在的社區分布，同時由于潛變量的變化，會間接影響社區屬性以及網絡結構的推斷，因此相較于原PSB_PG算法仍具有一定程度的變化.

算法1.DPSB_PG模型算法.

輸入：鄰接矩陣A、屬性矩陣W、社區數量c、最大迭代次數IT和閾值ε;

輸出：模型參數D,Θ,Φ.

① 由鄰接矩陣A計算每個節點i的度xi;

② 隨機初始化模型參數D(0),Θ(0),Φ(0);

③ fort=1:ITdo

⑤ M步：根據式(7)～(9)分別更新模型參數D(t),Θ(t),Φ(t);

⑥ ift=IT或者|L(t)-L(t-1)|<εthen

⑦D=D(t),Θ=Θ(t),Φ=Φ(t)；

⑧ break；

⑨ end if

⑩ end for

由于社區隸屬度矩陣D刻畫了每個節點i在所有c個社區上的分布，基于此可以推斷網絡中節點的社區歸屬度，可以是軟劃分(即通過限定dir的閾值，超過此閾值時一個節點可以歸屬于對應的多個社區)，也可以是硬劃分(即只利用dir的最大值，限定一個節點只能歸屬于一個社區)，分別對重疊社區或非重疊社區檢測，本文主要針對非重疊社區檢測進行.隨機塊矩陣Θ反映了網絡中存在的結構類型，可以根據其對角分布推斷其是經典社區結構、還是二部圖結構或是混合結構等.社區相關屬性矩陣Φ描述了每個社區相關的屬性特征，可以通過屬性類別分析當前社區的語義，增強所識別社區的可解釋性.并且，由于EM算法自身的收斂性質保證了DPSB_PG求解算法的收斂性.

算法1的時間復雜度主要取決于EM算法對參數的更新迭代過程.其中，執行E步的時間復雜度為O(mc2+nKc)，執行M步的時間復雜度為O(nc+c2+nck)，又由于實際網絡中社區數量c常小于節點個數n且算法的最大迭代次數是IT，故算法1整體的時間復雜度可為O(IT(mc2+nKc)).

4 實驗結果及分析

4.1 評價指標

本文采用常用的標準化互信息(normalized mutual information,NMI)[30]以及F測度(pairwise F-measure,PWF)[16]2種評價指標度量本文模型與現有方法在真實網絡上的廣義結構識別效果.其分別表示為

其中，precision=|S∩T|/|S|,recall=|S∩T|/|T|分別表示算法劃分結果的精確度和召回率，S表示算法識別社區中具有相同類標的節點集合，T表示對應的真實網絡中具有相同類標的節點集合，|·|表示集合中元素數量.

利用NMI,PWF這2種指標對社區劃分的質量進行評價可較為直觀地表示算法檢測到的社區劃分與真實劃分的差異.其中二者的值介于0和1之間，值越大，表示所對應的社區劃分效果越好.

4.2 參數設置

由于節點對(i,j)所對應社區隨機塊矩陣Θ反映了網絡中隱含廣義結構的類型.因此其初始值的設置會嚴重影響算法的收斂速度與社區檢測的精度.當Θ的初始值對應的結構與真實的網絡結構一致時，算法收斂速度快，檢測結果也相對更優；相反當二者完全相反時(如真實結構是二部圖，但初始值為傳統社區結構)，算法收斂速度很慢，且容易陷入局部最小.因此，在實驗過程中，我們利用最大熵以及最大似然的思想對Θ的初始值進行預判.

在矩陣Θ=(θrs)c×c的初始值選擇中，我們考慮3種情況：主對角線元素大、非對角線元素大以及所有元素值隨機但近乎相等.這3種情況分別對應：社區結構、二部圖結構以及混合結構.因此針對每個網絡我們首先對3種初值迭代固定的少量幾步(如10步)EM并反復幾次，根據式(5)計算多次的平均似然值.最后選擇3種情形中平均似然最大時對應的Θ情況作為Θ的初始設置.

在實驗過程中，我們設置社區數量c與已知的實際網絡社區數量相等，同時不限定真實網絡的結構類型，對輸入的網絡通過上述初始化步驟進行網絡結構的預判，進而執行對網絡社區結構的檢測.

4.3 數據集描述

我們將本模型在真實屬性網絡與非屬性網絡上進行了實驗.表2、表3分別描述了本文所選用的4個真實屬性網絡數據集和6個非屬性網絡數據集的相關統計特征.

Table 2 Feature of the Attributed Networks表2 屬性網絡數據集特征

Table 3 Feature of the Non-attributed Networks表3 非屬性網絡數據集特征

4個屬性網絡數據集包括：

1) WebKB數據集(1)http://www.cs.cmu.edu/～webkb/.該數據集由Cornell，Texas，Washington，Wisconsin四所大學的網頁以及網頁間的鏈接關系構成，共包含877個節點，1 608條邊，均劃分為5個社區.同時，每個節點都關聯一個高維的二值屬性特征，由各網頁中出現的不同詞構成.該數據集的4個網絡含有的結構均為混合結構.

2) Facebook數據集(2)http://snap.stanford.edu/data/.該數據集記錄了社交網站Facebook上從2005年起的社交關系數據.這里選取其中一個數據子集，包含1 018個節點用戶，26 717條邊表示了用戶之間的朋友關系，同時每個節點由一個576維的屬性特征向量描述.

3) Cora數據集[31].該數據集為科技文獻引文網絡的一個子集，其中包含2 708個節點，代表所有的文獻，5 429條邊代表文獻之間的引用關系，共包括7種文獻類別構成的相應社區，同時每個節點都關聯一個1 433維的屬性向量.

4) Citeseer數據集[32].該數據集也是科技文獻引文網絡的一個子集，含有3 312個節點，4 732條引用關系，包括6個文獻類別構成的相應社區，同時每個節點由一個3 703維的屬性向量構成.

6個非屬性網絡數據集包括：

1) Karate數據集[33].該數據集是一所美國大學空手道俱樂部成員構成的關系網絡，包含34個節點和78條邊，由于內部矛盾分裂為2個社區.

2) Dolphins數據集[34].該數據集由新西蘭某海峽62只海豚群體的交流情況得到，海豚之間的頻繁交流構成了網絡中159條邊，分為2個社區.

3) Football數據集[1].該數據集是由美國大學生足球聯賽構建的網絡，包含115個節點和613條邊，其中節點表示各個足球隊，邊表示兩球隊之間進行過比賽，所有代表隊分為12個聯盟.

4) Adjnoun數據集[35].該數據集表示了某英文文章中形容詞與名詞的連接情況.共包含名詞、形容詞構成的112個頂點和表示二者相鄰情況的425條邊，由于形容詞與名詞大體上總是相鄰出現而很少有名詞與名詞、形容詞與形容詞相鄰的情況，因此構成了典型的二部圖網絡結構.

5) Polbooks數據集(3)http://www-personal.umich.edu/～mejn/netdata/：該數據集由關于美國政治的圖書在線購買情況構成，包含105個在線商家銷售的書籍構成的節點，節點之間共441條連邊，表示同一買家頻繁購買的書籍之間的關系，構成3個社區.

6) Polblogs數據集[36]：該數據集是由政治博客構成的網絡，包含1 490個節點和19 079條邊.節點代表網頁博客，每條邊代表網頁間超鏈接情況，原數據中節點包含了網頁政治傾向，代表了2個社區.

4.4 實驗結果對比

本節我們通過與相關工作中的提到的部分融合節點屬性的屬性網絡社區檢測方法以及只利用網絡結構的社區檢測方法分別在屬性網絡以及非屬性網絡上進行對比實驗，以驗證本文方法的有效性.

4.4.1 屬性網絡結果分析

在真實屬性網絡數據集上，我們將本文的模型DPSB_PG與現有融合節點鏈接與屬性的生成式模型NEMBP，BNPA，PPSB_DC，PCL_DC以及未改進的PSB_PG模型進行了對比實驗.為了保持公平，所有比較算法均采用原文中提及的最優參數設置.表4、表5展示了對應的NMI，PWF結果.由于EM算法迭代過程會根據初始值的不同收斂到局部最優解，我們對每個模型進行了30輪實驗，并報告了2個指標30輪的均值以及最大值.

Table 4 Comparison of NMI for Attributed Networks表4 屬性網絡NMI結果對比

Table 5 Comparison of PWF for Attributed Networks表5 屬性網絡PWF結果對比

由表4和表5可知：本文提出的DPSB_PG模型可以適用于廣義結構檢測，且對于含有混合結構的真實屬性網絡(WebKB數據集的4個網絡上)的檢測效果有明顯改善.相較于沒有考慮節點度信息的PSB_PG模型，除在屬性網絡Washington上表現略差外，我們改進的模型在其他網絡中表現更好.說明融入節點的度信息對網絡社區結構的檢測具有積極影響，使得DPSB_PG模型對數據具有較好的擬合能力.對Washington網絡，我們分析發現：該網絡規模相對較小，而其中存在多個孤立節點，因此這些節點的度分布可能會影響本模型的整體表現，相較于未引入度信息的PSB_PG模型表現略差.

BNPA模型對Cora數據集中社區結構的檢測得到了最好的效果，但由于其引入了先驗信息，需要對先驗參數進行調參，且其檢測精度依賴于社區數量估計的準確性，在其他網絡中表現效果不佳.PCL_DC模型在具有社區結構的Cora，Citeseer網絡上取得了較好的效果，但對非傳統社區結構適應性較差.進一步，我們的模型在Citeseer中表現僅次于PCL_DC，由指標NMI可知，在Facebook數據中表現最優，這也說明本模型在混合結構、社區結構網絡中均表現出良好的性能，而NEMBP，PPSB_DC模型在各個網絡中的表現具有不穩定性，NEMBP僅在Texas網絡中取得了較好的效果，PPSB_DC由于初值及收斂性的影響使得表現效果差異較大.因此，本文的DPSB_PG模型綜合性能優于其他相關算法，說明利用度修正思想以及泊松分布隨機塊模型能較好地識別屬性網絡的廣義結構.

4.4.2 非屬性網絡結果分析

原PSB_PG模型中重點針對屬性網絡，對節點屬性進行了充分分析，但對非屬性網絡中模型的表現缺少進一步比較.因此，對模型改進后，在非屬性網絡數據集中，我們對比了DPSB_PG與其他模型PSB_PG，BNPA-link，PPSB和PCL在只利用網絡拓撲信息時性能上的差異(同樣所有比較算法均采用原文中的最優參數設置).除此之外，我們的模型在生成過程中引入了節點度修正的思想，與DCSBM[12]模型類似.而二者差異之處在于：DPSB_PG模型采用EM算法求解模型參數，DCSBM模型基于貪心算法利用標簽交換思想最大化似然函數求解模型參數.因此，我們也將改進的模型與DCSBM模型進行了對比，以驗證本文算法的性能.同樣，我們將對比的前4個模型執行30輪并報告了NMI，PWF指標的均值以及最大值.為了與原文保持一致，對于DCSBM模型，我們基于貪心策略執行20次KL算法以實現標簽轉換，并報告其最大值.為保持公平，我們在與DCSBM對比時只將其與其他模型的最大值進行對比.表6、表7中展示了相應的實驗結果.

由表6和表7中結果可知，改進后的DPSB_PG模型在其中4個非屬性網絡中取得了第1或第2的表現效果，進一步表明我們的模型在僅利用網絡拓撲信息時同樣能較好地挖掘網絡的多種類型結構.在PSB_PG的基礎上引入節點度信息進行修正后，除在Adjnoun數據集上DPSB_PG效果略差外，在其他真實非屬性網絡中的效果均優于PSB_PG模型，可見度修正的引入起到了積極作用，進一步對網絡拓撲結構進行了擬合.對Adjnoun網絡，我們同樣分析發現：在其網絡規模下，孤立節點占據較大比重，因此其度分布可能會影響網絡鏈接生成過程，相較于未引入度修正信息的PSB_PG模型性能略有下降.

Table 6 Comparison of NMI for Non-attributed Networks 表6 非屬性網絡NMI結果對比

Table 7 Comparison of PWF for Non-Attributed Networks表7 非屬性網絡PWF結果對比

同樣，由于BNPA模型在生成過程中引入了先驗，通過對參數的調整可得到相對更優的社區檢測結果，因此在Karate，Dolphin，Adjnoun，Polbooks數據集中都取得了最好的效果.但由文獻[37]可知，BNPA模型在自動判斷社區數量時，與真實網絡社區數量差異明顯.更一般的情況下，我們的模型效果明顯好于PPSB以及PCL模型(除Football網絡數據集外).因PCL模型只適用于傳統的社區結構，在明顯的二部圖結構網絡Adjnoun中該模型并不適用.對DCSBM模型，其貪心優化策略正確發現了Dolphin網絡中社區結構，但對其他網絡的檢測效果相較于我們的算法較差，在這里標簽交換思想沒有額外的優勢.因此通過對比可以反映出：我們的模型在僅利用節點鏈接信息時同樣對網絡中社區結構、二部圖結構的檢測具有較好的性能.

5 結 論

融合網絡中節點之間的鏈接關系以及節點固有的屬性信息挖掘網絡中潛在的結構，并利用屬性信息增強所識別社區的可解釋性，進而揭示網絡系統的功能逐漸被人們所重視.本文在PSB_PG模型的基礎上引入節點的度信息對模型進行改進，提出了一種屬性網絡中鏈接和節點屬性產生過程都服從Poisson分布的度修正隨機塊模型DPSB_PG，以充分擬合節點度在真實世界中的冪律分布特征，并基于隨機塊特性識別網絡中廣義社區結構.并且，DPSB_PG模型易于通過EM算法進行求解，具有較好的算法收斂性.通過與現有方法在真實屬性網絡、非屬性網絡上的實驗比較研究：我們的模型能夠發現網絡中的廣義結構，如傳統的社區結構、二部圖結構以及混合結構等多種網絡結構；節點度的引入更好地擬合了真實網絡，因此識別精度優于基礎模型PSB_PG，且相較于現有的其他同類算法在性能上也有不同程度的改善.另外，該模型保持了PSB_PG模型靈活的社區語義關系學習特性以及重疊社區檢測能力.

由于EM算法在模型參數求解過程中根據網絡規模的不同，可能需要較大的計算量，進而影響模型的效率.因此，在今后的工作中，我們擬引入變分推理或隨機變分推理等其他策略加快模型參數的求解過程，在保證社區檢測精度的基礎上提高算法的計算效率，以適應更加大型的復雜網絡，更快更好地挖掘網絡中的“社區”結構.