王 林，趙月娥

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

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

王 林，趙月娥

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

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

隨機(jī)塊模型；度糾正隨機(jī)塊模型；正則無(wú)回路矩陣；社團(tuán)數(shù)目

0 引言

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

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

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

1 無(wú)回路矩陣

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

(1)

2 正則無(wú)回路矩陣

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

(2)

其中，0n為n維全零矩陣，D-1為n維度矩陣D的逆陣，而B(niǎo)′為2m維無(wú)回路矩陣的簡(jiǎn)化形式。

(3)

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

3 利用正則無(wú)回路矩陣估計(jì)社團(tuán)數(shù)目

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

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

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

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

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

(4)

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

R=λr

(5)

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

K=num{λiλi>R}

(6)

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

[4] 王林, 戴冠中. 復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)——理論與應(yīng)用[J]. 科技導(dǎo)報(bà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é)報(bào), 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ú)回路矩陣的網(wǎng)絡(luò)社團(tuán)數(shù)目估計(jì)[J].微型機(jī)與應(yīng)用，2017,36(17)：82-85.

2017-04-06)

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