基于邊分類的SVM模型在社區(qū)發(fā)現(xiàn)中的研究

王鵬，高鋮，楊華民

（長(zhǎng)春理工大學(xué)　計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春　130022）

基于邊分類的SVM模型在社區(qū)發(fā)現(xiàn)中的研究

王鵬，高鋮，楊華民

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春130022）

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究的重要內(nèi)容，也是分析網(wǎng)絡(luò)結(jié)構(gòu)的重要途徑。分析了社區(qū)發(fā)現(xiàn)研究中存在的問(wèn)題，提出了一種基于邊分類的SVM模型。通過(guò)邊頂點(diǎn)相似度和邊介數(shù)來(lái)表示邊的特征，從而構(gòu)造分類函數(shù)。利用LFR生成社區(qū)結(jié)構(gòu)已知的人工網(wǎng)絡(luò)，通過(guò)人工網(wǎng)絡(luò)數(shù)據(jù)訓(xùn)練基于邊分類的SVM模型，對(duì)分類函數(shù)的參數(shù)進(jìn)行估計(jì)，利用訓(xùn)練模型對(duì)真實(shí)網(wǎng)絡(luò)進(jìn)行社區(qū)分類并通過(guò)標(biāo)準(zhǔn)化互信息（NMI）和整體準(zhǔn)確度來(lái)評(píng)價(jià)分類效果。實(shí)驗(yàn)得到了較高的整體準(zhǔn)確度和NMI值。實(shí)驗(yàn)表明基于邊分類的SVM訓(xùn)練模型對(duì)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)劃分有較高的準(zhǔn)確度，表明該方法是可行的。

社區(qū)發(fā)現(xiàn)；邊分類；SVM模型；LFR

現(xiàn)實(shí)世界中的很多復(fù)雜系統(tǒng)都可以通過(guò)將實(shí)體抽象為節(jié)點(diǎn)，實(shí)體之間的聯(lián)系抽象為邊的復(fù)雜網(wǎng)絡(luò)來(lái)表示。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征，刻畫(huà)了網(wǎng)絡(luò)中節(jié)點(diǎn)連接關(guān)系的局部聚集特性，對(duì)揭示復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能之間的聯(lián)系有著十分重要的作用。對(duì)社區(qū)結(jié)構(gòu)的研究主要有社區(qū)發(fā)現(xiàn)、社區(qū)演化分析、社區(qū)網(wǎng)絡(luò)動(dòng)力學(xué)分析等［1］，其中，社區(qū)發(fā)現(xiàn)是結(jié)構(gòu)分析的一個(gè)基本任務(wù)。

社區(qū)發(fā)現(xiàn)的基本思路就是識(shí)別網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，使集合內(nèi)的節(jié)點(diǎn)之間連接緊密，集合間的聯(lián)結(jié)比較稀疏?；谶@個(gè)思路，2002年Girvan和Newman提出了基于邊介數(shù)劃分的GN（Girvan-Newman）算法［2］，該算法通過(guò)計(jì)算邊介數(shù)，識(shí)別社區(qū)間連接，從而切斷社區(qū)間連接劃分社區(qū)，但該算法具有很高的時(shí)間復(fù)雜度，不適合處理大規(guī)模網(wǎng)絡(luò)。為了度量社區(qū)內(nèi)的緊密程度，2004年Newman提出了基于模塊性的FN（Fast Newman）算法［3］，該算法定義模塊度函數(shù)Q［4］，將使函數(shù)Q值增加或者減小最少的社區(qū)合并，從而選擇對(duì)應(yīng)Q值最大的社區(qū)劃分作為聚類結(jié)果，同樣該算法的計(jì)算開(kāi)銷較大。2007年Raghavan等人提出了標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）［5］，該算法通過(guò)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)標(biāo)簽來(lái)更新自身標(biāo)簽，通過(guò)標(biāo)簽來(lái)確定節(jié)點(diǎn)社區(qū)，該算法收斂速度較快，聚類精度有待提高。在前人研究的基礎(chǔ)上，本文提出了一種基于邊劃分的機(jī)器學(xué)習(xí)方法，通過(guò)建立基于邊劃分的支持向量機(jī)模型（Support Vector Machine，SVM［8］）利用人工網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行機(jī)器學(xué)習(xí)，進(jìn)而對(duì)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析實(shí)驗(yàn)來(lái)提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確度，并利用標(biāo)準(zhǔn)化互信息（Normalized Mutual information，NMI［10］）和整體準(zhǔn)確率來(lái)衡量結(jié)果的優(yōu)劣，實(shí)驗(yàn)結(jié)果表明該方法是可行的。

1　基于邊分類的SVM模型

復(fù)雜網(wǎng)絡(luò)的抽象表示是由節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)，在圖論中即可表示為G=（V，E），V表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E表示網(wǎng)絡(luò)中邊的集合［6］。那么社區(qū)發(fā)現(xiàn)問(wèn)題即可表述為：對(duì)于任意一條邊ab∈E，節(jié)點(diǎn)a，b是否屬于同一個(gè)社區(qū)。對(duì)于二元分類問(wèn)題，本文構(gòu)造分類器函數(shù)h，對(duì)于邊ab的特征Xab，通過(guò)計(jì)算分類函數(shù)h（ ）Xab的值來(lái)判斷節(jié)點(diǎn)a，b是否屬于同一個(gè)社區(qū)，遍歷網(wǎng)絡(luò)中的每一條邊，由此對(duì)網(wǎng)絡(luò)中的邊進(jìn)行切割，最終得到社區(qū)集合。算法流程圖如圖1所示。

圖1　算法流程圖

1.1分類函數(shù)

構(gòu)造基于邊的分類器函數(shù)，需要首先確定邊的特征量。復(fù)雜網(wǎng)絡(luò)中對(duì)邊的特征度量主要有邊介數(shù)、邊聚集系數(shù)、邊兩端節(jié)點(diǎn)的度以及鄰近結(jié)點(diǎn)個(gè)數(shù)等。本文通過(guò)計(jì)算邊兩端節(jié)點(diǎn)的Jaccard相似度和邊介數(shù)來(lái)作為該條邊的特征度量，并根據(jù)特征量構(gòu)造分類器函數(shù)。

1.1.1Jaccard相似度

節(jié)點(diǎn)的Jaccard相似性是根據(jù)兩節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的交集節(jié)點(diǎn)數(shù)占并集節(jié)點(diǎn)數(shù)的比重定義的［7］，其公式如下：

其中Adj（）表示節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，其相似性的取值范圍為［0，1］。傳統(tǒng)的Jaccard相似度節(jié)點(diǎn)的鄰居節(jié)點(diǎn)并不包含自身，但實(shí)際網(wǎng)絡(luò)中存在邊ab且。從相互關(guān)系來(lái)看，兩個(gè)節(jié)點(diǎn)相連接在某種程度上存在相似性，因此本文采用修正的Jaccard相似度，在節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合中并入自身節(jié)點(diǎn)。

1.1.2邊介數(shù)

根據(jù)社區(qū)發(fā)現(xiàn)的思想，社區(qū)與社區(qū)之間聯(lián)系稀疏，社區(qū)內(nèi)聯(lián)系密切，可以發(fā)現(xiàn)連接社區(qū)間的邊成為社區(qū)之間溝通的主要橋梁。基于這個(gè)思想，Girvan 和Newman提出了邊介數(shù)的概念：一條邊的邊介數(shù)是網(wǎng)絡(luò)中任意兩點(diǎn)的最短路徑通過(guò)該邊的路徑數(shù)與最短路徑總和的比值［1］。定義公式如下：

其中g(shù)ab表示通過(guò)邊ab的最短路徑數(shù)，gij表示網(wǎng)絡(luò)中任意兩點(diǎn)的最短路徑數(shù)。為了方便實(shí)驗(yàn)處理，本文采用標(biāo)準(zhǔn)邊介數(shù)，即將邊介數(shù)做歸一化處理。

由邊的特征向量構(gòu)造分類器，本文提出通過(guò)加權(quán)的節(jié)點(diǎn)相似度和邊介數(shù)得分來(lái)判斷邊的歸屬，從而進(jìn)行切割劃分社區(qū)。得分公式定義如下：

其中α為邊特征向量元素的權(quán)重，Sab的取值范圍為［0，1］。自然地，通過(guò)設(shè)定閾值來(lái)定義分類器函數(shù)，當(dāng)Sab＞τ???0＜τ＜1時(shí)，邊ab屬于社區(qū)內(nèi)；相反當(dāng)Sab≤τ時(shí)，邊ab屬于社區(qū)間，即節(jié)點(diǎn)a，b屬于不同社區(qū)。因此，分類器函數(shù)可以表示為：

1.2SVM模型及參數(shù)估計(jì)

對(duì)模型參數(shù)的估計(jì)實(shí)際上就是對(duì)邊特征向量所對(duì)應(yīng)的權(quán)重向量的估計(jì)。對(duì)于社區(qū)結(jié)構(gòu)已知的復(fù)雜網(wǎng)絡(luò)很容易得到邊的特征向量，同時(shí)還有邊的歸屬，即模型的響應(yīng)變量，定義如下：

在自變量與響應(yīng)變量已知的情況下，通過(guò)利用SVM模型進(jìn)行參數(shù)估計(jì)，進(jìn)而將訓(xùn)練模型應(yīng)用到社區(qū)結(jié)構(gòu)未知的網(wǎng)絡(luò)，進(jìn)行社區(qū)發(fā)現(xiàn)研究。SVM模型是一種機(jī)器學(xué)習(xí)方法，該算法基于統(tǒng)計(jì)學(xué)習(xí)理論采用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，使得分類準(zhǔn)確率和預(yù)測(cè)能力都能達(dá)到較高水平。

假設(shè)存在線性可分的數(shù)據(jù)集（X，Y） ，則線性判別函數(shù)即可定義為g（X）=W·X+b，那么，存在一個(gè)超平面W·X+b=0，使得數(shù)據(jù)分布在該平面的兩側(cè)。對(duì)任意xi存在平行于超平的邊界面W·xi+b≥1或W·xi+b≤-1，最大化兩個(gè)平行超平面的距離，即。因此，最優(yōu)分類面的求解，轉(zhuǎn)化為了求‖‖W的最小值，即求函數(shù)的最小值。這是一個(gè)二次優(yōu)化問(wèn)題，采用拉格朗日乘子法進(jìn)行求解，定義Lagrange函數(shù)［9］：

其中αi＞0是拉格朗日系數(shù)。在參數(shù)W，b下求Lagrange函數(shù)的極小值，關(guān)于Lagrange函數(shù)分別對(duì)W，b求偏導(dǎo)，得到原問(wèn)題的對(duì)偶問(wèn)題表達(dá)式：

最后利用符號(hào)函數(shù)得到最優(yōu)分類函數(shù)：

2　社區(qū)評(píng)價(jià)

對(duì)于社區(qū)結(jié)構(gòu)已知的基準(zhǔn)網(wǎng)絡(luò)，為了比較實(shí)驗(yàn)結(jié)果與真實(shí)社區(qū)之間的相似程度，利用Lancichinetti提出的NMI指標(biāo)來(lái)評(píng)價(jià)模型的優(yōu)劣，同時(shí)本文也提出了一種新的評(píng)價(jià)指標(biāo)整體準(zhǔn)確率ρ。

2.1NMI指標(biāo)

Normalized Mutual information（NMI［10］，標(biāo)準(zhǔn)化互信息），是基于信息論和概率論提出的一種衡量聚類或分類效果的評(píng)價(jià)指標(biāo)。NMI的值域?yàn)椋?，1］，其值越大說(shuō)明實(shí)驗(yàn)結(jié)果越接近真實(shí)情況。NMI的公式定義如下：

其中X，Y為兩個(gè)離散隨機(jī)變量，I（X；Y ）表示兩個(gè)隨機(jī)變量的互信息，H（X），H（Y ）表示兩個(gè)隨機(jī)變量的邊緣熵，p（x），p（y），p（x，y）分別表示隨機(jī)變量的概率分布和聯(lián)合概率分布。

2.2整體準(zhǔn)確率

在社區(qū)發(fā)現(xiàn)試驗(yàn)中，真實(shí)網(wǎng)絡(luò)的社區(qū)數(shù)量往往比實(shí)驗(yàn)發(fā)現(xiàn)的社區(qū)數(shù)量少，觀察實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，真實(shí)網(wǎng)絡(luò)社區(qū)往往被拆分成若干個(gè)子社區(qū)。在這種情況下NMI指標(biāo)并不能很好的衡量算法的效果。因此文本提出了一種新的衡量指標(biāo)：整體準(zhǔn)確率ρ，其公式定義如下：

其中Sr表示實(shí)驗(yàn)發(fā)現(xiàn)的社區(qū)，nr對(duì)應(yīng)為社區(qū)的節(jié)點(diǎn)數(shù)，表示社區(qū)Sr中節(jié)點(diǎn)屬于第i個(gè)真實(shí)社區(qū)的個(gè)數(shù)，m為真實(shí)社區(qū)個(gè)數(shù)，k為實(shí)驗(yàn)發(fā)現(xiàn)的社區(qū)個(gè)數(shù)，nri表示社區(qū)Sr中節(jié)點(diǎn)屬于真實(shí)社區(qū)最多的第i個(gè)真實(shí)社區(qū)的規(guī)模。

3　仿真實(shí)驗(yàn)及結(jié)果分析

LFR［11］是由Lancichinetti和Fortunato提出的一種標(biāo)準(zhǔn)測(cè)試網(wǎng)絡(luò)?，F(xiàn)實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)度服從冪律分布，利用LFR生成的人工網(wǎng)絡(luò)節(jié)點(diǎn)度同樣服用冪律分布，因此利用LFR生成的網(wǎng)絡(luò)結(jié)構(gòu)與現(xiàn)實(shí)網(wǎng)絡(luò)相似。本文利用LFR生成的數(shù)據(jù)訓(xùn)練分類器，確定相應(yīng)的分類器參數(shù)。為了構(gòu)造具有特定性質(zhì)的LFR網(wǎng)絡(luò)，需要一定的參數(shù)配置，其中N表示節(jié)點(diǎn)的個(gè)數(shù)；k表示節(jié)點(diǎn)的平均度；maxk表示最大節(jié)點(diǎn)度；minc表示最小社區(qū)的節(jié)點(diǎn)個(gè)數(shù)；maxc表示最大社區(qū)的節(jié)點(diǎn)個(gè)數(shù)；最為重要的是混合參數(shù)μ，它控制社區(qū)之間的關(guān)聯(lián)程度。當(dāng)μ=0時(shí)，社區(qū)之間沒(méi)有連接，即社區(qū)之間相互獨(dú)立；當(dāng)μ=1時(shí)，網(wǎng)絡(luò)中每一條邊的兩個(gè)節(jié)點(diǎn)分別屬于不同的兩個(gè)社區(qū)，社區(qū)之間聯(lián)系密切。

在不同混合參數(shù)μ下，對(duì)社區(qū)發(fā)現(xiàn)算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)本文采用LFR生成的標(biāo)準(zhǔn)GN網(wǎng)絡(luò)，訓(xùn)練數(shù)據(jù)利用LFR生成，參數(shù)設(shè)置為N=1000，k=10，maxk=30，minc=20，maxc=100，mu=0.5。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2　訓(xùn)練模型與原始模型對(duì)標(biāo)準(zhǔn)GN網(wǎng)絡(luò)劃分結(jié)果比較

圖2中紅線表示訓(xùn)練模型，黑線表示原始模型，可以看出訓(xùn)練模型基本優(yōu)于原始模型，特別是在混合參數(shù)不大的情況下，訓(xùn)練模型對(duì)社區(qū)發(fā)現(xiàn)的精準(zhǔn)度較高。

真實(shí)數(shù)據(jù)采用經(jīng)典的Zachary空手道俱樂(lè)部網(wǎng)絡(luò)Karate、美國(guó)大學(xué)生足球賽網(wǎng)絡(luò)Football、海豚關(guān)系網(wǎng)絡(luò)Dolphins、美國(guó)政論著作網(wǎng)絡(luò)Polbooks，這三個(gè)真實(shí)網(wǎng)絡(luò)都有清晰的社區(qū)結(jié)構(gòu)，方便與實(shí)驗(yàn)結(jié)果進(jìn)行比較分析。實(shí)驗(yàn)結(jié)果如表1所示。

表1　真實(shí)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

從上表可以看出訓(xùn)練模型對(duì)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)有較好的分類效果，真實(shí)社區(qū)個(gè)數(shù)與分類社區(qū)個(gè)數(shù)存在一定的差別，這與模型本身和模型的訓(xùn)練程度有一定的關(guān)系，模型的精度可以進(jìn)一步的提高。受分類社區(qū)個(gè)數(shù)影響，NMI值相對(duì)偏低，但整體準(zhǔn)確率基本保持在較高水平，說(shuō)明實(shí)驗(yàn)分類社區(qū)中的節(jié)點(diǎn)純度很高。

4　結(jié)論

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究的重要內(nèi)容之一，許多專家學(xué)者對(duì)這方面做出了深入的研究，也取得了很大的成果。本文基于網(wǎng)絡(luò)中邊的特征，構(gòu)造分類函數(shù)，利用LFR仿照現(xiàn)實(shí)網(wǎng)絡(luò)性質(zhì)參數(shù)，生成一些社區(qū)結(jié)構(gòu)已知的人工網(wǎng)絡(luò)，通過(guò)人工網(wǎng)絡(luò)數(shù)據(jù)訓(xùn)練基于邊劃分的SVM模型，利用SVM模型進(jìn)行參數(shù)估計(jì)，并利用訓(xùn)練模型對(duì)未知網(wǎng)絡(luò)進(jìn)行社區(qū)分類，通過(guò)NMI和整體準(zhǔn)確度評(píng)價(jià)分類結(jié)果。實(shí)驗(yàn)表明基于邊分類的SVM訓(xùn)練模型對(duì)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)劃分有較高的準(zhǔn)確度，說(shuō)明文中的方法是可行的。

［1］ 程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，08（1）：57-70.

［2］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826.

［3］ Newman M E J.Fast algorithm for detecting community structure in networks.［J］.Phys Rev E Stat Nonlin Soft Matter Phys，2004，69（6）：279-307.

［4］ Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：292-313.

［5］Raghavan U N，Albert R，Kumara S.Near linear timealgorithmtodetectcommunitystructuresin large-scale networks.［J］.Phys Rev E Stat Nonlin Soft Matter Phys，2007，76（3）：036106-036111.

［6］ Lei Tang，Huan Liu著，文益民，閉應(yīng)洲譯.社會(huì)計(jì)算：社區(qū)發(fā)現(xiàn)和社會(huì)媒體挖掘［M］.北京：機(jī)械工業(yè)出版. 2012.

［7］Laarhoven T V，Marchiori E.Network community detectionusingedgeclassifierstrainedonLFR graphs［C］.ESANN 2013：21st European Symposium on Artificial Neural Networks，Computational IntelligenceAndMachineLearningBrugesApril 24-25-26，2013.Proceedings，2013.

［8］ Guyon I，Weston J，Barnhill S，et al.Gene Selection for Cancer Classification using Support Vector Machines［J］.Machine Learning，2002，46（1-3）：389-422.

［9］ 鞏知樂(lè)，張德賢，胡明明.一種改進(jìn)的支持向量機(jī)的文本分類算法［J］.計(jì)算機(jī)仿真，2009，26（7）：164-167.

［10］Lancichinetti A，F(xiàn)ortunato S，Kertész J.Detecting the overlapping and hierarchical community structureincomplexnetworks［J］.NewJournalof Physics，2009，11（15）：19-44.

［11］Radicchi F，Castellano C，Cecconi F，et al.Defining and Identifying Communities in Networks［J］. Proceedings of the National Academy of Sciences of the United States of America，2004，101（9）：2658-2663.

The SVM Model Based on Edge Classification Research in Community Detection

WANG Peng，GAO Cheng，YANG Huamin
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

The community detection is an important part of the complex network research，and it is also the important way to analyze the network structure.In this paper，the problems existing in the community detection research are analyzed and a kind of SVM model based on the edge classification is proposed.Based on vertex similarity and edge betweenness the characteristics of the edge are represented，so the classification function is constructed.The artificial network of the known community structure is generated by LFR.Through artificial network data training based on edge classification of SVM model，the parameters of classification function are estimated and the real network community is simulated by using the trained model.The higher overall accuracy and NMI values are got in the experiment.Experiments show that the edge classification of SVM trained model have higher accuracy on real network data and the method is effective.

community detection；edge classification；SVM model；LFR

TP391

A

1672-9870（2015）05-0127-04

2015-06-08

王鵬（1973-），男，副教授，E-mail：635461179@qq.com

楊華民（1963-），男，博士，教授，博士生導(dǎo)師，E-mail：yhm@cust.edu.cn