劉玥波，張偉杰

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

1 引言

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

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

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

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

2 社交網絡數(shù)據(jù)動態(tài)聚類算法構建

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

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

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

ρi=ξi+ηi

(1)

(2)

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

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

(3)

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

(4)

(5)

(6)

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

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

2.2 多標簽傳播

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

(7)

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

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

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

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

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

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

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

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

(8)

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

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

(9)

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

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

(10)

根據(jù)上式得到與最大標簽項對應的標簽ml，完成LTi=ml更新，結合標簽特性，標簽ml的表達式如下所示

ml=arg max(li)

(11)

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

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

3 社交網絡數(shù)據(jù)均衡調度算法設計

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

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

(12)

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

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

x(τ)eφπτ2cot α

(13)

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

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

(14)

(15)

當社交網絡數(shù)據(jù)進行多任務傳輸時，需通過能量均衡控制策略獲取數(shù)據(jù)均衡調度輸出的耦合特征量，表達式如下所示

(16)

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

(17)

式中，社交網絡數(shù)據(jù)的初始負載為uMCMA。

經過上述算法流程，提取社交網絡數(shù)據(jù)的關聯(lián)特征，實現(xiàn)數(shù)據(jù)均衡調度。

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

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

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

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

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

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

(18)

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

(19)

式中，在算法仿真結果與實際社區(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。

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

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

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

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

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

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

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

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

4.3 均衡調度效果分析

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

圖1 社交網絡數(shù)據(jù)調度輸出結果示意圖

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

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

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

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

5 結論

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

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