丁彩英，李澤鵬，劉松華，3

(1.太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600；2.蘭州大學(xué) 信息科學(xué)與工程學(xué)院，蘭州 730000； 3.北京大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100871)

現(xiàn)實(shí)生活中眾多復(fù)雜系統(tǒng)都能用網(wǎng)絡(luò)進(jìn)行建模，如社交網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)、生物網(wǎng)絡(luò)等。而隨著在線網(wǎng)絡(luò)信息量激增，獲取的各種屬性等數(shù)據(jù)越來(lái)越多。如何理解這些網(wǎng)絡(luò)的內(nèi)在機(jī)制，并有效利用這些數(shù)據(jù)成為當(dāng)前社區(qū)檢測(cè)領(lǐng)域的重要研究熱點(diǎn)。

檢測(cè)社區(qū)允許我們發(fā)現(xiàn)與對(duì)象相關(guān)的功能，研究模塊之間的關(guān)聯(lián)，推斷丟失的屬性值，預(yù)測(cè)沒(méi)有觀察到的連接等。傳統(tǒng)的社區(qū)檢測(cè)中，所謂的社區(qū)一般是保證組內(nèi)的邊的連接密度高于組間[1]。如在線社交網(wǎng)絡(luò)中，社區(qū)對(duì)應(yīng)一組朋友，他們就讀于相同的學(xué)?；蛘邅?lái)自相同的縣市。蛋白質(zhì)相互作用網(wǎng)絡(luò)中，社區(qū)對(duì)應(yīng)相互作用的蛋白質(zhì)之間的功能模塊。協(xié)作網(wǎng)絡(luò)中，社區(qū)對(duì)應(yīng)學(xué)科分類。

從建模模型角度分析，傳統(tǒng)的社區(qū)檢測(cè)算法可以分為兩類：1) 概率模型，如SBM(stochastic block model)模型[2]、Dirichlet模型[3]等；2) 譜近似模型，如模塊度[4-6]、及其它的譜聚類[7]、矩陣分解類[8-9]等算法。目前，已有社區(qū)檢測(cè)算法已經(jīng)取得了巨大成功，在各行各業(yè)都有具體的應(yīng)用。但由于已有算法大多數(shù)均基于聚類的無(wú)監(jiān)督版本，唯一可利用的信息就是圖結(jié)構(gòu)，通?？紤]圖的鄰接矩陣，無(wú)法有效挖掘潛在的社區(qū)形成和發(fā)展的機(jī)制。因此不可避免會(huì)碰到如下問(wèn)題：1) 噪聲問(wèn)題，如數(shù)據(jù)的獲取方式本身會(huì)帶來(lái)各種干擾信息；2) 不同的檢測(cè)算法產(chǎn)生不同的解，如分別從節(jié)點(diǎn)和邊的角度進(jìn)行檢測(cè)會(huì)產(chǎn)生不同的社區(qū)。

近年來(lái)，隨著網(wǎng)絡(luò)數(shù)據(jù)獲取能力的提升，出現(xiàn)了大量可用數(shù)據(jù)。針對(duì)社區(qū)挖掘面臨兩大挑戰(zhàn)：1) 可用數(shù)據(jù)以指數(shù)級(jí)增長(zhǎng)；2) 數(shù)據(jù)標(biāo)注任務(wù)繁重且昂貴，同時(shí)需要專家參與。因此國(guó)內(nèi)外學(xué)者開(kāi)始以半監(jiān)督學(xué)習(xí)的方式進(jìn)行社區(qū)挖掘，在現(xiàn)實(shí)網(wǎng)絡(luò)中，除了網(wǎng)絡(luò)拓?fù)湫畔⑼猓赡軙?huì)有特定節(jié)點(diǎn)聚類歸屬的信息。主要包括兩類[10]：1) 節(jié)點(diǎn)類別、屬性等信息；2) 成對(duì)約束(必連和必不連)。

從節(jié)點(diǎn)等信息分析，文獻(xiàn)[11]提出了利用部分節(jié)點(diǎn)語(yǔ)義信息進(jìn)行社區(qū)檢測(cè)的方法，該方法可以用于檢驗(yàn)先驗(yàn)知識(shí)對(duì)檢測(cè)閾值[12]的影響程度。文獻(xiàn)[13]提出了基于密度的自適應(yīng)聚類方法，結(jié)合節(jié)點(diǎn)類別控制密度區(qū)域參數(shù)的選取。文獻(xiàn)[14]基于非負(fù)矩陣分解提出了一種結(jié)合節(jié)點(diǎn)重要程度的學(xué)習(xí)方法。文獻(xiàn)[15]結(jié)合離散勢(shì)理論進(jìn)行半監(jiān)督社區(qū)檢測(cè)，但僅限于無(wú)重疊類型，不考慮多條邊，且要求每個(gè)社區(qū)至少有一個(gè)有類別的節(jié)點(diǎn)。文獻(xiàn)[16]提出了將網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)特征結(jié)合的社區(qū)檢測(cè)算法，有別于其它工作，它可以檢測(cè)重疊社區(qū)。但是上述方法沒(méi)有考慮節(jié)點(diǎn)特征的重要性，因此文獻(xiàn)[17]提出了判別節(jié)點(diǎn)特征的重要性并結(jié)合鄰接矩陣進(jìn)行社區(qū)檢測(cè)的方法。

從成對(duì)約束分析，文獻(xiàn)[18]將主動(dòng)學(xué)習(xí)引入社區(qū)檢測(cè)問(wèn)題中，利用主動(dòng)學(xué)習(xí)來(lái)生成必連和必不連約束，然后進(jìn)行半監(jiān)督社區(qū)檢測(cè)。文獻(xiàn)[19]將成對(duì)約束結(jié)合到鄰接矩陣中，并采用NMF(non-negative matrix factorization)、譜聚類、InfoMap等方法，結(jié)合降噪的一致矩陣進(jìn)行半監(jiān)督社區(qū)檢測(cè)。文獻(xiàn)[20]提出了基于對(duì)稱非負(fù)矩陣分解的半監(jiān)督方法，該方法將成對(duì)約束結(jié)合到鄰接矩陣中尋找社區(qū)結(jié)構(gòu)，并證明了模塊密度與對(duì)稱非負(fù)矩陣分解的等價(jià)性。在此基礎(chǔ)上，文獻(xiàn)[21]添加一個(gè)邏輯推斷步驟來(lái)利用必連和必不連約束，最后進(jìn)行半監(jiān)督學(xué)習(xí)。

除了上述工作外，有學(xué)者結(jié)合節(jié)點(diǎn)和邊的內(nèi)容進(jìn)行社區(qū)檢測(cè)，如文獻(xiàn)[22]提出節(jié)點(diǎn)屬性等信息與真實(shí)類別之間的關(guān)聯(lián)，證明了節(jié)點(diǎn)等先驗(yàn)知識(shí)對(duì)社區(qū)檢測(cè)的重要作用。文獻(xiàn)[23]提出了基于連接的主動(dòng)監(jiān)督信息獲取框架，主動(dòng)選擇集線器節(jié)點(diǎn)所連的邊并斷開(kāi)社區(qū)間的邊，最后以文獻(xiàn)[19, 21]提出的半監(jiān)督社區(qū)檢測(cè)方法為基準(zhǔn)進(jìn)行比較。

值得注意的是，上述半監(jiān)督社區(qū)檢測(cè)方法都是將有類別信息的數(shù)據(jù)編碼并將先驗(yàn)信息轉(zhuǎn)化到拓?fù)湫畔⒅?，通過(guò)直接轉(zhuǎn)換和修改鄰接矩陣來(lái)使用先驗(yàn)知識(shí)。但存在一個(gè)主要的缺陷是無(wú)法有效利用必連先驗(yàn)，因此會(huì)存在諸如直接連接的節(jié)點(diǎn)不能保證分配到相同的社區(qū)等問(wèn)題，而且這些方法通過(guò)修改網(wǎng)絡(luò)拓?fù)洌瑢氡O(jiān)督轉(zhuǎn)化為了傳統(tǒng)的無(wú)監(jiān)督學(xué)習(xí)，半監(jiān)督作為社區(qū)檢測(cè)的預(yù)處理，沒(méi)有使用半監(jiān)督的本質(zhì)特性。因此文獻(xiàn)[24]提出了一種統(tǒng)一框架，將NMF和譜聚類統(tǒng)一到一個(gè)框架下進(jìn)行半監(jiān)督學(xué)習(xí)，但是沒(méi)有對(duì)先驗(yàn)知識(shí)的重要性進(jìn)行提取。

為了解決上述問(wèn)題，有效利用現(xiàn)有網(wǎng)絡(luò)內(nèi)的各種信息，基于文獻(xiàn)[10]的自旋玻璃模型(SG,Spin-Glass)和文獻(xiàn)[6]的模塊度優(yōu)化模型，本文提出了新的半監(jiān)督社區(qū)檢測(cè)算法(SSE,Semi-supervised community detection based on global edge function learning)，該模型能夠?qū)⒕W(wǎng)絡(luò)拓?fù)湫畔?、?jié)點(diǎn)屬性、邊屬性等信息或者其它有用的先驗(yàn)知識(shí)結(jié)合到社區(qū)檢測(cè)中，能針對(duì)特定的需求有效引導(dǎo)社區(qū)發(fā)現(xiàn)過(guò)程，最大程度提升半監(jiān)督學(xué)習(xí)的社區(qū)檢測(cè)性能。

1 學(xué)習(xí)全局邊函數(shù)的半監(jiān)督社區(qū)發(fā)現(xiàn)

本節(jié)針對(duì)上述半監(jiān)督學(xué)習(xí)面臨的問(wèn)題，提出從3個(gè)方面結(jié)合屬性等信息完成社區(qū)發(fā)現(xiàn)，首先引入節(jié)點(diǎn)屬性信息和部分類別信息。其次引入必連和必不連成對(duì)約束條件。最后引入網(wǎng)絡(luò)的拓?fù)湫畔?，從三個(gè)層面不斷優(yōu)化。

1.1 問(wèn)題描述

本文的任務(wù)是結(jié)合邊屬性、節(jié)點(diǎn)屬性或者部分已有類別等可利用信息來(lái)預(yù)測(cè)每個(gè)未標(biāo)注節(jié)點(diǎn)u(u∈U)的合理的類別r.

1.2 融合邊函數(shù)的目標(biāo)函數(shù)

模塊度[6]用來(lái)衡量網(wǎng)絡(luò)中一個(gè)劃分的質(zhì)量，是社區(qū)檢測(cè)中普遍采用的方法。該度量從全局視角測(cè)度圖中獲取的社區(qū)結(jié)構(gòu)，其主要思想是假定一個(gè)沒(méi)有社區(qū)結(jié)構(gòu)的空模型，進(jìn)而采取譜分解的方法來(lái)優(yōu)化模塊度函數(shù)。設(shè)Q是一組社區(qū)C的模塊度，則其計(jì)算公式如下：

(1)

式中：Pij表示空模型中節(jié)點(diǎn)vi和vj之間存在一條邊的概率；Ck表示節(jié)點(diǎn)vk所屬的社區(qū)；d(Ci,Cj)是Kronecker delta函數(shù)，如果節(jié)點(diǎn)vi和vj屬于相同社區(qū)，其值為1，否則為0.

NEWMAN et al[6]采用的空模型如下：

(2)

該模型保持總的邊數(shù)和度分布不變，對(duì)給定的圖進(jìn)行重新連接，構(gòu)成了空模型。

然而，隨著屬性網(wǎng)絡(luò)的出現(xiàn)，如何將屬性結(jié)合到社區(qū)發(fā)現(xiàn)過(guò)程中成為了重要的研究方向。YANG et al[24]指出合適的采用各種屬性信息能極大提高社區(qū)發(fā)現(xiàn)的質(zhì)量，并有效提升發(fā)現(xiàn)社區(qū)的可解釋性。因此本文在公式(2)空模型的基礎(chǔ)上，定義新的模型如下：

(3)

一旦公式(3)中所示改進(jìn)空模型確定，則根據(jù)自旋玻璃模型SG[10]，將公式(1)對(duì)應(yīng)的模塊度優(yōu)化問(wèn)題轉(zhuǎn)化為波茨模型的漢密爾頓最小化問(wèn)題：

(4)

其中g(shù)參數(shù)與文獻(xiàn)[10]中計(jì)算相同。

1.3 邊函數(shù)學(xué)習(xí)

采用公式(3)的主要目的在于將現(xiàn)有信息直接結(jié)合到目標(biāo)函數(shù)中，如文獻(xiàn)[18-21]中涉及的必連和必不連信息。本文可以對(duì)邊函數(shù)采用兩種學(xué)習(xí)方法：設(shè)置為核函數(shù)或者用半監(jiān)督聚類學(xué)習(xí)邊函數(shù)。

1.3.1 直接設(shè)置為核函數(shù)

與文獻(xiàn)[25]的邊函數(shù)設(shè)置不同，本文將邊函數(shù)定義為核函數(shù)[26]，形式如下：

kij=w(vi,vj)=〈j(vi),j(vj)〉 .

(5)

由公式(5)即可計(jì)算相應(yīng)的邊函數(shù)，采用上式的原因有兩點(diǎn)：1) 根據(jù)文獻(xiàn)[5]，模塊密度計(jì)算目標(biāo)函數(shù)等價(jià)于核k均值聚類，因此本文可以很方便地推廣到模塊密度；2) 根據(jù)文獻(xiàn)[26]，其中的低秩近似方法在應(yīng)用于大規(guī)模圖時(shí)能有效降低時(shí)空復(fù)雜度，提高算法的推廣性能。

1.3.2 半監(jiān)督聚類邊函數(shù)學(xué)習(xí)

設(shè)圖中每個(gè)節(jié)點(diǎn)vi∈Rd表示一個(gè)d維向量，包含了節(jié)點(diǎn)的各種屬性等信息。M為必連約束集合(vi,vj)∈M表示節(jié)點(diǎn)vi和vj屬于相同社區(qū)；CN為必不連約束集合(vi,vj)∈CN表示節(jié)點(diǎn)vi和vj屬于不同社區(qū)。F∈{0,1}n×n為二值矩陣，表示n個(gè)節(jié)點(diǎn)劃分到最多n個(gè)社區(qū)。對(duì)于所有可能的社區(qū)劃分結(jié)果表示如下：

(6)

其中Fl,*和F*,j表示矩陣第l行的向量和j列的向量。

基于以上背景，公式(3)中的邊函數(shù)可以設(shè)置為F，使得其與學(xué)習(xí)到的K盡可能一致。因此需要測(cè)度兩者之間的偏差，采用如下距離：

(7)

除了滿足公式(7)的條件，還需要測(cè)試F與約束條件的一致性，因此引入兩個(gè)損失函數(shù)，必連約束的損失函數(shù)定義為L(zhǎng)oss-(Fi,*,Fj,*)：

(8)

同理，必不連損失函數(shù)定義為L(zhǎng)oss+(Fi,*,Fj,*)：

(9)

結(jié)合公式(7)和損失函數(shù)，可以將上述半監(jiān)督學(xué)習(xí)轉(zhuǎn)化為如下的優(yōu)化問(wèn)題：

(10)

綜上，采用文獻(xiàn)[27]的方法求解公式(10)，可以獲取到公式(3)所需的邊函數(shù)w=F.

1.4 半監(jiān)督社區(qū)發(fā)現(xiàn)算法

經(jīng)過(guò)半監(jiān)督學(xué)習(xí)框架獲取的目標(biāo)矩陣為P，其對(duì)應(yīng)的元素為Pij。據(jù)此，本文采用矩陣分解的方法對(duì)P求解如下優(yōu)化問(wèn)題并進(jìn)行社區(qū)檢測(cè)。

(11)

其中P為公式(4)優(yōu)化后的目標(biāo)矩陣，U為社區(qū)類別歸屬矩陣，大小為n×r，表示n個(gè)節(jié)點(diǎn)分別屬于r個(gè)社區(qū)，公式(11)的求解采用算法SBMF的思路進(jìn)行。

最后，本文提出的半監(jiān)督學(xué)習(xí)算法整體框架如下。

算法1:學(xué)習(xí)全局邊函數(shù)的半監(jiān)督社區(qū)發(fā)現(xiàn)框架(SSE)輸入:鄰接矩陣A,已知部分類別信息節(jié)點(diǎn)集合L,包含屬性的節(jié)點(diǎn)集合V,成對(duì)約束必連條件M和必不連條件CN,節(jié)點(diǎn)類別數(shù)目r輸出:類別歸屬矩陣U1:引入節(jié)點(diǎn)屬性V和部分類別信息L求解核矩陣,根據(jù)公式(5)結(jié)合文獻(xiàn)[26]的T-SLKMS方法輸出K2:引入成對(duì)約束條件M和CN求解邊函數(shù)F,根據(jù)公式(7-10)結(jié)合文獻(xiàn)[27]的方法輸出F3:引入圖拓?fù)湫畔求解矩陣P,根據(jù)公式(3,4)結(jié)合文獻(xiàn)[10]的方法輸出P4:采用矩陣分解方法對(duì)P進(jìn)行求解,根據(jù)公式(11)的方法輸出U

2 仿真分析

為了證實(shí)本文提出算法的有效性，本文與已有的算法進(jìn)行比較：無(wú)監(jiān)督的SBMF算法、半監(jiān)督自旋玻璃模型SG[10]、半監(jiān)督NMF_LSE算法[24]。數(shù)據(jù)采用人工數(shù)據(jù)GN，真實(shí)數(shù)據(jù)采用Karate，Dolphins，F(xiàn)ootball，這些數(shù)據(jù)均為上述方法采用的公開(kāi)數(shù)據(jù)。最后用結(jié)合真實(shí)數(shù)據(jù)的合成贛南客家數(shù)據(jù)進(jìn)行了測(cè)試，結(jié)果采用10次平均，其它均采用50次實(shí)驗(yàn)的平均值與標(biāo)準(zhǔn)差標(biāo)注。

評(píng)價(jià)算法性能除了從社區(qū)分類正確率和F測(cè)度[10]來(lái)分析，還采用了通用的規(guī)范化互信息NMI來(lái)衡量。

2.1 人工合成數(shù)據(jù)GN實(shí)驗(yàn)

GN(Girvan-Newman)網(wǎng)絡(luò)數(shù)據(jù)是測(cè)試社區(qū)檢測(cè)算法的一類基準(zhǔn)數(shù)據(jù)集，劃分示意圖如圖1所示。網(wǎng)絡(luò)包含128個(gè)節(jié)點(diǎn)、4個(gè)社區(qū)，每32個(gè)節(jié)點(diǎn)劃分為1個(gè)社區(qū)，每個(gè)節(jié)點(diǎn)與Zin個(gè)社區(qū)內(nèi)和Zout個(gè)社區(qū)間節(jié)點(diǎn)隨機(jī)連接生成平均16條邊，即Zin+Zout=16.對(duì)于每對(duì)Zin與Zout隨機(jī)生成10個(gè)網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果顯示隨著Zout的增加，網(wǎng)絡(luò)結(jié)構(gòu)變化復(fù)雜，難以有效檢測(cè)社區(qū)。

與文獻(xiàn)[24]的NMF_LSE比較結(jié)果，可得如下結(jié)論：1) 與SBMF同樣，本文算法能有效獲取GN網(wǎng)絡(luò)的真實(shí)社區(qū)劃分；2) 與NMF_LSE比較，本文能在Zout=6，先驗(yàn)知識(shí)使用10%的時(shí)候?qū)⒄鎸?shí)社區(qū)劃分出來(lái)，見(jiàn)圖1(b)所示，與NMF_LSE性能接近。3) 隨著Zout的增加，網(wǎng)絡(luò)會(huì)變得難以劃分，當(dāng)達(dá)到8時(shí)，僅僅使用拓?fù)湫畔o(wú)法有效發(fā)現(xiàn)社區(qū)，而SSE算法與NMF_LSE算法仍然能有效檢測(cè)真實(shí)社區(qū)，且SSE在先驗(yàn)知識(shí)使用10%時(shí)能檢測(cè)出4個(gè)社區(qū)，相比NMF_LSE性能稍高。4) 本文SSE算法在使用先驗(yàn)知識(shí)達(dá)到26%的時(shí)候NMI=0.882±0.101，因此本文算法從一定程度上可以避免分辨率極限問(wèn)題，也表明了先驗(yàn)知識(shí)對(duì)社區(qū)劃分的重要影響。

圖1 GN合成數(shù)據(jù)劃分示意圖Fig.1 Sketch map of GN compose data

SBMF僅給出了正確檢測(cè)社區(qū)數(shù)，而文獻(xiàn)[10]由于作者沒(méi)有在GN上進(jìn)行測(cè)試，因此沒(méi)有與其對(duì)比。

2.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

Karate數(shù)據(jù)包含34個(gè)俱樂(lè)部成員作為節(jié)點(diǎn)，78條邊表示成員之間的關(guān)系。劃分示意圖如圖2所示。由于俱樂(lè)部管理員和教練之間的分歧，俱樂(lè)部一分為二，分別由上述兩人帶領(lǐng)各自團(tuán)隊(duì)組建。Dolphins該數(shù)據(jù)包含62個(gè)海豚，159條邊。劃分示意如圖3所示。Football數(shù)據(jù)有115個(gè)美國(guó)足球隊(duì)，613條邊。劃分示意如圖4所示。節(jié)點(diǎn)表示足球隊(duì)，如果兩隊(duì)之間有比賽則有邊連接。該數(shù)據(jù)已知的信息是足球隊(duì)被分為12個(gè)大型比賽，在某個(gè)比賽中足球隊(duì)通常與多個(gè)其它對(duì)進(jìn)行比賽。FaceBook數(shù)據(jù)有10個(gè)自我網(wǎng)絡(luò)(ego-networks)，包含193個(gè)社交圈和4 039個(gè)節(jié)點(diǎn)，88234條邊，網(wǎng)絡(luò)的平均聚類系數(shù)為0.605 5，該網(wǎng)絡(luò)為無(wú)向圖，每個(gè)節(jié)點(diǎn)包含26個(gè)屬性(包括家鄉(xiāng)、生日、同事、政治面貌等)。

與NMF_LSE實(shí)驗(yàn)結(jié)果表2比較，本文算法SSE在Karate上算法與其類似，在dolphins算法上性能較高，主要原因在于SSE有效的特征提取性能，但當(dāng)先驗(yàn)知識(shí)使用比例增大時(shí)，NMI值會(huì)不同程度下降，檢測(cè)的社區(qū)數(shù)目會(huì)增加，存在過(guò)度學(xué)習(xí)問(wèn)題。與SG實(shí)驗(yàn)結(jié)果fig1比較，在上述兩個(gè)數(shù)據(jù)結(jié)果類似，體現(xiàn)了半監(jiān)督的獨(dú)有特性。

與SBMF實(shí)驗(yàn)結(jié)果fig6(a)比較，本文算法SSE在檢測(cè)到社區(qū)數(shù)目為11和13時(shí)均有較高的NMI值，但與NMF_LSE算法結(jié)果Table II比較可知，在該數(shù)據(jù)集上的NMI值相對(duì)較低。同時(shí)發(fā)現(xiàn)在社區(qū)檢測(cè)數(shù)目增多的時(shí)候，可能能檢測(cè)出新的有意義的社區(qū)，如圖2(b)、3(b)、4(d)，一定程度上可以表示社區(qū)演化結(jié)果。SBMF算法在分解的過(guò)程中引入懲罰項(xiàng)控制分辨率極限問(wèn)題。而SG，NMF_LSE方法則受限于監(jiān)督信息的獲取。本次實(shí)驗(yàn)中SBMF可以看作本文算法的后處理階段。

圖2 Karate數(shù)據(jù)劃分示意圖Fig.2 Sketch map of Karate data to divide

圖3 dolphins數(shù)據(jù)劃分示意圖Fig.3 Sketch map of ddphins data to divide

為了驗(yàn)證本文算法在數(shù)據(jù)量較大時(shí)的有效性，以贛南客家群落為研究對(duì)象，研究其遷徙地屬性特征對(duì)遷徙后群落形成的影響，并進(jìn)一步探討群落分類。由于客家數(shù)據(jù)目前仍在整理階段，因此本文模仿LFR合成數(shù)據(jù)，主要用于測(cè)試不同社區(qū)節(jié)點(diǎn)數(shù)目不同以及節(jié)點(diǎn)度數(shù)差異較大的網(wǎng)絡(luò)結(jié)構(gòu)問(wèn)題。數(shù)據(jù)生成器允許指定節(jié)點(diǎn)數(shù)目、平均度數(shù)、社區(qū)大小分布、度分布、最小最大社區(qū)大小、重疊比率。LFR中社區(qū)大小和度分布都服從冪率分布，通過(guò)抽樣的方式生成節(jié)點(diǎn)和社區(qū)。本節(jié)實(shí)驗(yàn)中，節(jié)點(diǎn)數(shù)目設(shè)置為201 8，社區(qū)數(shù)目為13，平均度為10，節(jié)點(diǎn)度和社區(qū)大小的冪指數(shù)分別為-2和-1，重疊比率為0.1～0.5，并將平衡參數(shù)設(shè)置為1。表1中給出了本文算法在贛南客家網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，由于運(yùn)行時(shí)間較高，因此最終結(jié)果取10次實(shí)驗(yàn)的平均值。數(shù)據(jù)集生成時(shí)模擬Facebook引入屬性，分別是贛南水系(空間：長(zhǎng)度、流向、落差，特征：江、河、湖)、贛南地形(面積，特征：丘陵、山地)、耕地(山地、平原)、道路(村、省、國(guó)道)等14個(gè)特征屬性，屬性根據(jù)生成數(shù)據(jù)時(shí)的聚類或分類分別加入，屬性加入服從常見(jiàn)高斯分布，數(shù)據(jù)生成時(shí)間為東晉南北朝末第一次大遷徙到唐末中期第二次大遷徙階段。

圖4 football數(shù)據(jù)劃分示意圖Fig.4 Sketch map of football data to divide

表1 在合成贛南客家數(shù)據(jù)集上進(jìn)行測(cè)試結(jié)果Table 1 Test result of Gannan Hakka

表1中，本文算法主要考慮引入類別知識(shí)后邊的必連和必不連信息，同時(shí)考慮先驗(yàn)知識(shí)中的節(jié)點(diǎn)屬性。分析F測(cè)度，Micro-F1基本呈現(xiàn)遞增趨勢(shì)，Macro-F1則無(wú)此規(guī)律，可見(jiàn)訓(xùn)練數(shù)據(jù)集的選取對(duì)算法性能有較大影響，同時(shí)也說(shuō)明了數(shù)據(jù)中存在較大的冗余。同時(shí)從表1中發(fā)現(xiàn)，單單分析社區(qū)識(shí)別準(zhǔn)確率，SSE算法在使用訓(xùn)練數(shù)據(jù)方面，隨著使用比例加大識(shí)別率會(huì)單調(diào)遞增。而采用所有數(shù)據(jù)后，對(duì)于不同屬性，識(shí)別準(zhǔn)確率呈現(xiàn)多樣性，并不會(huì)隨著屬性增加識(shí)別率單調(diào)遞增，表明算法加入的屬性有類似噪聲的作用。所以，對(duì)屬性提取后，選取江、河、湖(4，5，6)，山地、平原(10，11)以及江、平原(4，11)計(jì)算識(shí)別準(zhǔn)確率，結(jié)果發(fā)現(xiàn)水系對(duì)贛南客家遷徙相比于耕地對(duì)遷徙意向起了較多的影響，而水系和耕地結(jié)合則更能影響遷徙路徑，因此遷徙中地理環(huán)境對(duì)贛南客家人有較為重要的作用。

3 結(jié)束語(yǔ)

本文提出的半監(jiān)督策略，能有機(jī)結(jié)合已有先驗(yàn)知識(shí)，獲取全局最優(yōu)解，但對(duì)數(shù)據(jù)要求較高，在人工和真實(shí)數(shù)據(jù)上的仿真實(shí)驗(yàn)結(jié)果表明提出的方法具有較好的效果和可擴(kuò)展性。下一步工作將集中在各類附加信息在動(dòng)態(tài)社區(qū)檢測(cè)中的影響及應(yīng)用，以及對(duì)網(wǎng)絡(luò)各類型數(shù)據(jù)的降解工作，便于處理海量數(shù)據(jù)。

本文給出了一種新的驗(yàn)證贛南客家遷徙的思路，生成的實(shí)驗(yàn)數(shù)據(jù)可以說(shuō)明遷徙中的部分影響因素，下一步工作集中在數(shù)據(jù)生成器，在設(shè)計(jì)時(shí)應(yīng)該考慮度分布與屬性分布相結(jié)合，同步生成可能更切合實(shí)際情況。