基于正則無回路矩陣的網(wǎng)絡(luò)社團數(shù)目估計

王 林，趙月娥

(西安理工大學(xué) 自動化與信息工程學(xué)院，陜西 西安 710048)

基于正則無回路矩陣的網(wǎng)絡(luò)社團數(shù)目估計

王 林，趙月娥

(西安理工大學(xué) 自動化與信息工程學(xué)院，陜西 西安 710048)

針對社團檢測中社團數(shù)目未知的問題，提出一種基于正則無回路矩陣的社團數(shù)目估計方法。該方法通過定義一種正則無回路矩陣并利用其譜特性對網(wǎng)絡(luò)中社團數(shù)目進行估計。該方法計算高效，并且能夠適用于隨機塊模型和度糾正隨機塊模型。利用兩種人工網(wǎng)絡(luò)進行驗證，實驗結(jié)果表明，相比基于無回路矩陣的估計方法，該方法重點消除了度異質(zhì)分布對社團數(shù)目估計的影響，從而提高了估計結(jié)果的準(zhǔn)確率。

隨機塊模型；度糾正隨機塊模型；正則無回路矩陣；社團數(shù)目

0 引言

復(fù)雜網(wǎng)絡(luò)廣泛存在于自然界和人類社會，如地震網(wǎng)、萬維網(wǎng)、朋友關(guān)系網(wǎng)和科學(xué)家合作網(wǎng)等[1]。大量研究表明，許多真實的復(fù)雜網(wǎng)絡(luò)中都呈現(xiàn)出社團結(jié)構(gòu)特性，那么對社團檢測是了解整個網(wǎng)絡(luò)結(jié)構(gòu)和功能的重要途徑。

目前已有諸多社團檢測方法[2-4]，其中大多數(shù)方法依賴于網(wǎng)絡(luò)社團數(shù)目這一先驗知識，然而社團數(shù)目在實際網(wǎng)絡(luò)中通常是未知的，這極大地限制了這些方法的應(yīng)用。鑒于此，許多學(xué)者致力于研究如何預(yù)先估計網(wǎng)絡(luò)中的社團數(shù)目。Saldana等人[5]提出了一種基于似然的方法，但是對大規(guī)模網(wǎng)絡(luò)而言該方法收斂速度慢且計算復(fù)雜度高；Chauhan等人[6]提出了一種基于鄰接矩陣主特征值分布的方法，對于相對稀疏的網(wǎng)絡(luò)而言，該方法收斂速度慢、計算成本高且只適用于隨機塊模型；Shen等人[7]提出了一種基于模塊度矩陣非負(fù)特征值的方法，但是該方法只能確定網(wǎng)絡(luò)中社團數(shù)目的上限；Chen等人[8]提出了一種交叉驗證法，該方法雖然實現(xiàn)簡單但計算開銷巨大。此外，Le等人[9]提出了一種基于無回路矩陣的方法，該方法根據(jù)無回路矩陣主特征值估計社團數(shù)目，但是當(dāng)網(wǎng)絡(luò)在社團大小或邊密度任何一方不均衡時，該方法的準(zhǔn)確性就會下降。

針對上述研究中所出現(xiàn)的問題，本文提出了一種新的社團數(shù)目估計方法，該方法定義了一種新的矩陣，即正則無回路矩陣，并根據(jù)該矩陣的本征間隙最大位置估計社團數(shù)目。由于該方法在矩陣定義時對節(jié)點度進行了歸一化處理，因此很好地消除了邊密度不均衡對方法準(zhǔn)確性的影響，并且在整個估計過程中只需計算矩陣的幾個實特征值，從而降低了社團數(shù)目估計過程中不必要的計算開銷，同時該方法可適用于不同的網(wǎng)絡(luò)生成模型。

1 無回路矩陣

無回路矩陣是一種描述稀疏網(wǎng)絡(luò)中譜分析法特性的矩陣，記為B。該矩陣采用兩條單向邊代替節(jié)點i和j之間的連邊，一條邊是從i指向j，另一條從j指向i。假設(shè)網(wǎng)絡(luò)中有m條邊，則矩陣B為2m維矩陣。一條為i→j、k→l的路徑，若滿足i≠l且j=k的條件，則矩陣元素為1，反之矩陣元素為0。簡言之，這條路徑不會形成閉合回路，所以形象地稱之為無回路路徑，相應(yīng)的以無回路路徑為元素的矩陣稱為無回路矩陣。該矩陣的公式化定義為[10]:

(1)

2 正則無回路矩陣

當(dāng)網(wǎng)絡(luò)的度異質(zhì)分布時，基于無回路矩陣的社團數(shù)目估計方法的準(zhǔn)確性就會下降。因此，通過譜分析法估計社團數(shù)目，若想要得到準(zhǔn)確的結(jié)果就必須考慮節(jié)點度異質(zhì)這一影響因素。本文定義一種正則無回路矩陣，記為Bnorm。從數(shù)學(xué)角度來講，正則無回路矩陣的定義思路：將無回路矩陣與度矩陣的逆陣相乘，旨在實現(xiàn)對無回路矩陣的每個元素進行度歸一化處理。但是由于度矩陣的逆陣和無回路矩陣的維數(shù)不同，使得它們不滿足兩個矩陣相乘的條件，所以并不能直接對這兩種矩陣進行相乘操作。為了解決這一困難，本文用度矩陣的逆陣構(gòu)造了一個2n維的分塊矩陣。正則無回路矩陣的具體定義為：

(2)

其中，0n為n維全零矩陣，D-1為n維度矩陣D的逆陣，而B′為2m維無回路矩陣的簡化形式。

(3)

其中，In為n維單位矩陣，D=diag(di)為一個n維對角矩陣，對角元素為相應(yīng)節(jié)點的度，A為n維鄰接矩陣。該簡化操作使得矩陣由m維降至n維，在保證主要性質(zhì)不變的前提下，顯著地降低了算法的計算復(fù)雜度。正則無回路矩陣本質(zhì)上就是對無回路矩陣的每一個元素都進行了度歸一化處理，下文的實驗結(jié)果將會表明這種歸一化操作能很好地消除節(jié)點度異質(zhì)對結(jié)果準(zhǔn)確性的影響。

3 利用正則無回路矩陣估計社團數(shù)目

與無回路矩陣的特征譜相比，正則無回路矩陣的特征值范圍變?yōu)閇0,1]，即特征譜整體縮小。本文通過多次實驗發(fā)現(xiàn)，正則無回路矩陣的特征值分布具有一定的規(guī)律性，即當(dāng)一個網(wǎng)絡(luò)包含K個社團時，那么正則無回路矩陣的所有特征值中必然會有前K個數(shù)量級較大的特征值是實數(shù)，而且明顯分布在以某個值為半徑的圓盤之外。如圖1所示是將海豚網(wǎng)絡(luò)(Dolphins Network)用正則無回路矩陣表示后所得到的特征值分布圖，圖中將該矩陣的復(fù)數(shù)特征值用小圓點表示，實數(shù)特征值用大圓點表示。

圖1 Dolphins網(wǎng)絡(luò)的特征值分布圖

Dophins網(wǎng)絡(luò)實際包含兩個社團，相應(yīng)地，從圖中可以看到橫軸上有兩個大圓點明顯遠離大多數(shù)圓點，這與本文發(fā)現(xiàn)的正則無回路矩陣特征譜規(guī)律相吻合。基于這一規(guī)律，發(fā)現(xiàn)大于某個圓盤半徑的實特征值數(shù)目對待觀察網(wǎng)絡(luò)的社團數(shù)目估計有至關(guān)重要的指引作用。因此，本文的首要任務(wù)就是如何去確定這樣一個圓盤半徑。

通過多次實驗發(fā)現(xiàn)，利用本征間隙的最大位置來確定正則無回路矩陣特征譜的圓盤半徑是比較合理的。根據(jù)矩陣擾動理論，相鄰的兩個連續(xù)特征值之間的差值稱為本征間隙。由本征間隙決定的穩(wěn)定特征向量能夠確定社團結(jié)構(gòu)，而且本征間隙本身還能反映潛在社團數(shù)目的信息。基于此，首先將實軸上的特征值降序排列，依次計算相鄰兩個實特征值的本征間隙；然后找到本征間隙的最大位置得到圓盤半徑，最后統(tǒng)計大于此半徑的實特征值數(shù)目。本文中，將本征間隙序列中出現(xiàn)第一個極大值的后一個特征值的下標(biāo)定義為本征間隙的最大位置，定義公式為：

r=argmax(λr-1-λr),λr∈R

(4)

式中λr是第r個特征值。本征間隙最大位置處的特征值即為圓盤半徑R，公式定義為：

R=λr

(5)

那么網(wǎng)絡(luò)社團數(shù)目就是大于此半徑的實特征值的數(shù)目，具體公式定義為：

K=num{λiλi>R}

(6)

這種方法只需要計算網(wǎng)絡(luò)中少數(shù)的實特征值，并不需要計算所有特征值。因此，本文方法保持了基于無回路矩陣估計方法高計算效率的優(yōu)勢。基于正則無回路矩陣的網(wǎng)絡(luò)社團數(shù)目估計方法的具體實現(xiàn)步驟如下：

輸入：網(wǎng)絡(luò)的邊列表Edge_list。

輸出：社團數(shù)目K和正則無回路矩陣譜分布圖。

(1)由實驗網(wǎng)絡(luò)的邊列表Edge_list轉(zhuǎn)換成鄰接矩陣和度矩陣；

(2)根據(jù)式(2)構(gòu)造正則無回路矩陣；

(3)通過eig或eigs函數(shù)求出實軸上的特征值并對其降序排列；

(4)計算本征間隙序列，根據(jù)式(4)得到第一個極大值對應(yīng)的驟變點；

(5)根據(jù)式(5)確定圓盤半徑；

(6)根據(jù)式(6)估計網(wǎng)絡(luò)社團數(shù)目；

(7)結(jié)果可視化，即畫出具有社團結(jié)構(gòu)網(wǎng)絡(luò)的正則無回路矩陣特征值分布圖。

4 實驗驗證

本文利用人工網(wǎng)絡(luò)驗證所提算法的準(zhǔn)確性。隨機塊模型[11](Stochastic Block Model, SBM)是比較經(jīng)典的網(wǎng)絡(luò)生成模型之一，用于生成大規(guī)模網(wǎng)絡(luò)中的塊、組或社團。該模型對同一社團內(nèi)的所有節(jié)點都設(shè)置了相同的節(jié)點度，但是許多現(xiàn)實網(wǎng)絡(luò)存在小部分度相對較高的節(jié)點[12]，故該模型不能很好地擬合現(xiàn)實網(wǎng)絡(luò)。度糾正隨機塊模型[13](Degree-Corrected Stochastic Block Model, DCSBM)是在簡單隨機塊模型的基礎(chǔ)上融合了節(jié)點度對生成網(wǎng)絡(luò)的影響，對每個節(jié)點設(shè)置了一個度參數(shù)，進而生成度異質(zhì)分布的網(wǎng)絡(luò)。

本文生成兩類含有120個節(jié)點的人工網(wǎng)絡(luò)，一類由SBM模型生成網(wǎng)絡(luò)，另一類由DCSBM模型生成度異質(zhì)分布的網(wǎng)絡(luò)，每類網(wǎng)絡(luò)由塊數(shù)分別為2和4的兩組網(wǎng)絡(luò)組成。與塊數(shù)相對應(yīng)，分別設(shè)置塊內(nèi)連接概率為0.99和0.77，塊間連接概率均為0.01。以下sbm和dcsbm分別代表方法在SBM或DCSBM人工網(wǎng)絡(luò)測試，k代表實驗社團數(shù)目，k_truth代表實際社團數(shù)目，sizeGap代表兩個相鄰社團內(nèi)節(jié)點數(shù)目之間的差值。

圖2中NB是基于無回路矩陣的社團數(shù)目估計，RNB是基于正則無回路矩陣的社團數(shù)目估計。從圖中可以看出，基于無回路矩陣的方法測試8次的估計結(jié)果中只有兩次的估計結(jié)果是正確的，而本文方法每次所得結(jié)果均與實際結(jié)果相符合。基于無回路矩陣方法的準(zhǔn)確率只有25%，也就是說，基于無回路矩陣的方法在DCSBM網(wǎng)絡(luò)中的測試結(jié)果存在誤差。這說明節(jié)點度異質(zhì)分布嚴(yán)重影響了該方法的準(zhǔn)確性，而本文方法很好地克服了這種影響，多次實驗均能得出正確的估計結(jié)果。

圖2 DCSBM人工網(wǎng)絡(luò)中兩種方法的準(zhǔn)確率對比

本文方法充分考慮了節(jié)點度異質(zhì)這一影響因素，然后通過正則無回路矩陣的本征間隙最大位置對社團數(shù)目進行估計。從圖3可以看出，無論在SBM或DCSBM網(wǎng)絡(luò)中，實驗的社團數(shù)目均與實際的社團數(shù)目相符合。這表明在節(jié)點度分布不均衡的網(wǎng)絡(luò)中，新的社團數(shù)目估計方法的估計結(jié)果更可靠。

圖3 本文方法在兩類人造網(wǎng)絡(luò)中的測試

在保持節(jié)點度異質(zhì)的情況下，通過改變社團大小對結(jié)果準(zhǔn)確性進行測試，結(jié)果如圖4所示。圖4(a)對兩個社團大小分別設(shè)置為30和90；(b)對四個社團大小分別設(shè)置為15、25、35和45。由(a)和(b)兩個子圖可以觀察出估計的社團數(shù)目與實際的社團數(shù)目相符合。實驗結(jié)果表明在社團大小和邊密度都不均衡時，本文社團數(shù)目估計方法同樣適用。

圖4 社團大小和節(jié)點度異質(zhì)分布對本文方法的影響

5 結(jié)論

估計網(wǎng)絡(luò)中的社團數(shù)目對一些要求社團數(shù)目作為輸入的社團檢測算法是至關(guān)重要的。本文提出一種基于正則無回路矩陣的網(wǎng)絡(luò)社團數(shù)目估計方法，該方法首先對無回路矩陣進行歸一化處理得到正則無回路矩陣，然后根據(jù)正則無回路矩陣的本征間隙最大位置來確定網(wǎng)絡(luò)社團數(shù)目。實驗結(jié)果表明，本文提出的基于正則無回路矩陣的社團數(shù)目估計方法的準(zhǔn)確率更高。此外，該方法計算復(fù)雜度低且適用范圍不受限。

當(dāng)前本文提出的社團數(shù)目估計方法只關(guān)注于由SBM和DCSBM模型生成的社團結(jié)構(gòu)顯著的人工網(wǎng)絡(luò)，在未來工作中還可以將本文方法應(yīng)用到存在弱小社團的實際網(wǎng)絡(luò)中。

[1] 汪小帆,汪秉宏,曹進德,等. 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)功能性質(zhì)及其應(yīng)用[J]. 系統(tǒng)工程理論與實踐, 2008, 28(S1): 45-48.

[2] 鄭浩原, 黃戰(zhàn). 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——改進的層次聚類算法[J]. 微型機與應(yīng)用, 2011, 30(16): 85-88.

[4] 王林, 戴冠中. 復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)——理論與應(yīng)用[J]. 科技導(dǎo)報, 2005, 23(8): 62-66.

[5] SALDANA D F, YU Y, FENG Y. How many communities are there?[J]. Journal of Computational & Graphical Statistics, 2015,26(1): 171-181.

[6] CHAUHAN S, GIRVAN M, OTT E. Spectral properties of networks with community structure[J]. Physical Review E, 2009, 80(80): 394-400.

[7] SHEN H W, CHENG X Q. Spectral methods for the detection of network community structure: a comparative analysis[J]. Computer Science, 2010, 10(10): 10020.

[8] CHEN K, LEI J. Network cross-validation for determining the number of communities in network data[J]. Eprint Arxiv, 2014, 178(5): 410.

[9] LE C M, LEVINA E. Estimating the number of communities in networks by spectral methods[J]. Computer Science, 2015: 769-774.

[10] BORDENAVE C, LELARGE M, MASSOULIE L. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs[J]. Eprint Arxiv, 2015, 4(2): 1347-1357.

[11] HOLLAND P W, LASKEY K B, LEINHARDT S. Stochastic blockmodels: first steps[J]. Social Networks, 1983, 5(2): 109-137.

[12] 王林, 戴冠中. 復(fù)雜網(wǎng)絡(luò)的度分布研究[J]. 西北工業(yè)大學(xué)學(xué)報, 2006, 24(4): 405-409.

[13] KARRER B, NEWMAN M E J. Stochastic blockmodels and community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 83(2): 211-222.

Estimation of the number of communities in networks based on regular non-backtracking matrix

Wang Lin, Zhao Yuee

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

Aiming at the issue that the number of communities is unknown in the community detection, a community number estimation method based on regular non-backtracking matrix was proposed in this paper. The method can be used to estimate the number of communities by defining a regular non-backtracking matrix and using its spectral properties. This method is efficient computationally, and suitable for stochastic blockmodel and degree-corrected stochastic blockmodel. The method was verified by two kinds of artificial networks, the experimental results show that the proposed method is superior to the method based on the non-backtracking matrix, which mainly eliminates the effect of degree heterogeneity distribution on the community number estimation, and improves the accuracy of the estimation results.

stochastic blockmodel; degree-corrected stochastic blockmodel; regular non-backtracking matrix; number of communities

TP393

：A

10.19358/j.issn.1674- 7720.2017.17.024

王林，趙月娥.基于正則無回路矩陣的網(wǎng)絡(luò)社團數(shù)目估計[J].微型機與應(yīng)用，2017,36(17)：82-85.

2017-04-06)

王林(1963-)，男，教授，主要研究方向：復(fù)雜網(wǎng)絡(luò)、大數(shù)據(jù)理論與應(yīng)用、無線傳感器及計算機應(yīng)用。趙月娥(1990-)，女，碩士研究生，主要研究方向：復(fù)雜網(wǎng)絡(luò)。