王韞燁,孔 珊,李亞倫

(1.鄭州師范學院 信息科學與技術(shù)學院,河南 鄭州 450044;2.天津工業(yè)大學 電子與信息工程學院,天津300387)

社交網(wǎng)絡(luò)是一種以用戶為節(jié)點、以用戶關(guān)系為邊的網(wǎng)絡(luò)結(jié)構(gòu),用戶的興趣、行為、功能等關(guān)系使社交網(wǎng)絡(luò)中存在多個社區(qū)或簇。社交網(wǎng)絡(luò)的結(jié)構(gòu)對于探求信息的傳播方式和獲取價值信息(如廣告投放、潛在商機發(fā)現(xiàn))等具有重要價值和意義[1]。大部分社交網(wǎng)絡(luò)均可抽象為無向或有向圖,研究這些圖結(jié)構(gòu),有利于挖掘出其中潛在的有價值信息。

聚類是實現(xiàn)結(jié)構(gòu)分析與劃分的有效方法[2]。常見的社交網(wǎng)絡(luò)聚類方法有基于鏈接稠密度的方法[3]、考慮節(jié)點功能特性[4]和網(wǎng)絡(luò)有向性等聚類方法[5]、考慮樞紐點的聚類[6]、基于結(jié)構(gòu)近似度的聚類算法等[7]。文獻[3]提出了基于鏈接稠密度的方法,但未考慮社交網(wǎng)絡(luò)的節(jié)點功能特性;文獻[4]考慮節(jié)點功能特性,但只能適用于無向網(wǎng)絡(luò);文獻[5]提出了網(wǎng)絡(luò)的有向性等聚類方法,但損失了社交網(wǎng)絡(luò)結(jié)構(gòu)的特性;文獻[6]考慮樞紐點的聚類,但尚未區(qū)分節(jié)點功能;文獻[7]提出基于結(jié)構(gòu)近似度的聚類算法,沒有考慮社交網(wǎng)絡(luò)的非對稱性。針對上述問題,本文提出一種基于結(jié)構(gòu)近似度的非對稱網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)聚類算法,算法具有低復雜度且能鑒別離群節(jié)點和樞紐節(jié)點。

1 社交網(wǎng)絡(luò)聚類問題分析

1.1 網(wǎng)絡(luò)的結(jié)構(gòu)近似度

網(wǎng)絡(luò)的結(jié)構(gòu)分析[8]就是首先規(guī)定一組能代表節(jié)點特征的定義,表示出各個節(jié)點的特征,通過定性定量的計算,研究圖內(nèi)相鄰節(jié)點之間的聯(lián)系緊密程度,進而實現(xiàn)對圖的分簇劃分,使相似的節(jié)點處于同一簇中,特殊的節(jié)點遍布在簇與簇之間。

在社交網(wǎng)絡(luò)中,有向邊的指向有著隱含的意義,由節(jié)點主動建立的連接可代表節(jié)點自身的行為、個人興趣和意愿等;同理,被動處理的節(jié)點則顯示出非自身節(jié)點對自身節(jié)點的關(guān)注,而不是直接表明節(jié)點的自身特征。在處理這種情形時,節(jié)點的出邊比入邊更能體現(xiàn)出節(jié)點的信息。

因此,本文將節(jié)點的出邊作為重點考察對象,提出結(jié)構(gòu)近似度的假設(shè):如果兩節(jié)點的相鄰鄰居節(jié)點交集越大,則兩個體被分配到相同集群的概率越高。本文采用的是圖劃分算法,即將網(wǎng)絡(luò)聚類問題看成圖論中的劃分子圖問題,把劃分出的子圖看做是一個簇,繼續(xù)對子圖(簇)進行劃分。

1.2 基于結(jié)構(gòu)近似度的有向網(wǎng)絡(luò)聚類模型

將社交網(wǎng)絡(luò)抽象為圖結(jié)構(gòu),其中的節(jié)點集用V集合表示,有向邊集用E集合表示,根據(jù)圖的拓撲結(jié)構(gòu),定義一組關(guān)系來表示節(jié)點之間的相互連接情況。通過收集圖中的拓撲信息并計算這些相關(guān)屬性關(guān)系來定量表示圖中相鄰節(jié)點的關(guān)系,并以此來作為劃分圖的依據(jù),將圖劃分為一個個簇結(jié)構(gòu),剩余的節(jié)點就是離群節(jié)點和樞紐節(jié)點[9,10],如圖1所示。圖1中,簇1和簇2分別為不同的簇結(jié)構(gòu),擁有共同的樞紐節(jié)點,另外還有無簇節(jié)點和離群節(jié)點。

首先給出幾個定義:

(1)可達節(jié)點:以節(jié)點I為出邊的節(jié)點所能到達的所有節(jié)點即為節(jié)點I的可達節(jié)點;

(2)結(jié)構(gòu)近似度:兩個節(jié)點可達節(jié)點越多,這兩節(jié)點屬同簇的概率越高,故結(jié)構(gòu)近似度代表著兩個節(jié)點的相近程度[4];

(3)可達鄰居:滿足結(jié)構(gòu)近似度要求的可達節(jié)點的集合。集合的大小受近似度值影響;

(4)核節(jié)點:滿足結(jié)構(gòu)相似度且滿足可達鄰居節(jié)點個數(shù)要求的節(jié)點。受可達鄰居集合影響。

算法中使用的符號說明如下:

ε是用于劃分鄰居與非鄰居的相似度閾值,μ(μ>0)是活躍節(jié)點的到達鄰居臨界參數(shù),節(jié)點i到節(jié)點j的有向邊,節(jié)點i與j的結(jié)構(gòu)相似度定義為

Γ(i)={j∈V|∈E}∪{i}

(1)

j的結(jié)構(gòu)相似度為

(2)

節(jié)點i的到達鄰居為

Nε(i)={j∈Γ(i)|σ(i,j)≥ε,ε>0}

(3)

核結(jié)點為

Cε,μ(i)?|Nε(i)|≥μ

(4)

i直接結(jié)構(gòu)可到j(luò)

DRε,μ(i,j)?Cε,μ(i)∧j∈Nε(i)

(5)

1.3 算法流程

本文算法流程如下:

Step1根據(jù)結(jié)構(gòu)相似度闕值ε篩選計算出所有的核節(jié)點。根據(jù)達到鄰居入?yún)㈥I值μ預處理所有節(jié)點的直接可到節(jié)點;

Step2將所有節(jié)點標為未分簇節(jié)點;

Step3遍歷預處理好的所有核節(jié)點,搜索其結(jié)構(gòu)直接可到鄰居,將核節(jié)點及其結(jié)構(gòu)直接可到鄰居加入到(以核節(jié)點的ID來命名該簇)同一簇。反復執(zhí)行以上判斷循環(huán),直至沒有新的節(jié)點來拓展簇結(jié)構(gòu)為止;

Step4遍歷所有(孤立點)未分簇節(jié)點,以與其相鄰的簇的數(shù)目為依據(jù),將其劃分為離群節(jié)點或樞紐節(jié)點。即若存在多個(大于一個)簇與其相連,則該點為樞紐節(jié)點;否則,該節(jié)點即為離群節(jié)點。

算法偽代碼如下:

Input:有向圖的拓撲結(jié)構(gòu)G={V,E},參數(shù)ε和μ

Output:各節(jié)點的情況(或簇編號或無簇或離群或樞紐)

//根據(jù)相似度闕值ε及到達鄰居臨界參數(shù)μ預處理計算出所有的核節(jié)點

prepare(ε,μ);

While(I為核節(jié)點)//遍歷所有核節(jié)點

{ If(solve(I))continue;//如果處理過,則跳過

賦予節(jié)點I新的簇編號C

將核節(jié)點I的達到相鄰節(jié)點加入Q隊列

While(Q不為空)

{ 取Q中節(jié)點J

If(J未處理過)

{ If(J為核節(jié)點){將J加入ClusterC中,且將J的到達鄰居集放入隊列}

Else{將J加入簇C中}

}

Else

{If(J為核節(jié)點){直接將J所在的簇中所有節(jié)點加入到新簇C中}

Else{進行邊界點處理算法}

}

將J移出隊列Q}

}

//處理離群點和樞紐點

if() 將I記做樞紐節(jié)點

else將I記做離群節(jié)點

1.4 算法特點分析

(1)對于邊集較少的稀疏圖來說,基本只用遍歷一遍所有核節(jié)點即可分簇成功,算法的時間復雜度可以接受;

(2)對簇的邊界劃分,不是簡單的將同屬于兩簇的邊界點隨意劃分,而是設(shè)定了一組邊界點處理算法,計算權(quán)衡后將其劃分到不同的簇結(jié)構(gòu);

(3)以出邊的作為劃分依據(jù),考慮了非理想性網(wǎng)絡(luò)的方向性;

(4)沒有僅重視簇的劃分情況,也對特殊節(jié)點的意義作用進行了分析與推廣。

本算法的缺點在于:對于較大數(shù)據(jù)集,包含較多的節(jié)點和有向邊,可能需要相當多的(內(nèi)存)存儲空間,空間復雜度不可接受;沒有考慮對網(wǎng)絡(luò)圖結(jié)構(gòu)節(jié)點及邊的及時更新。

1.5 算法時間復雜度

在提前預處理好結(jié)構(gòu)近似度以及到達鄰居節(jié)點的情況下,遍歷節(jié)點的時間復雜度為O(n),即該算法僅需要遍歷一次所有核節(jié)點;相比有向圖的遍歷,在最差的情況下,節(jié)點與其他所有節(jié)點均存在有向邊,時間復雜度為O(n2)。在實際生活中,接觸到的網(wǎng)絡(luò)大多是稀疏網(wǎng)絡(luò),即與完全圖相比弧的個數(shù)并不是很多,這樣算法內(nèi)部第二層循環(huán)遍歷邊的次數(shù)不會很多,故整個算法的時間復雜度仍然相對較低,這對于處理簡單網(wǎng)絡(luò)相對有優(yōu)勢。

此外,算法執(zhí)行結(jié)果不會受到數(shù)據(jù)相關(guān)讀入順序的影響。簇編號采用的是核節(jié)點最大范圍的編號。算法默認所有節(jié)點的編號均為[1,最大節(jié)點數(shù)]。

2 實驗結(jié)果分析與對比

2.1 實驗環(huán)境及參數(shù)設(shè)置

通過C++語言編程實現(xiàn)該算法,分別利用自定義的有向網(wǎng)絡(luò)數(shù)據(jù)集和標準數(shù)據(jù)集來測試算法的性能及準確性。標準的試驗數(shù)據(jù)集有Flickr數(shù)據(jù)集、P2P網(wǎng)絡(luò)數(shù)據(jù)集、YouTube數(shù)據(jù)集[7,11],最后通過pajek(一種大型復雜網(wǎng)絡(luò)分析工具)繪制出相應(yīng)的劃分結(jié)果圖[12],分析并計算出相關(guān)參數(shù)。算法通過TXT輸入,輸出結(jié)果分為4種:節(jié)點的簇編號、無簇節(jié)點,樞紐節(jié)點以及離群節(jié)點。

本算法的輸入包含ε和μ兩個參數(shù),設(shè)置μ取[1,最大鄰居數(shù)]之間的整數(shù),ε取[0,1]中步長為0.1的所有值進行測試。首先利用Txt2pajek將數(shù)據(jù)集的(包含邊信息)txt文件轉(zhuǎn)換為net文件,方便Pajek進行數(shù)據(jù)讀入和處理;然后利用Pajek讀入net文件,并繪制出對應(yīng)的有向結(jié)構(gòu)圖。本文算法采用編輯器CodeBlocks進行編寫編譯并運行[13]。

2.2 實驗結(jié)果及分析

2.2.1 自定義數(shù)據(jù)集結(jié)果及分析

本文自定義數(shù)據(jù)集結(jié)構(gòu)如圖2所示。圖2顯示,該數(shù)據(jù)集結(jié)構(gòu)包含9個節(jié)點和8條有向邊,實驗結(jié)果如圖3-6所示。

分別采用不同的參數(shù)設(shè)置對算法進行驗證,發(fā)現(xiàn)在ε∈{0.1,0.2},μ∈{1,2}范圍內(nèi),由于ε和μ參數(shù)的要求標準較低,故劃分結(jié)果如圖3所示。只將所有節(jié)點整體劃分為一個簇,ID為9,即簇ID:9。在ε∈{0.3,0.4,0.5},μ∈{1,2}和ε∈{0.1,0.2,0.3,0.4,0.5},μ=3范圍內(nèi),由于結(jié)構(gòu)相近度闕值或鄰居節(jié)點數(shù)要求更加嚴苛,簇的劃分也相應(yīng)嚴苛,劃分結(jié)果如圖4所示。由圖4可見,9個節(jié)點劃分為兩個簇結(jié)構(gòu),簇ID:5和簇ID:1以及一個樞紐節(jié)點9(連接兩個不同的簇)。

在ε∈{0.6～1},μ∈{1,2}、ε∈{0.6,0.7,0.8,0.9,1},μ=3以及ε∈{0.1～1},μ>3的范圍內(nèi),由于參數(shù)要求更加嚴苛,沒有兩個節(jié)點能滿足近似度要求,故劃分結(jié)果如圖5所示。

由實驗結(jié)果可以看出,簇的劃分受ε和μ參數(shù)的影響,該算法對于有向圖的劃分符合預期結(jié)果,并且聚類效果也相對較好。由于該算法是在小數(shù)據(jù)集上測試的,所以算法復雜度控制較好。

類似地,較復雜網(wǎng)絡(luò)的分析情況如圖6、7所示。圖6中包含32個節(jié)點、37條有向邊,取其中典型的情況進行分析。

由圖6、7可以看出,隨著參數(shù)ε和μ的增大,程序?qū)?jié)點之間的結(jié)構(gòu)相似性要求更為嚴苛,故由起初規(guī)模較大的簇結(jié)構(gòu)逐步劃分為多個規(guī)模較小的簇結(jié)構(gòu),由此也劃分出相應(yīng)的興趣愛好相同的一類群體。

2.2.2 特殊節(jié)點的分析與推廣

由圖3中可以看出,該劃分只有一個簇結(jié)構(gòu),該簇結(jié)構(gòu)以節(jié)點9為核節(jié)點,故節(jié)點9可以部分代表簇中其他節(jié)點的相關(guān)信息。這個結(jié)果對于商業(yè)投資方面很有價值。如果商家要制作并推廣一款產(chǎn)品,不需要考察太多的個體,僅僅考察節(jié)點9的興趣愛好,以此生產(chǎn)的產(chǎn)品,其受眾群體可能包含整個簇結(jié)構(gòu)的所有個體,并且會受到節(jié)點9的“帶動”作用,加速產(chǎn)品的推廣與銷售。

圖4中有個很重要的樞紐節(jié)點9,它連接著2個簇結(jié)構(gòu),那么該節(jié)點就應(yīng)該代表著兩個簇結(jié)構(gòu)的共同興趣愛好。若只能分散投放有限個廣告信息,那么這些節(jié)點將承擔著相當重要的“樞紐”作用。

圖5中的節(jié)點間連通性非常不好,這會導致信息的阻塞封閉,警示我們應(yīng)避免成為這樣的”假死”網(wǎng)絡(luò)。

2.2.3 相關(guān)算法性能評價及對比分析

本文實驗采用聚類評價標準通用指標,即準確率(Precison)、召回率(Recall)、F1值[13]。

準確率反映了分類的準確性,召回率反映了分類的完整性,兩者越大代表分類的性能越好。但是實際上兩個指標不會同時升高或者降低,會相互制約。為了能同時考察兩個指標,使用F-score公式進行計算[14]

當F-score公式的值取1時,被稱為F1值。F1值的計算方式為

F1值綜合了準確率和召回率,其值越大,說明分類效果越好。

正確率=正確劃分數(shù)/劃分數(shù)目;召回率=正確劃分數(shù)/測試數(shù)。這兩個數(shù)的取值范圍屬于0到1,該值越大,精度越好[15]。

2.2.4 相關(guān)算法對比分析

本文基于上述測試指標,采用P2PNET數(shù)據(jù)集、Flickr數(shù)據(jù)集及YouTuBe數(shù)據(jù)集進行算法準確性和有效性驗證[7,14],測試結(jié)果見表1。由表1可見,該算法在本文測試的3個數(shù)據(jù)集上的表現(xiàn)結(jié)果比文獻[7]算法更準確,分別提高0.4%、8.85%、2.4%及0.9%,在其他數(shù)據(jù)集上,3項測試值也都有顯著提升,不僅提高了有向網(wǎng)絡(luò)的劃分速度及效率,準確性也達到新的高度。

算法假設(shè)結(jié)構(gòu)簇由幾個相鄰的簇構(gòu)成,相鄰的兩個簇至少重疊m個節(jié)點,每個簇只屬于某個網(wǎng)絡(luò)簇,但不同的結(jié)構(gòu)簇可能會重疊某些節(jié)點,需要計算該節(jié)點分別對于兩個簇結(jié)構(gòu)的近似度權(quán)值,進而判斷該節(jié)點到底適合哪個簇網(wǎng)絡(luò)。這對于上述參考指標的提升有較大影響。算法通過以上步驟分析出簇結(jié)構(gòu),但在實際應(yīng)用中參考的參數(shù)不易確定,選取不同的參數(shù)值往往得到差距較大的網(wǎng)絡(luò)簇結(jié)構(gòu)。

表1 不同數(shù)據(jù)集評價指標對比示意表

3 結(jié)論

本文提出了基于結(jié)構(gòu)近似度的有向網(wǎng)絡(luò)聚類算法,不僅實現(xiàn)了對有向圖的聚類分簇,也更加準確地優(yōu)化了聚類邊界點的檢測。該算法時間復雜度相對較低,對網(wǎng)絡(luò)結(jié)構(gòu)的劃分較其他算法準確。本文算法僅考慮了簇的劃分情況,忽略了對特殊節(jié)點意義作用的分析與推廣,此外,邊界點沖突處理問題也需要進一步研究。