社交網(wǎng)絡(luò)數(shù)據(jù)動態(tài)聚類調(diào)度算法實現(xiàn)

劉玥波，張偉杰

(1. 吉林建筑科技學(xué)院計算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130114；2. 吉林建筑大學(xué)電氣與計算機(jī)學(xué)院，吉林 長春 130018)

1 引言

社會的發(fā)展使每個人都與其他人有著某種意義上的聯(lián)系，不論是現(xiàn)實生活里的鄰居關(guān)系、朋友關(guān)系，還是網(wǎng)絡(luò)上的好友關(guān)系，或者通過第三方建立起來的合作、愛好相同等間接關(guān)系，同一聯(lián)系內(nèi)的每個個體也許角色不同，但經(jīng)過不斷擴(kuò)展相關(guān)范圍，每個個體之間也有一定幾率形成不同關(guān)系，將這些關(guān)系構(gòu)建成一個網(wǎng)絡(luò)，即社交網(wǎng)絡(luò)[1]，實體就是網(wǎng)絡(luò)中的每個個體。通過分析社交網(wǎng)絡(luò)存在的聯(lián)系，可以獲取更多的有效信息，但該網(wǎng)絡(luò)通常規(guī)模較大，結(jié)構(gòu)也比較復(fù)雜，且實體之間的聯(lián)系將隨著時間的推移而不斷發(fā)生變化，因此，深入分析社交網(wǎng)絡(luò)含有的關(guān)系是一個具有挑戰(zhàn)性與現(xiàn)實意義的研究課題。

蘇葉健針對云計算光纖通信構(gòu)建了一種殘差融合型模糊C均值學(xué)習(xí)下大數(shù)據(jù)的聚類調(diào)度算法[2]，基于架構(gòu)的大數(shù)據(jù)分段特征分解模型，利用多元回歸分析法，均衡分配輸出大數(shù)據(jù)，采用模糊C均值聚類法，分類處理由結(jié)構(gòu)參數(shù)模型提取的大數(shù)據(jù)關(guān)聯(lián)特征分量，通過殘差變量的線性規(guī)劃融合調(diào)度，均衡聚類調(diào)度光纖通信大數(shù)據(jù)；王瑋琪等人為提升聚類精度與處理流數(shù)據(jù)效率，研究出一種局部網(wǎng)格動態(tài)聚類算法[3]，利用維度半徑概念，完成增量動態(tài)網(wǎng)格劃分，經(jīng)過判定簇邊界，根據(jù)稀疏網(wǎng)格與相鄰密集網(wǎng)格之間的質(zhì)心間距，劃分稀疏網(wǎng)格到對應(yīng)網(wǎng)格簇內(nèi)，通過迭代操作防止誤刪簇邊界，提升聚類精度。

聚類分析是數(shù)據(jù)挖掘領(lǐng)域的重要數(shù)據(jù)分析方法之一，被廣泛應(yīng)用于文本分析、生物信息等不同領(lǐng)域中，所得的聚類結(jié)果質(zhì)量將對人們的數(shù)據(jù)認(rèn)知產(chǎn)生直接影響，其目的就是將某個數(shù)據(jù)目標(biāo)集合分類為簇，令簇中的數(shù)據(jù)目標(biāo)具有較高的相似度，各簇之間的數(shù)據(jù)目標(biāo)具有較高的差異性。但是，若聚類過程中無法確定簇數(shù)，則會導(dǎo)致聚類偏差，而大規(guī)模的社交網(wǎng)絡(luò)一般不是強連通圖，也無法根據(jù)先驗知識驗證聚類調(diào)度結(jié)果，網(wǎng)絡(luò)中存在的孤立團(tuán)結(jié)構(gòu)節(jié)點較少，極易在聚類調(diào)度階段中被忽略，而且數(shù)據(jù)的抗干擾性與自適應(yīng)傳輸控制性都比較差。

因此，本文設(shè)計以社交網(wǎng)絡(luò)數(shù)據(jù)為研究目標(biāo)，設(shè)計一種社交網(wǎng)絡(luò)數(shù)據(jù)動態(tài)聚類調(diào)度算法。引入標(biāo)簽歸屬率指標(biāo)，避免標(biāo)簽更新階段信息丟失；通過更新降序的密度-距離值，將標(biāo)簽優(yōu)先分配至重要節(jié)點，抑制其余節(jié)點產(chǎn)生的影響，提升社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)聚類準(zhǔn)確度；提取社交網(wǎng)絡(luò)數(shù)據(jù)的關(guān)聯(lián)特征，提升數(shù)據(jù)均衡調(diào)度性能。

2 社交網(wǎng)絡(luò)數(shù)據(jù)動態(tài)聚類算法構(gòu)建

首先將動態(tài)聚類算法進(jìn)行劃分，將其分為社區(qū)中心點識別與多標(biāo)簽傳播兩個階段，這樣做的目的主要有2個方面。首先可以防止聚類過程中發(fā)生信息丟失，其次能夠優(yōu)先分配標(biāo)簽給重要節(jié)點，實現(xiàn)降低剩余節(jié)點影響的作用，進(jìn)而使社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)聚類效果更加理想。

2.1 社區(qū)中心點識別

已知社交網(wǎng)絡(luò)中存在任意節(jié)點i，求解該節(jié)點密度值ρi的計算公式如下所示

ρi=ξi+ηi

(1)

(2)

式中，節(jié)點i的度數(shù)為ηi，該節(jié)點所有鄰域節(jié)點的度數(shù)總和用ξi表示。

利用式(1)計算社交網(wǎng)絡(luò)中所有節(jié)點的密度值后，以此為依據(jù)，求解所有節(jié)點的距離值δ，以節(jié)點i為例，該節(jié)點的距離值δi的計算公式如下所示

(3)

式中，節(jié)點i與j的圖論[4]距離為dij節(jié)點i的密度值ρi小于節(jié)點j的密度值ρj。

(4)

(5)

(6)

式中，所有節(jié)點的密度值均值與距離值均值分別是μρ與μδ，全部節(jié)點的密度值標(biāo)準(zhǔn)差與距離值標(biāo)準(zhǔn)差分別是σρ與σδ。

通過切比雪夫不等式[6]提取，得到所有節(jié)點中密度-距離γ*的較大值，則社區(qū)中心點就是與較大值對應(yīng)的社交網(wǎng)絡(luò)節(jié)點。

2.2 多標(biāo)簽傳播

遍歷社交網(wǎng)絡(luò)的全部節(jié)點之后，找到只直接與一個社區(qū)中心點連接的節(jié)點，并為其分配與該社區(qū)中心點相同的標(biāo)簽，構(gòu)建種子區(qū)域，利用下列計算公式求取所有節(jié)點的標(biāo)簽覆蓋率ψ

(7)

式中，節(jié)點i的鄰域節(jié)點個數(shù)為Ni，其中，已被分配標(biāo)簽的節(jié)點個數(shù)為ni，此類節(jié)點的標(biāo)簽覆蓋率取值為0。

按順序選取標(biāo)簽覆蓋率最大的節(jié)點，完成標(biāo)簽更新操作，基于鄰域節(jié)點標(biāo)簽的發(fā)生頻率，將最大頻率標(biāo)簽分配給該節(jié)點，對其鄰域節(jié)點標(biāo)簽覆蓋率重新求解，對求出的解引入多標(biāo)簽傳播過程中，實現(xiàn)社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)聚類。

為避免標(biāo)簽更新階段信息丟失，引入標(biāo)簽歸屬率指標(biāo)，構(gòu)建基于節(jié)點密度-距離值γ*的多標(biāo)簽傳播過程，具體步驟描述如下：

1)降序排列節(jié)點序列N={n1，n2，…，nm}的密度-距離值γ*，該序列的節(jié)點數(shù)量是m，得到降序節(jié)點序列T={T1，T2，…，Tm}；

2)對標(biāo)簽結(jié)果集合L=[0，0，…，0]進(jìn)行初始化，設(shè)定所有節(jié)點的初始標(biāo)簽為{(l1，0)，(l2，0)，…，(lk，0)}，其中，|L|=m，識別得到的社區(qū)中心點數(shù)量是k；

3)把不同標(biāo)簽分配給識別的k個社區(qū)中心點集合C={C1，C2，…，Ck}，令中心點Ci的標(biāo)簽li取值1，同時更新LCi=i；

4)遍歷節(jié)點集合N，若節(jié)點ni為非社區(qū)中心點，且僅與中心點Cj直接連接，兩點間的圖論距離dij取值是1，則令節(jié)點ni的標(biāo)簽lj為1，更新Lni=j；

5)遍歷降序節(jié)點序列T，關(guān)于節(jié)點Ti，若LTi=0，則采用下列計算公式完成對節(jié)點Ti已有標(biāo)簽的更新

(8)

式中，節(jié)點Ti的鄰域節(jié)點是Tj，該鄰域節(jié)點的第k個標(biāo)簽項為lTj，k，節(jié)點i與節(jié)點j的結(jié)構(gòu)相似度[7]用simTi，Tj表示，表達(dá)式如下所示

simTi，Tj=|N(i)∩N(j)|

(9)

式中，與節(jié)點i的圖論距離是1的節(jié)點和節(jié)點i自身用N(i)表示，N(i)含有的節(jié)點個數(shù)為|N(i)|。

完成節(jié)點Ti的標(biāo)簽更新計算后，歸一化處理標(biāo)簽，令標(biāo)簽li滿足下列表達(dá)式

(10)

根據(jù)上式得到與最大標(biāo)簽項對應(yīng)的標(biāo)簽ml，完成LTi=ml更新，結(jié)合標(biāo)簽特性，標(biāo)簽ml的表達(dá)式如下所示

ml=arg max(li)

(11)

6)基于所有標(biāo)簽結(jié)果集合L，把含有相同數(shù)值項的節(jié)點劃分到同一社區(qū)，以此對標(biāo)簽進(jìn)行系統(tǒng)分類，獲取社交網(wǎng)絡(luò)的k個社區(qū)。

更新降序的密度-距離值，能夠?qū)?biāo)簽優(yōu)先分配至重要節(jié)點，抑制其余節(jié)點產(chǎn)生的影響，提升社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)聚類準(zhǔn)確度，達(dá)到標(biāo)簽精準(zhǔn)定位的效果，進(jìn)而實現(xiàn)多標(biāo)簽準(zhǔn)確傳播。

3 社交網(wǎng)絡(luò)數(shù)據(jù)均衡調(diào)度算法設(shè)計

在完成社交網(wǎng)絡(luò)數(shù)據(jù)動態(tài)聚類算法構(gòu)建的基礎(chǔ)上，基于動態(tài)聚類的社交網(wǎng)絡(luò)數(shù)據(jù)，采用下列計算公式解得數(shù)據(jù)的動態(tài)遷移負(fù)載特征量

Φ(ω)=E[eφωX]

(12)

式中，數(shù)據(jù)傳輸調(diào)制系數(shù)用ω表示。

根據(jù)提取的數(shù)據(jù)正相關(guān)特征量，計算動態(tài)遷移[8]狀態(tài)下社交網(wǎng)絡(luò)數(shù)據(jù)中第φ=0，1，…，M個采樣點的輸出，運算公式如下所示

x(τ)eφπτ2cot α

(13)

式中，有限長的離散社交網(wǎng)絡(luò)數(shù)據(jù)碼元序列為x(τ)，數(shù)據(jù)輸出統(tǒng)計峰值為N=(Δx)2。

由此推導(dǎo)出下式描述的社交網(wǎng)絡(luò)數(shù)據(jù)通頻帶特征分布形式

(14)

(15)

當(dāng)社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行多任務(wù)傳輸時，需通過能量均衡控制策略獲取數(shù)據(jù)均衡調(diào)度輸出的耦合特征量，表達(dá)式如下所示

(16)

根據(jù)上列各式得到下列調(diào)度輸出的迭代函數(shù)方程，實現(xiàn)社交網(wǎng)絡(luò)數(shù)據(jù)的均衡調(diào)度

(17)

式中，社交網(wǎng)絡(luò)數(shù)據(jù)的初始負(fù)載為uMCMA。

經(jīng)過上述算法流程，提取社交網(wǎng)絡(luò)數(shù)據(jù)的關(guān)聯(lián)特征，實現(xiàn)數(shù)據(jù)均衡調(diào)度。

4 動態(tài)聚類調(diào)度算法仿真

4.1 實驗用數(shù)據(jù)集與指標(biāo)設(shè)定

為驗證所提算法的有效性，實驗選擇Bochs平臺進(jìn)行仿真。分別選取兩個真實數(shù)據(jù)集與兩個人工數(shù)據(jù)集作為算法的處理對象，兩類別數(shù)據(jù)集的具體情況分別如下表1、表2所示。

表1 真實數(shù)據(jù)集統(tǒng)計表

表2 人工數(shù)據(jù)集統(tǒng)計表

分別采用準(zhǔn)確率Acc、標(biāo)準(zhǔn)互信息[9]NMI、模塊度[10]Θ以及蘭德指數(shù)ARI指標(biāo)來綜合評價算法效果，已獲得更加可靠度評價結(jié)果。各指標(biāo)界定公式分別如下所示

(18)

式里，第i個社區(qū)中被正確識別的節(jié)點個數(shù)為ai，社區(qū)個數(shù)為λ，節(jié)點數(shù)量為m。

(19)

式中，在算法仿真結(jié)果與實際社區(qū)情況里均不是同一社區(qū)的節(jié)點對個數(shù)為ε00，屬于同一社區(qū)的節(jié)點對個數(shù)為ε11，在仿真過程中不是同一社區(qū)但是在實際社區(qū)里為同一社區(qū)的節(jié)點對個數(shù)為ε01，在仿真過程中是同一社區(qū)但是在實際社區(qū)里不是同一社區(qū)的節(jié)點對個數(shù)為ε10。

(20)

式中，混淆矩陣為Ξ，同屬于社區(qū)A與B的節(jié)點個數(shù)分別為、，邊個數(shù)分別為a、b。

(21)

式中，鄰域社區(qū)所含項為Aij。

通過對比文獻(xiàn)[2]、[3]方法與本文算法的數(shù)據(jù)集處理結(jié)果，驗證算法的有效性與可行性。

4.2 動態(tài)聚類效果分析

下列各表所示分別為四個數(shù)據(jù)集的各算法實驗結(jié)果。

表3 Karate數(shù)據(jù)集的各算法實驗結(jié)果統(tǒng)計表

表4 Football數(shù)據(jù)集的各算法實驗結(jié)果統(tǒng)計表

表5 LFR1數(shù)據(jù)集的各算法實驗結(jié)果統(tǒng)計表

表6 LFR2數(shù)據(jù)集的各算法實驗結(jié)果統(tǒng)計表

與文獻(xiàn)[2]、[3]方法的實驗數(shù)據(jù)對比后，發(fā)現(xiàn)本文算法因識別了社區(qū)中心點，完成了多標(biāo)簽傳輸階段，所有指標(biāo)數(shù)據(jù)都存在顯著的優(yōu)越性；從數(shù)據(jù)集角度來說，本文算法在處理Karate數(shù)據(jù)集與LFR2數(shù)據(jù)集時，大部分指標(biāo)仍符合應(yīng)用需求，針對Football數(shù)據(jù)集與LFR1數(shù)據(jù)集，所有指標(biāo)都能夠滿足實際要求。

4.3 均衡調(diào)度效果分析

基于多徑信道分布的社交網(wǎng)絡(luò)數(shù)據(jù)，采用本文算法完成數(shù)據(jù)均衡調(diào)度，數(shù)據(jù)輸出結(jié)果如圖1所示。

圖1 社交網(wǎng)絡(luò)數(shù)據(jù)調(diào)度輸出結(jié)果示意圖

分析圖1后可知，本文算法因提取出了社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)遷移負(fù)載特征量，故輸出比特序列傳輸偏差的收斂值可以快速為0，使數(shù)據(jù)傳輸?shù)木庑缘玫酱蠓忍嵘?/p>

下圖2所示為各算法均衡調(diào)度數(shù)據(jù)的誤碼率對比曲線。

圖2 各算法數(shù)據(jù)輸出誤碼率比較示意圖

通過圖2中的曲線走勢可以看出，由于本文方法通過能量均衡控制策略，獲取了數(shù)據(jù)均衡調(diào)度輸出的耦合特征量，所以，較其它兩種方法具有更低的輸出誤碼率。

5 結(jié)論

社交網(wǎng)絡(luò)中各實體之間存在相互聯(lián)系，因其具有的規(guī)模大、結(jié)構(gòu)復(fù)雜等特點，大幅度增加了網(wǎng)絡(luò)數(shù)據(jù)的處理難度，為此，本文構(gòu)建了一種社交網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)聚類調(diào)度算法，針對Karate數(shù)據(jù)集、Football數(shù)據(jù)集、LFR1數(shù)據(jù)集和LFR2數(shù)據(jù)集，在準(zhǔn)確率、標(biāo)準(zhǔn)互信息、模塊度以及蘭德指數(shù)均取得良好成績，準(zhǔn)確率最高可達(dá)0.954，標(biāo)準(zhǔn)互信息可達(dá)0.972，模塊度可達(dá)0.827，蘭德指數(shù)0.959。

另外，研究雖然取得了一定的研究成果，但同時也存在著諸多不足，需要在今后的工作中對以下方面加以改進(jìn)、完善：應(yīng)將帶權(quán)的社交網(wǎng)絡(luò)作為下一步聚類對象，展開深入分析；應(yīng)繼續(xù)探索更好的聚類準(zhǔn)確度評價指標(biāo)；應(yīng)在后續(xù)的實驗中，采集更多的真實數(shù)據(jù)集來提升算法的可靠性。