趙雨露 張曦煌

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇 無錫 214122)

一種結(jié)合小世界模型改良的NMF社區(qū)發(fā)現(xiàn)算法

趙雨露 張曦煌

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 江蘇 無錫 214122)

社區(qū)發(fā)現(xiàn)是當(dāng)前復(fù)雜網(wǎng)絡(luò)與數(shù)據(jù)挖掘的熱點(diǎn)，非負(fù)矩陣分解是社區(qū)發(fā)現(xiàn)的常用手段。針對(duì)當(dāng)前非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法，為提高算法的準(zhǔn)確率與可解釋性，提出多階鄰居節(jié)點(diǎn)的概念，在小世界模型的基礎(chǔ)上構(gòu)建了規(guī)?？煽氐亩嚯A復(fù)合信息矩陣，用后處理的方法減少了算法中隨機(jī)因素帶來的不穩(wěn)定性。對(duì)于真實(shí)網(wǎng)絡(luò)與人工網(wǎng)絡(luò)的實(shí)驗(yàn)證明，新背景下的算法較原算法在性能上有一定的提升。

社區(qū)發(fā)現(xiàn) 非負(fù)矩陣分解 小世界模型 復(fù)雜網(wǎng)絡(luò)

0 引 言

現(xiàn)實(shí)世界中存在大量可以抽象為復(fù)雜網(wǎng)絡(luò)的關(guān)系形式，例如人際網(wǎng)絡(luò)、通信網(wǎng)絡(luò)和軟件中API的調(diào)用等。這些網(wǎng)絡(luò)中包含著大量潛藏的信息，從簡(jiǎn)單的網(wǎng)絡(luò)中挖掘和總結(jié)出有價(jià)值的信息成為既有困難又有意義的工作。

在復(fù)雜網(wǎng)絡(luò)的無標(biāo)度、高聚集系數(shù)和節(jié)點(diǎn)中心性等基本特征中，社區(qū)結(jié)構(gòu)是一種重要的基本特性。在社區(qū)發(fā)現(xiàn)的早期研究中，傳統(tǒng)的圖論與社會(huì)學(xué)中的層次聚類是主要的研究手段，自2002年NewMan[1]于PNAS上對(duì)社區(qū)的基本結(jié)構(gòu)提出了更清晰的闡釋后，社區(qū)結(jié)構(gòu)研究進(jìn)入全新的層次。針對(duì)社團(tuán)發(fā)現(xiàn)的研究大量涌現(xiàn)，研究視角和研究方法也獲得了極大豐富，包括滲流、邊分割等一系列新視角與新方法。

目前，社區(qū)發(fā)現(xiàn)的主要手段有圖的劃分算法、邊聚類算法、隨機(jī)游走、模塊度以及層次聚類等。本質(zhì)上社區(qū)發(fā)現(xiàn)問題應(yīng)歸納于無監(jiān)督學(xué)習(xí)范疇，非負(fù)矩陣分解NMF(nonnegative matrix factorization) 模型作為一種有效的無監(jiān)督學(xué)習(xí)手段，也受到了極大關(guān)注。研究發(fā)現(xiàn)，NMF與K-means和PLSI(probabilistic latent semantic indexing)等無監(jiān)督學(xué)習(xí)方法關(guān)系密切且具有更好的解釋性。將非負(fù)矩陣分解應(yīng)用于對(duì)復(fù)雜網(wǎng)絡(luò)中社區(qū)的挖掘，具有物理含義明確、計(jì)算簡(jiǎn)單和準(zhǔn)確度較高等優(yōu)點(diǎn)。

NMF是一種有Paatero等[2]提出的矩陣分解思想，直到1999年Lee等[3]將純數(shù)學(xué)思想的NMF應(yīng)用于圖像處理并取得良好的成果后，NMF在提取隱含結(jié)構(gòu)與模式時(shí)所具有的良好能力才得到重視，之后NMF被廣泛應(yīng)用于諸多領(lǐng)域。其中Wang等[4]提出采用NMF方法對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行了社區(qū)劃分，之后基于非負(fù)矩陣的社區(qū)發(fā)現(xiàn)算法得到了快速發(fā)展。眾多該領(lǐng)域的學(xué)者對(duì)其進(jìn)行了不同程度不同角度的改進(jìn)。

當(dāng)前對(duì)于基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法的主要改良方式主要有替換目標(biāo)矩陣，例如基于物理過程或以共有鄰居結(jié)點(diǎn)為依據(jù)構(gòu)造信息矩陣的方法[5-6]、以針對(duì)目標(biāo)矩陣的特殊性進(jìn)行目標(biāo)函數(shù)優(yōu)化的方法[7-8]和將更多的先驗(yàn)信息融入信息矩陣的算法[9]等。他們都將基于NMF的社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)速度或精度等性能進(jìn)行了不同程度的提升。

本文權(quán)衡算法復(fù)雜度提出一種新的信息矩陣，提出一種算法降低NMF帶來的隨機(jī)性，采用真實(shí)數(shù)據(jù)集與人工網(wǎng)絡(luò)數(shù)據(jù)集對(duì)算法進(jìn)行實(shí)驗(yàn)。

1 預(yù)備知識(shí)

定義1對(duì)于節(jié)點(diǎn)v需要最短n條邊可以連接的節(jié)點(diǎn)，稱為節(jié)點(diǎn)v的n階鄰居節(jié)點(diǎn)。

定義2對(duì)于一個(gè)無向、無權(quán)的圖G=(V，E)，V是其所有節(jié)點(diǎn)構(gòu)成的集合，E為其所有連邊構(gòu)成的集合。其鄰接矩陣設(shè)為A，對(duì)于V中的任意節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間若存在連邊則A[i,j]=1，否則A[i,j]=0。

二十世紀(jì)末以來，對(duì)通信、社交與技術(shù)等網(wǎng)絡(luò)的研究表明，大多數(shù)網(wǎng)絡(luò)均具有高度的集群性、不均衡的度分布以及中心節(jié)點(diǎn)結(jié)構(gòu)等特點(diǎn)。Watts等[10]于1998年發(fā)表在nature論文上以數(shù)學(xué)的方式定義了小世界網(wǎng)絡(luò)，其中涉及兩個(gè)重要的衡量網(wǎng)絡(luò)特征特征路徑長(zhǎng)度與聚合系數(shù)。

定義3網(wǎng)絡(luò)中，設(shè)定連接任意兩點(diǎn)所需要的最少邊數(shù)為兩點(diǎn)間的路徑長(zhǎng)度，全部網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的路徑長(zhǎng)度的平均值，定義為網(wǎng)絡(luò)的特征路徑長(zhǎng)度。其網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量與特征路徑長(zhǎng)度的關(guān)系為：

(1)

式中，N為節(jié)點(diǎn)總數(shù)，W為每個(gè)節(jié)點(diǎn)的聯(lián)系寬度，n為特征路徑長(zhǎng)度。

可以看出隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)指數(shù)增長(zhǎng)，平均步長(zhǎng)近似線性增長(zhǎng)。該文指出，社會(huì)關(guān)系中人普遍的聯(lián)系寬度為260，在超過70億節(jié)點(diǎn)的網(wǎng)絡(luò)中從任一節(jié)點(diǎn)聯(lián)系到另一節(jié)點(diǎn)僅需6.5步，即著名的“六度分割理論”。

(2)

式中，w為實(shí)際的邊數(shù)，k為節(jié)點(diǎn)v的連邊個(gè)數(shù)，cc為節(jié)點(diǎn)v的聚合數(shù)。網(wǎng)絡(luò)中所有節(jié)點(diǎn)的聚合數(shù)的平均值為網(wǎng)絡(luò)的聚合數(shù)。網(wǎng)絡(luò)的聚合系數(shù)反映了相鄰兩個(gè)節(jié)點(diǎn)之間的鄰居節(jié)點(diǎn)的重合程度。

2 基于NMF的社區(qū)發(fā)現(xiàn)算法改進(jìn)

2.1 非負(fù)矩陣分解與社區(qū)發(fā)現(xiàn)

minD(X,WHT)s.t.M≥0H≥0

(3)

式中，D(x,y)為x與y差異性的損失函數(shù)，實(shí)際應(yīng)用中D(x,y)可以選用平方誤差函數(shù)或者廣義KL散度函數(shù)。

平方誤差函數(shù)是采用兩個(gè)矩陣差的Frobenius范數(shù)平方表示，即：

(4)

廣義KL散度的定義為：

(5)

然后可以采用多步疊乘、梯度下降或交替最小二乘法等方法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化。

2.2 一種基于小世界模型的復(fù)合多階信息矩陣

目前絕大多數(shù)基于矩陣分解的社區(qū)發(fā)現(xiàn)算法多采用鄰居矩陣作為數(shù)據(jù)矩陣，通過上節(jié)關(guān)于對(duì)此類算法應(yīng)用于社區(qū)發(fā)現(xiàn)的解釋可以發(fā)現(xiàn)數(shù)據(jù)矩陣若包含更多連邊信息則會(huì)更有助于社區(qū)發(fā)現(xiàn)的質(zhì)量，而鄰接矩陣的缺陷在于只能反映某節(jié)點(diǎn)與其一階鄰居節(jié)點(diǎn)的關(guān)系不能直觀地反映與其他更高階的大多數(shù)節(jié)點(diǎn)的關(guān)系。

為此，本文采用一個(gè)三維矩陣M[i][j][l]描述任一節(jié)點(diǎn)與絕大多數(shù)節(jié)點(diǎn)之間形成的關(guān)系。i、j分別對(duì)應(yīng)節(jié)點(diǎn)vi與節(jié)點(diǎn)vj，若兩個(gè)節(jié)點(diǎn)在第l步建立聯(lián)系，則M[i][j][1]=1；否則M[i][j][1]=0?？紤]到矩陣中節(jié)點(diǎn)vi到達(dá)自身無太多實(shí)際意義，所以矩陣M[i][j][1]中的對(duì)角線應(yīng)全為零。

通過小世界模型的特征路徑長(zhǎng)度概念可以發(fā)現(xiàn)，當(dāng)三維矩陣中的l等于特征路徑長(zhǎng)度時(shí)，就可以將節(jié)點(diǎn)i與大多數(shù)的節(jié)點(diǎn)建立聯(lián)系。為充分體現(xiàn)邊的生成概率，通過多重路徑到達(dá)的節(jié)點(diǎn)應(yīng)該得到加權(quán)，即在第l層有t種路徑從節(jié)點(diǎn)i到達(dá)某節(jié)點(diǎn)j，則該節(jié)點(diǎn)對(duì)應(yīng)的M[i][j][1]=t。例如，圖1中的節(jié)點(diǎn)v1到v5對(duì)應(yīng)的M[1][5][2]=2,而v1到v4對(duì)應(yīng)的M[1][2][4]=1。此外，文獻(xiàn)[11]指出聚合系數(shù)對(duì)于社區(qū)結(jié)構(gòu)的重要意義，同一節(jié)點(diǎn)可以被不同的步長(zhǎng)多次訪問，則每一次訪問都應(yīng)該被記錄以加權(quán)體現(xiàn)訪問概率，圖1中的v1與v2對(duì)應(yīng)的M[1][2][1]=1且M[1][2][2]=1。

圖1 五個(gè)節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)圖

(6)

2.3 目標(biāo)函數(shù)的求解與算法優(yōu)化

實(shí)際應(yīng)用中，復(fù)雜網(wǎng)絡(luò)的信息矩陣有著一定的特殊性，例如對(duì)于共有n個(gè)節(jié)點(diǎn)的無向復(fù)雜網(wǎng)絡(luò)信息矩陣一般為大小是n×n的對(duì)稱矩陣，且主對(duì)角線全為零?；诖?，大量的改良后的非負(fù)矩陣分解算法被提出，一種常應(yīng)用于社區(qū)發(fā)現(xiàn)的改進(jìn)非負(fù)矩陣分解的方法為文獻(xiàn)[12]提出的SNMF算法。被分解后的兩個(gè)矩陣為對(duì)稱的大小為n×c的U與UT,SNMF的算法公式如下：

(7)

式中，n為節(jié)點(diǎn)的數(shù)量，c為社區(qū)的數(shù)量，Uij表示節(jié)點(diǎn)i隸屬于社區(qū)j的概率。

為了得到矩陣U,可以采用歐氏距離衡量X與UUT的相似度，利用式(8)目標(biāo)函數(shù)進(jìn)行限定次數(shù)的迭代得到結(jié)果：

(8)

采用文本中的數(shù)據(jù)矩陣進(jìn)行基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)進(jìn)行多次實(shí)驗(yàn)，證明處于兩個(gè)社區(qū)邊界的節(jié)點(diǎn)會(huì)被隨機(jī)的劃分的兩個(gè)社區(qū)中的任一一個(gè)，在數(shù)據(jù)上即表現(xiàn)為分解后的U中前幾列差值較小的行數(shù)，由此帶來了算法的不穩(wěn)定性。為了提高穩(wěn)定性，需要對(duì)輸出的結(jié)果進(jìn)行后處理。本文將利用信息矩陣對(duì)邊界節(jié)點(diǎn)最終劃歸的社區(qū)進(jìn)行判定?；舅悸窞椋眯畔⒕仃嚱y(tǒng)計(jì)已經(jīng)確定的社區(qū)中所有節(jié)點(diǎn)對(duì)于該邊界節(jié)點(diǎn)的影響力之和，再取平均值，最后將節(jié)點(diǎn)劃歸平均值較大的社區(qū)內(nèi)，其可表達(dá)為：

(9)

2.4 改進(jìn)后的SNMF-sl算法描述

綜上可以得到新的基于矩陣分解的社區(qū)發(fā)現(xiàn)算法，其步驟如下：

輸入：鄰接矩陣A，迭代次數(shù)T，劃分成c個(gè)社區(qū)

輸出：節(jié)點(diǎn)社區(qū)劃分矩陣E

步驟1對(duì)鄰接矩陣A進(jìn)行處理，統(tǒng)計(jì)并計(jì)算出節(jié)點(diǎn)總數(shù)N，節(jié)點(diǎn)平均聯(lián)系寬度W，特征路徑長(zhǎng)度1。

步驟2構(gòu)造l階的三維矩陣M。

步驟3通過式(6)進(jìn)行處理后得到二維數(shù)據(jù)矩陣Γ。

步驟4按照式(8)迭代計(jì)算U矩陣(共迭代T次)，并對(duì)W進(jìn)行歸一化操作，使得W矩陣每一行元素之和為1。

步驟5篩選出U中隸屬度差值較小的節(jié)點(diǎn)，并利用式(9)對(duì)最后結(jié)果進(jìn)行后處理。

步驟6輸出結(jié)果U。

2.5 算法復(fù)雜度分析

步驟1需要時(shí)間復(fù)雜度O(n)，步驟2需要時(shí)間復(fù)雜度O(nl)，步驟3的復(fù)雜度為O(n)，步驟4需要復(fù)雜度O(Tn2c)，若邊界上未確定的節(jié)點(diǎn)總數(shù)為s平均帶分入的社區(qū)數(shù)量為q社區(qū)平均節(jié)點(diǎn)數(shù)量為p則步驟4復(fù)雜度為O(sqp)。綜上算法所需要的總復(fù)雜度為O(nl+Tn2c)。

3 基于非負(fù)矩陣分解的社區(qū)發(fā)現(xiàn)算法改進(jìn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)估方法

為了有效地測(cè)試對(duì)比改進(jìn)后的算法與原算法，我們將分別采用真實(shí)數(shù)據(jù)集與人工網(wǎng)絡(luò)數(shù)據(jù)集對(duì)算法分別進(jìn)行測(cè)試，并采用相關(guān)指標(biāo)量化兩種算法的劃分性能。所有實(shí)驗(yàn)均采用MATLAB實(shí)現(xiàn)，為了保證公平性，所有的數(shù)據(jù)矩陣都將使用同樣的軟件與硬件環(huán)境，目標(biāo)函數(shù)變化小于e-10為終止條件，運(yùn)行20次取平均值。

數(shù)據(jù)集Zachary Karate Club[13]是一個(gè)著名的復(fù)雜網(wǎng)絡(luò)小型數(shù)據(jù)集，其包含34個(gè)節(jié)點(diǎn)，78條邊。后來該俱樂部由于管理問題，該網(wǎng)絡(luò)被分為兩個(gè)大小相當(dāng)?shù)淖由鐓^(qū)。

Dolphin Social Network是由Lesseau等[14]用近七年時(shí)間對(duì)新西蘭一海灣的寬吻海豚進(jìn)行觀察實(shí)驗(yàn)收集后得到的關(guān)系網(wǎng)絡(luò)，其包含62個(gè)節(jié)點(diǎn)共有159條邊，大致分為兩個(gè)社區(qū)，亦是常用于社區(qū)發(fā)現(xiàn)的數(shù)據(jù)集之一。

American College football Network由美國(guó)2000年橄欖球賽季的高校代表隊(duì)組成，網(wǎng)絡(luò)中的連邊表示橄欖球隊(duì)之間進(jìn)行過比賽。其一共包含115個(gè)節(jié)點(diǎn)，613條邊構(gòu)成，115個(gè)代表隊(duì)來自12個(gè)聯(lián)盟。

Books about US politics網(wǎng)絡(luò)中，節(jié)點(diǎn)表示美國(guó)亞馬遜在線售賣的書籍，若兩本書被同一個(gè)顧客購(gòu)買則兩個(gè)節(jié)點(diǎn)之間建立起連邊。一共包含105個(gè)節(jié)點(diǎn)，441條連邊，可以大致分為三個(gè)不同的類型即三個(gè)社區(qū)。人工網(wǎng)絡(luò)數(shù)據(jù)集采用Lancichinetti等[15]人提出的LFR benchmark，其可以生成指定規(guī)模不同需求的網(wǎng)絡(luò)數(shù)據(jù)集，生成網(wǎng)絡(luò)輸入數(shù)據(jù)中一個(gè)重要的參數(shù)為混合參數(shù)mu。mu表示節(jié)點(diǎn)與社區(qū)外部節(jié)點(diǎn)鏈接的概率，mu值越大生成數(shù)據(jù)的社區(qū)之間的邊界越模糊，mu值越小生成社區(qū)之間的邊界越清晰。

為了方便比較幾個(gè)算法的性能，本文采用標(biāo)準(zhǔn)互信息與準(zhǔn)確率作為量化的評(píng)價(jià)方法。

(1) 精準(zhǔn)率(ACC)

給定節(jié)點(diǎn)vi，lpi為該節(jié)點(diǎn)被社區(qū)劃分的結(jié)果，lti為其實(shí)際所在的社區(qū)編號(hào)。精準(zhǔn)率的實(shí)際意義為所有被劃分節(jié)點(diǎn)中占正確節(jié)點(diǎn)的總數(shù)，根據(jù)文獻(xiàn)[16]精準(zhǔn)度的數(shù)學(xué)定義如下：

(10)

式中，對(duì)于函數(shù)δ(x,y)，當(dāng)x=y時(shí)，函數(shù)值為1否則為0。pmap(lpi)為映射函數(shù)用以調(diào)取節(jié)點(diǎn)vi對(duì)應(yīng)的社區(qū)編號(hào)。N為節(jié)點(diǎn)總數(shù)。ACC值的取值在0到1之間，越大說明社區(qū)劃分的準(zhǔn)確率越高，反之則準(zhǔn)確率越低。

(2) 標(biāo)準(zhǔn)互信息(NMI)

標(biāo)準(zhǔn)互信息是一種由Lancichinetti等[17]提出的一種公認(rèn)較為可靠的評(píng)估標(biāo)準(zhǔn)。其可以量化算法生成的結(jié)果與標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)的相似程度，以方便進(jìn)行評(píng)價(jià)比較。數(shù)學(xué)定義如下：

(11)

式中，N為含混矩陣，Nij代表i、j兩個(gè)社區(qū)中共有的節(jié)點(diǎn)個(gè)數(shù)，而Ni、Nj分別表示N中對(duì)應(yīng)的第i、j行的和。通過式(11)可知，NMI的取值范圍處于0到1之間。NMI越小說明與標(biāo)準(zhǔn)網(wǎng)絡(luò)區(qū)別越大，NMI越大說明與標(biāo)準(zhǔn)網(wǎng)絡(luò)越相似。

3.2 實(shí)驗(yàn)與結(jié)果分析

為了比較文中提及的數(shù)據(jù)矩陣與后處理改進(jìn)對(duì)社區(qū)劃分結(jié)果的影響。將要以SNMF為基本方法分別以鄰接矩陣A，基于物理過程的熱量擴(kuò)散得到的方法(heat)[5]，基于最共鄰節(jié)點(diǎn)數(shù)量為依據(jù)的jaccard相似度方法[18]方法與本文提及的小世界模型下的多階復(fù)合矩陣(sl)為信息矩陣進(jìn)行非負(fù)矩陣分解。選用文中提及的四個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)并不一定完全符合完美的社區(qū)結(jié)構(gòu)模型，故對(duì)真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)使用精準(zhǔn)率作為評(píng)價(jià)指標(biāo)。

表1的實(shí)驗(yàn)結(jié)果中，較鄰接矩陣而言，各類新矩陣在基于NMF的社區(qū)劃分中取得了更好的實(shí)驗(yàn)結(jié)果，說明矩陣中更為豐富的信息有利于提升社區(qū)劃分的精度，而本文提出的新矩陣sl方法從基于NMF社區(qū)發(fā)現(xiàn)的物理解釋出發(fā)構(gòu)造，劃分結(jié)果較其他算法更優(yōu)。

表1 采取不同數(shù)據(jù)矩陣的準(zhǔn)確率比較

為了考察后處理對(duì)于社區(qū)劃分結(jié)果穩(wěn)定性的影響，本文采用人工網(wǎng)絡(luò)LFR。其中LFR的數(shù)據(jù)設(shè)置如表2所示，這里，mu取值范圍是0.35到0.8，每次遞增0.05生成10個(gè)邊界清晰程度不同的LFR-4000網(wǎng)絡(luò)。

表2 LFR-4000人工網(wǎng)絡(luò)參數(shù)設(shè)置

圖2中記錄的是在LFR-4000人工網(wǎng)絡(luò)下，各種不同情況下NMI值的變化。

圖2 不同實(shí)驗(yàn)條件下LFP-4000網(wǎng)絡(luò)上NMI值比較

圖中折線SNMF-1為采用SNMF算法隨機(jī)的一次劃分的NMI值結(jié)果，SNMF-1A為采用后處理后的SNMF算法開始隨機(jī)的一次劃分的NMI值結(jié)果，SNMF為運(yùn)行算法20次的平均結(jié)果，SNMF-sl為采用了sl信息矩陣與后處理后運(yùn)行20次的平均結(jié)果。

從以上的實(shí)驗(yàn)結(jié)果來看，sl方法得到的信息矩陣較其他類型的矩陣體現(xiàn)了更多的有用信息，令算法的精準(zhǔn)率獲得了提高。而新的后處理手段，尤其在社區(qū)邊界不清晰的情況下使算法的結(jié)果趨于穩(wěn)定，并且使得算法獲得了更好的社區(qū)劃分結(jié)果。值得注意的是，在人工網(wǎng)絡(luò)的實(shí)驗(yàn)中當(dāng)社區(qū)邊界清晰時(shí)，改良后的算法與先前的算法并沒有多少性能上的差異，但是當(dāng)邊界逐漸模糊發(fā)現(xiàn)社區(qū)難度變大時(shí)，改良后的算法優(yōu)勢(shì)更為明顯，具有更好的適應(yīng)性。

4 結(jié) 語

本文的實(shí)驗(yàn)結(jié)果表明，在矩陣分解的社區(qū)發(fā)現(xiàn)算法中，通過采用本文的信息矩陣與后處理方法，可以提高劃分結(jié)果的精準(zhǔn)性，同時(shí)提高算法結(jié)果的穩(wěn)定性，可以有效降低運(yùn)算次數(shù)。雖然通過小世界模型，控制了生成新信息矩陣的復(fù)雜度，但生成的矩陣不再是鄰接矩陣，并且生成矩陣的復(fù)雜度依然很高。所以在以后的工作中，需要通過并行計(jì)算的實(shí)現(xiàn)方法提高算法的效率，使得本文算法更有利于應(yīng)用。

[1] Newman M E J.The Structure and Function of Complex Networks[C]//SIAM Rev,2006:167-256.

[2] Paatero P,Tapper U.Positive matrix factorization:A non-negative factor model with optimal utilization of error estimates of data values[J].Environmetrics,1994,5(2):111-126.

[3] Lee D D,Seung H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

[4] Wang F,Li T,Wang X,et al.Community discovery using nonnegative matrix factorization[J].Data Mining and Knowledge Discovery,2011,22(3):493-521.

[5] Mahajan S,Pande A,Pande S,et al.Mining Web Graphs for Recommendations[J].International Journal of Electronics Communication and Computer Engineering,2014,5(2):351-353.

[6] Jiao J,Hu D,Zhang Z Y.A Novel Similarity Measurement for Community Structure Detection[C]//International Conference on Intelligent Human-Machine Systems and Cybernetics,2012:301-306.

[7] Staff P O.Correction: uncovering community structures with initialized bayesian nonnegative matrix factorization[J].Plos One,2014,9(9):e107884-e107884.

[8] Cao X,Wang X,Jin D,et al.ERRATUM:Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J].Scientific Reports,2014,3(10):2993-2993.

[9] Zhang Z Y,Sun K D,Wang S Q.Enhanced Community Structure Detection in Complex Networks with Partial Background Information[J].Scientific Reports,2013,3(11):48005.

[10] Watts D J,Strogatz S H.Collective dynamics of ’small-world’ networks[C]//Nature,1998:440-442.

[11] Cui Y,Wang X,Li J.Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient[J].Physica A Statistical Mechanics & Its Applications,2014,405(405):85-91.

[12] Xu J,Xiang L,Wang G,et al.Sparse Non-negative Matrix Factorization (SNMF) based color unmixing for breast histopathological image analysis[J].Computerized Medical Imaging & Graphics the Official Journal of the Computerized Medical Imaging Society,2015,46 Pt 1:20-29.

[13] Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(6):066133.

[14] Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.

[15] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(4 Pt 2):561-570.

[16] Li Y,Jia C,Yu J.A parameter-free community detection method based on centrality and dispersion of nodes in complex networks[J].Physica A Statistical Mechanics & Its Applications,2015,438:321-334.

[17] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.

[18] Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33(4):473.

ACOMMUNITYDETECTIONALGORITHMBASEDONSMALLWORLDMODELANDNMF

Zhao Yulu Zhang Xihuang

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)

Community detection is the hotspot of current complex networks and data mining, whose common means is non-negative matrix factorization. To improve the accuracy and interpretability of community detection algorithm, we propose the concept of first-order neighbors. On the basis of the small-world model, this paper constructed a controllable scale multi-stage compound information matrix. Treatment reduced the algorithm after using random factors of instability. Regarding experimental proof of the real network and artificial networks, new algorithms increase in performance compared to the original algorithm.

Community detection Non-negative matrix factorization Small-world model Complex network

TP301.6

A

10.3969/j.issn.1000-386x.2017.10.048

2016-11-27。江蘇省產(chǎn)學(xué)研合作項(xiàng)目(BY2015019-30)。趙雨露，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。張曦煌，教授。