王鵬，高鋮，楊華民

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

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

王鵬，高鋮，楊華民

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

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

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

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

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

1　基于邊分類的SVM模型

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

圖1　算法流程圖

1.1分類函數(shù)

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

1.1.1Jaccard相似度

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

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

1.1.2邊介數(shù)

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

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

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

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

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

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

在自變量與響應(yīng)變量已知的情況下，通過利用SVM模型進(jìn)行參數(shù)估計，進(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)計學(xué)習(xí)理論采用結(jié)構(gòu)風(fēng)險最小化原則，使得分類準(zhǔn)確率和預(yù)測能力都能達(dá)到較高水平。

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

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

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

2　社區(qū)評價

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

2.1NMI指標(biāo)

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

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

2.2整體準(zhǔn)確率

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

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

3　仿真實驗及結(jié)果分析

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

在不同混合參數(shù)μ下，對社區(qū)發(fā)現(xiàn)算法進(jì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。實驗結(jié)果如圖2所示。

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

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

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

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

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

4　結(jié)論

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

［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)洲譯.社會計算：社區(qū)發(fā)現(xiàn)和社會媒體挖掘［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］ 鞏知樂，張德賢，胡明明.一種改進(jìn)的支持向量機(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