社交網絡數據動態聚類調度算法實現

劉玥波，張偉杰

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

1 引言

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

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

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

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

2 社交網絡數據動態聚類算法構建

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

2.1 社區中心點識別

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

ρi=ξi+ηi

(1)

(2)

式中，節點i的度數為ηi，該節點所有鄰域節點的度數總和用ξi表示。

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

(3)

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

(4)

(5)

(6)

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

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

2.2 多標簽傳播

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

(7)

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

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

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

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

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

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

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

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

(8)

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

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

(9)

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

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

(10)

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

ml=arg max(li)

(11)

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

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

3 社交網絡數據均衡調度算法設計

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

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

(12)

式中，數據傳輸調制系數用ω表示。

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

x(τ)eφπτ2cot α

(13)

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

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

(14)

(15)

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

(16)

根據上列各式得到下列調度輸出的迭代函數方程，實現社交網絡數據的均衡調度

(17)

式中，社交網絡數據的初始負載為uMCMA。

經過上述算法流程，提取社交網絡數據的關聯特征，實現數據均衡調度。

4 動態聚類調度算法仿真

4.1 實驗用數據集與指標設定

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

表1 真實數據集統計表

表2 人工數據集統計表

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

(18)

式里，第i個社區中被正確識別的節點個數為ai，社區個數為λ，節點數量為m。

(19)

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

(20)

式中，混淆矩陣為Ξ，同屬于社區A與B的節點個數分別為、，邊個數分別為a、b。

(21)

式中，鄰域社區所含項為Aij。

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

4.2 動態聚類效果分析

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

表3 Karate數據集的各算法實驗結果統計表

表4 Football數據集的各算法實驗結果統計表

表5 LFR1數據集的各算法實驗結果統計表

表6 LFR2數據集的各算法實驗結果統計表

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

4.3 均衡調度效果分析

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

圖1 社交網絡數據調度輸出結果示意圖

分析圖1后可知，本文算法因提取出了社交網絡數據的動態遷移負載特征量，故輸出比特序列傳輸偏差的收斂值可以快速為0，使數據傳輸的均衡性得到大幅度提升。

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

圖2 各算法數據輸出誤碼率比較示意圖

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

5 結論

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

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