基于空間尺度粗粒化的異常檢測方法

摘 要：目前，大部分基于鏈路預測對社會網絡進行異常檢測的研究中，缺乏對異常節點演化影響的分析，且受社會網絡規模以及復雜度的限制，檢測效率普遍不高。針對上述問題，提出了一種基于空間尺度粗粒化和異常節點加權機制的異常檢測方法。首先利用凝聚型社區發現算法Louvain對社會網絡進行粗粒化得到簡化網絡，然后在簡化網絡的演化過程中識別有異常演化行為的節點，并將其異常演化過程量化，引入異常節點加權機制到鏈路預測方法中進行異常檢測。在真實社會網絡數據集VAST、Email-EU（dept1和dept2）以及Enron上，與基于LinkEvent的不同調整策略算法和NESO_ED方法進行對比。結果表明，該方法可以兼顧異常檢測的穩定性和敏感性，能夠更合理地描述網絡演化過程，得到更好的異常檢測效果。

關鍵詞：異常檢測；節點演化；鏈路預測；網絡簡化；復雜網絡

中圖分類號：TP181 文獻標志碼：A

文章編號：1001-3695（2022）07-023-2068-08

doi：10.19734/j.issn.1001-3695.2021.11.0649

基金項目：國家自然科學基金資助項目（62072154）

作者簡介：富坤（1979-），女（通信作者），遼寧遼陽人，副教授，碩導，博士，主要研究方向為社會網絡分析、網絡表示學習（fukun@hebut.edu.cn）；劉琪（1996-），河北張家口人，碩士研究生，主要研究方向為異常檢測、社會網絡分析；禚佳明（1996-），山東青島人，碩士研究生，主要研究方向為網絡表示學習、機器學習；李佳寧（1996-），男，河北唐山人，碩士研究生，主要研究方向為lncRNA相關計算模型研究；郭云朋（1991-），男，河北邢臺人，碩士研究生，主要研究方向為網絡表示學習、深度學習.

Abnormal detection method based on spatial scale coarse-grained

Fu Kun^1，2?，Liu Qi^1，2，Zhuo Jiaming^1，2，Li Jianing^1，2，Guo Yunpeng^1，2

（1.College of Artificial Intelligence amp; Data Science，Hebei University of Technology ，Tianjin 300401，China；2.Key Laboratory of Big Data Computing，Tianjin 300401，China）

Abstract：At present，most link-prediction based models on anomaly detection in social networks lack the ability to consider the influence of abnormal nodes evolution.With the limitation of network scale and complexity，the detection efficiency of traditional models is generally low.To address these issues，this paper proposed an anomaly detection method based on the spatial scale coarse granulation and weighting mechanism on abnormal nodes.Firstly，the method introduced a cohesive community discovery algorithm，Louvain algorithm，to coarsely granulate process to streamline network.Subsequently，it identified abnormal nodes with different evolution behaviors in the processed network following the quantification of abnormal evolution process.Finally，it applied the link prediction method combined with a weighting mechanism of abnormal nodes for final abnormal detection.Compared with different LinkEvent-based strategy adjustment algorithms and NESO_ED method on three real social network data sets VAST，Email-EU（dept1 and dept2） and Enron，the proposed method outperforms other state-of-the-art methods，can take into account both stability and sensitivity on anomaly detection tasks and more reasonably describe the network evolution process.

Key words：abnormal detection；node evolution；link prediction；network simplification；complex network

0 引言

隨著近年網絡技術的不斷發展和社交平臺的廣泛應用，人們在網絡上越發頻繁的活動產生了大量數據，不同領域的不同種類的數據都可以被表示為復雜網絡，如社交網絡、通信網絡、蛋白質網絡等^［1］。復雜網絡的網絡拓撲結構一般都高度復雜，社交網絡就是復雜網絡的一個典型例子。異常事件是由復雜網絡中的個體或團體的異常演化行為所引起的，具有持續性和擴散性，會對網絡正常演化造成影響。通過異常檢測來預測異常事件發生及其發展趨勢，能夠對異常作出快速反映，以防造成更大損失，在社會安全方面能為政府或企業合理監控網絡輿論、干預敏感話題等提供理論支撐^［2］。

網絡演化規律分析是社會網絡異常檢測的重要方法基礎，通過追蹤不同階段社會網絡的變化，分析社會網絡的增長、衰弱、傳播等演化行為來描述網絡演化的規律，并以此預測網絡結構變化。鏈路預測是研究復雜網絡的重要工具^［3］，現已有研究證明鏈路預測與網絡演化規律具有較大的關聯^［4］，可以通過鏈路預測進行網絡演化分析。目前較為常見的鏈路預測方法包括基于網絡拓撲結構的方法^［5］、基于最大似然的方法^［6］和基于機器學習的方法^［7］等，其中基于網絡拓撲結構的方法計算簡單且高效，應用最為廣泛。胡文斌等人^［8］提出了一種基于鏈路預測的社會網絡異常檢測方法，采取單一相似性指標檢測。Wang等人^［9］提出了面向節點演化波動的異常檢測方法，提高了異常檢測的精確性和敏感性。

由于社會網絡具有復雜性，在網絡演化分析過程中通常需要對規模較大的社會網絡進行粗粒化來分析效率。網絡演化行為受網絡空間結構的影響很大，所以網絡粗粒化的研究方向主要是網絡空間結構的粗粒化。網絡中的社區結構是研究網絡拓撲的基礎^［10］，對網絡進行基于空間尺度的粗粒化，主要是基于網絡重整化和社區發現將某些相似的網絡團體合并。基于網絡重整化思想，Kim^［11］提出了一種能夠保持網絡無標度屬性的網絡粗粒化方法；Song等人^［12］指出網絡結構具有自相似性，并對比研究了粗粒化前后的網絡性質。基于分層社區結構的思想，Ahn等人^［13］提出了一種基于層次聚類的社區發現方法，將社區定義為連邊組而不是節點組，調和了社區重疊性和分層結構的矛盾；Chen等人^［14］經過對W-S模型、B-A模型等進行研究，得出了網絡的社區結構越明顯，基于空間尺度進行網絡粗粒化的效果越好的結論；Blondel等人^［15］提出的基于模塊度優化的Louvain算法以優化整體網絡的模塊度為目標函數，通過迭代進行社區發現，具有很高的效率，適用于大規模網絡的社區發現。

社會網絡的異常行為通常是網絡中個體演化行為的綜合表現，節點的演化機制通常會受網絡波動的影響而發生改變，使節點出現異常演化行為，從而導致異常事件。現已有針對社會網絡中節點重要性的研究^［16］、針對節點影響力的研究^［17］、結合節點相似性和網絡結構的鏈路預測研究^［18］，其對異常檢測的研究方法主要都是監測宏觀性能的變化，分析整體網絡的演化，缺乏在微觀層面對節點演化的分析，沒有考慮異常節點對網絡演化的影響。此外，由于受網絡規模和網絡復雜結構的限制較大，目前大部分的異常檢測方法運行效率不高，敏感性也有待提升。

基于以上問題，本文提出一種基于空間尺度粗粒化的異常檢測方法（abnormal detection method based on spatial scale coarse-grained，SCAD），主要包括基于空間尺度的網絡粗粒化算法（network coarse-grained algorithm based on spatial scale，SC_NC）以及引入異常節點加權機制的網絡異常檢測算法（abnormal detection method based on weighted abnormal node，WAN_AD）。通過引入社區發現算法Louvain，在不破壞社會網絡拓撲結構的情況下簡化網絡結構；在分析網絡演化過程中識別異常節點并量化異常節點的演化。最后在異常檢測過程中強化異常節點的影響力，以提高異常檢測的準確率和效率。

1 相關工作

本文異常檢測的研究對象為社會網絡，粗粒化算法引用Louvain算法。本章介紹社會網絡預備知識、Louvain算法的基本流程以及相關概念。

1.1 社會網絡相關定義及描述

進行異常檢測的網絡對象一般都是動態網絡，即帶有時間標簽的時序網絡，社會網絡連續時間段的網絡快照可以表示為G=（g¹，g²，…，gn），t時刻的網絡快照表示為gt=（V t，Et），其中Vt表示網絡中t時刻節點的集合，Et表示t時刻邊的集合。

通過鏈路預測進行異常檢測的關鍵步驟是計算節點的相似性，需要計算同一節點在不同時刻的相似性值，但在網絡演化過程中網絡是不斷變化的，有的節點并不會一直存在于網絡中，也可能會有新節點在某一時刻出現，為了調節這類節點對分析網絡演化帶來的影響引入虛擬節點^［8］，在每個時刻的網絡中加入一個與圖中所有節點都存在邊的節點。加入虛擬節點后的相似性指標計算如表1所示。k（vti）表示t時刻節點i的度數，Γ（vti）表示t時刻節點i的所有鄰居節點的集合。

1.2 Louvain及相關定義

社區是指網絡中的一組節點，社區內部的聯系要比和外界的聯系更加緊密，檢測出社會網絡中的社區對社交網絡的研究很重要^［19］。模塊度是評估社區網絡劃分好壞的度量方法^［20］，通過比較社區內部和外部的緊密程度來衡量劃分的優劣。Louvain算法是基于模塊度通過不斷迭代進行社區發現，當網絡整體模塊度不再增大時，便自動停止迭代，得到粗粒化網絡。模塊度的計算如式（1）所示，其含義是社區c內部的連邊數與社區c與外部的連邊差值。

其中：m表示初始網絡的邊數i、j是網絡中的任意兩個節點；Aij表示i、j之間邊的權重；ki是節點i的度；δ（ci，cj）的含義是判斷i、j是否屬于同一社區，若是則δ（ci，cj）=1，反之δ（ci，cj）=0。

模塊度增益ΔQ表示改變節點所屬社區引起的模塊度變化。將節點i移動到社區c后產生的模塊度增益計算公式為

其中：ki，in為節點i在社區c內的度數；Σin為社區c中的邊數；Σtot為社區c內節點的度之和。

2 SCAD方法

本文設計的SCAD方法是采用鏈路預測技術，從節點演化角度定量評估網絡演化過程，計算相鄰時段節點的相似性值，得到相鄰時段網絡相似性值并計算網絡演化的波動性，通過設定的閾值來判斷異常發生的時段。

2.1 整體框架

SCAD方法主要包括SC_NC和WAN_AD算法，SCAD方法的輸入是某個時間區間內的社會網絡圖序列，輸出是社會網絡異常發生時段，算法整體框架如圖1所示，具體步驟如下：

a）輸入一段時間區間的社會網絡快照；

b）執行SC_NC算法，對原始圖序列中的網絡快照進行粗粒化處理，獲得每階段簡化后的網絡；

c）執行WAN_AD算法，計算得到時序網絡中具有異常演化行為的節點，獲得每階段中的異常節點集，在粗粒化網絡中通過采用異常節點加權機制計算網絡相似值和波動值，計算圖相似性和波動值，針對波動值設定閾值，當波動值大于閾值時意味著此階段是異常演化階段；

d）輸出社會網絡中的異常時段。

2.2 SC_NC算法

在對社會網絡的研究過程中，由于數據量不斷增加以及網絡結構的復雜化，對網絡進行粗粒化處理十分重要。網絡粗粒化是以保持網絡結構相似性為前提，通過融合圖中有某些相同性質的節點，減少冗余結構信息來達到簡化網絡的目的。

SC_NC算法是基于Louvain算法，在不破壞網絡拓撲結構的前提下根據社區發現對網絡進行簡化，能夠快速完成在不同尺度下對大規模網絡的社區劃分，根據實際需要的簡化程度選取對應的尺度。當網絡整體模塊度不再增大時，便自動結束迭代，得到粗粒化網絡。算法可分為兩個階段：

a）模塊劃分。初始網絡中有n個節點，認為每個節點單獨屬于一個社區，此時網絡中的節點個數便是社區個數。然后令節點i（i=1，2，…，n）不再屬于本身的社區，而是依次被劃分到它的鄰居節點j的社區，這就使網絡出現了模塊度的變動，計算每次劃分后產生的網絡模塊度增益ΔQ，最后將節點i劃分到使ΔQ最大的社區中，若沒有增益則不改變i所屬的社區。當網絡中所有節點所屬的社區都不再發生變化時，停止迭代。

本文的研究對象是無向無權圖，圖中所有的邊權值默認為1。基于無權圖對式（1）進行簡化，計算公式為

在模塊劃分過程中會產生模塊度增益，模塊度增益的正負表示模塊度是否增加，基于無權圖對式（2）進行簡化，計算公式為

b）將劃分后的社區分別融合為一個節點，重新構造一個新網絡，其中節點間的邊的權值由原先兩個社區之間的節點邊數累加得到。則實現了一次網絡粗粒化。

算法1 SC_NC

輸入：原始網絡G（V，E）。

輸出：第k層粗粒化網絡GCK（V，E）。

C={1，2，…，n} //將每個節點劃分為一個社區

do

for i∈C

Q=0，ΔQ=0，best_ΔQ=0，new_ΔQ=0

get_Neighbor（i） //得到節點i所有鄰居社區集合

for j∈Neighbor（i）

add（i，j） //將節點i加入j的社區中

根據式（4）計算當前模塊度增益new_ΔQ

if new_ΔQgt;best_ΔQ

best_i←j //best_i是節點i的最佳鄰居節點

best_ΔQ←new_ΔQ

remove（i，j） //將i恢復到原社區中

end

if best_ΔQgt;0：

add（i，best_i） //劃分i到使網絡模塊度增益最大的社區

ΔQ←ΔQ+best_ΔQ

end

while new_ΔQgt;ΔQ //網絡整體模塊度達到最大，結束算法

saveup GCK（V，E）

end

2.3 WAN_AD異常檢測算法

WAN_AD算法區別于傳統面向節點的網絡演化波動性檢測，在異常檢測算法中引入異常節點加權機制，增強了異常節點對網絡演化的影響，算法分為識別異常演化的節點和異常檢測兩個步驟。

2.3.1 檢測異常節點

通過對比節點演化相鄰階段的變化程度，判定該節點是否出現了異常演化，若是則屬于異常節點。異常演化是指現階段的演化方向與之前出現了大的偏差，算法通過鏈路預測分析網絡演化過程，對社會網絡中邊生成和丟失兩種情況進行判斷。

通過節點相似性計算公式對邊的生成和丟失兩種演化情況進行量化，邊生成指數eglp（i，t）表示在t時刻基于相似性指標lp，節點i邊生成情況的量化指數；邊丟失指數enlp（i，t）表示在t時刻基于相似性指標lp，節點i邊丟失情況的量化指數。計算公式分別如式（5）（6）所示。

對于在（t-1，t）時段網絡演化過程中的任意異常節點i，i在t時刻新生成的邊集合為EG（i，t），在t時刻丟失的邊集合為ER（i，t），EC（i，t）表示在t時刻存在的邊集合，EN（i，t）表示在t時刻不存在的邊集合。式（5）中：N表示EG（i，t）與EN（i，t）集合內的邊數量的乘積；n1表示EG（i，t）集合中相似性得分大于EN（i，t）的次數；n2表示得分相等的次數。式（6）中：N表示EC（i，t）和ER（i，t）集合內邊的數量的乘積；n1表示EC（i，t）集合中相似性得分大于ER（i，t）的次數；n2表示得分相等的次數。鏈路預測通過計算節點的相似性值來判斷邊生成的可能性，節點的相似性值越大，它們之間越可能產生新邊。在網絡演化過程中，可以認為新生成的邊與目前不存在的邊相比，邊生成的可能性更大，所以EG（i，t）中邊的節點相似性值應大于EN（i，t）中邊的節點相似性值；同理，目前存在的邊與已經丟失的邊相比，邊生成的可能性更大，即EC（i，t）中邊的節點相似性值應大于ER（i，t）中邊的節點相似性值。

社會網絡中節點的演化機制具有復雜性，演化方向具有多樣性，很難通過基于單一指標的鏈路預測算法進行準確預測^［21］。通過將多個相似性同時運用于算法中構造一個行為向量，可以更貼近社會網絡的真實演化過程。構造行為向量，首先需要建立一個具有m個相似性指標的鏈路預測相似性指標集LPI=（lp1，lp2，…，lpm）；然后根據eglp（i，t）和enlp（i，t）構造節點行為向量b_vec（i，t），表示節點i在t時刻的演化情形，其構造過程如式（7）所示。

通過計算相鄰時段的節點行為向量的余弦相似性值，可以表示節點演化在相鄰時段的變化程度，向量相似度越大，節點演化的變化程度越小；向量相似度越小，節點演化的變化程度越大。向量的余弦相似性值是［0，1］，可以認為當余弦相似性值大于0.5時，節點行為向量不相似，從而檢測該節點是異常節點，反之則認為該節點是正常演化的節點。向量的余弦相似性值計算公式為

2.3.2 異常檢測

識別出異常節點后，根據異常節點對網絡演化的影響重新計算節點相似性，若是異常節點則節點的相似性值要乘以權重因子ω，ω用來控制異常節點對網絡演化的影響。通過分析式（9）～（11）可知，ω值過大會導致異常節點對網絡演化的波動影響過于微弱，過小則會過度影響網絡演化的波動，不利于客觀分析網絡演化過程。節點相似性的計算公式為

所有相鄰時段的節點相似性計算完成后，取每個階段全部節點的節點相似性值的累加平均值作為網絡快照之間的圖相似性。計算公式為

網絡波動性表示為圖相似性的倒數，圖相似性越高，說明網絡波動性越小，計算公式為

用各階段網絡波動性的集合來表示網絡演化序列，如式（12）所示。

通過比較網絡波動值與閾值T來判斷網絡演化階段是否為異常發生時段，若波動值超過T則表示該階段發生異常。不同社會網絡的網絡結構存在較大差異，導致網絡演化波動值無法統一比較，所以將實驗結果經過正則化處理后，再與閾值比較。人為設定閾值T，其取值一般為［0.5，1）。閾值過低可能會將網絡正常演化也判定為異常演化，導致檢測敏感性過高，閾值過高情況則相反，閾值具體設定應依據具體實驗分析設定為適中值。

算法2 WAN_AD

輸入：粗粒化網絡GC（V，E）；閾值T；異常節點權重因子ω。

輸出：網絡異常演化發生時段Graph_Ab。

for i∈V

for t=1 to n-1

通過式（5）計算邊生成指數eglp（i，t）

通過式（6）計算邊丟失指數erlp（i，t）

通過式（7）計算節點行為向量b_vec（i，t）

end

for k=1 to n-2

通過式（8）計算節點行為向量的余弦相似性值

if s_vec（i，k，k+1）gt;0.5 then

i→Ab（k，k+1） //識別出（k，k+1）時段的異常節點

end

end

for t=1 to n-1

for i∈Vt

通過式（9）計算節點相似性S′（vti，v^t+1i）

end

通過式（10）計算網絡相似性S（gt，g^t+1）

通過式（11）計算網絡波動性D（g^t+1|gt）

if D（g^t+1|gt）gt;T then

t→Graph_Ab //檢測網絡異常演化發生時段

end

end

3 實驗結果與分析

本文選取真實的無向時序社會網絡數據集VAST^［22］和EmailEU^［23］兩個部門的數據dept1、dept2以及Enron^［24］郵件數據進行實驗，并在3.2節從八個方面進行了實驗結果分析。

3.1 數據集

VAST是由400人在10天內的通話數據組成的電話通信社交網絡，來自IEEE VAST 2008公開競賽項目，按天劃分時間片，將每天的數據表示成一張網絡快照，VAST網絡共包含10張網絡快照。EmailEU是由一個歐洲大型研究機構的E-mail數據生成的數據集，共擁有1 005個節點，時間總跨度為18個月，dept1和dept2是其中兩個部門的數據集，分別有320和172個節點，按月劃分時間片，每月的通信數據形成一張網絡快照，兩個數據集都有18張網絡快照。Enron數據集是Enron公司經歷破產后公布在網上的郵件數據，時間跨度為2002年1月至2002年3月，數據集中共包含153個郵件地址，在整個時段中有多個異常事件發生，本文將最終的公司破產視做異常事件，按周劃分時間片，選取后期時段中包含公司破產時間節點的29個時間段進行實驗。每個數據集的網絡快照中邊的數量變化情況如表2所示，Enron數據集的29個時間片中邊的最大值為3 157，最小值為242，均值為1 693，由于Enron數據集中時間片較多，表中不進行展示。

3.2 實驗結果分析

已知在真實情況下，VAST網絡中第8天發生了高層變動事件，數據集包含10張網絡快照9個階段，異常時段的網絡結構與前后相鄰的正常時段的網絡結構都不同，第7和第8階段的網絡演化均有可能引起網絡波動值的明顯變化，所以在第7或第8階段檢測到異常，都表示檢測成功。同理在dept1和dept2中，在第13或第14階段檢測到異常表示檢測成功。在Enron數據集中，破產事件發生在第27周，所以在第26或27階段檢測出異常表示檢測成功。

實驗共采用四種策略進行異常檢測：M1不進行網絡粗粒化處理，不采用異常節點加權機制，即LinkEvent方法^［8］；M2不進行網絡粗粒化處理，采用異常節點加權機制，指標集LPI由相似性指標CN、PA以及AA構成；M3進行網絡粗粒化處理，不采用異常節點加權機制；M4進行網絡粗粒化處理，同時采用異常節點加權機制，即SCAD方法。實驗將NESO_ED方法^［25］與本文方法進行對比分析。LinkEvent方法是基于單一指標分析網絡演化的方法，NESO_ED方法是基于節點分階段優化的異常事件檢測方法。

利用客觀性評價指標異常檢測敏感值SEN來判斷實驗四種策略的效果，敏感值越大，則異常檢測敏感性越高，越有利于檢測出異常。敏感值的計算如式（13）所示。

3.2.1 不同粗粒化網絡的異常檢測分析

在SCNC運行過程中，會在各層次得到不同的粗粒化網絡，根據實際需要選擇合適層次的粗粒化網絡。本文根據后續異常檢測的效果來選擇算法中最佳層次的粗粒化網絡。M3策略采用了粗粒化網絡并且沒有引入異常節點加權機制，所以實驗主要分析M3的對比實驗結果。

在VAST數據集中選定最佳相似性指標PAS進行實驗，在dept1和dept2數據集中選定最佳相似性指標JAS進行實驗，在Enron數據集上選定最佳相似性指標PAS進行實驗。關于指標選取的分析在之后的3.2.7節進行了詳細闡述。在各數據集上，采用M3策略對不同粗粒化網絡進行異常檢測的實驗結果如表3所示。

由表3可知，SCNC在VSAT、dept1和dept2數據集上運行得到了三個層次的粗粒化網絡，不同層次粗粒化網絡的敏感性都高于原始網絡，并且第二層次的粗粒化網絡表現最好。在Enron數據集上得到了一個層次的粗粒化網絡，并且敏感性高于原始網絡。SCNC算法在不同規模的數據集上運行時，層次數各不相同，會得到不同數量的粗粒化網絡。通常數據集的規模越大，層次數越多，粗粒化網絡的數量越多。從實驗結果可知，對原始網絡進行粗粒化時，中部層次得到的粗粒化網絡在異常檢測中效果較好。分析可知，層次較大時網絡中的節點個數較少，存在過度簡化現象，會造成重要網絡結構信息的丟失，從而使異常檢測敏感性下降。因此，在VSAT、dept1和dept2上取第二層次的粗粒化網絡進行后續異常檢測，在Enron上選取第一層次的粗粒化網絡進行后續異常檢測。

3.2.2 異常權重因子ω的參數敏感性分析

異常權重因子ω值表示異常節點對網絡演化的影響，取值為［0，1］。其值設定應適中，若過大則會導致無法體現出異常節點對網絡演化的影響，過小則會夸大異常節點對網絡演化的影響。通過觀察ω在不同取值下的實驗結果，可以分析ω參數取值對異常檢測的影響。由于只有M2和M4引入異常節點加權機制，所以實驗主要分析M2和M4的實驗結果。在VAST數據集上選擇最佳相似性指標PAS進行實驗，在dept1和dept2數據集中選定最具相似性指標JAS進行實驗，在Enron數據集上選定最佳相似性指標PAS進行實驗。實驗結果如表4所示。

分析表4可知，在VAST和Enron數據集中，隨著ω取值的增大，M2策略的異常檢測敏感值整體呈增加的趨勢；M4策略的異常檢測敏感值先增后減，在中間達到峰值。在dept1和dept2數據集中，隨著ω取值的增大，M2策略的異常檢測敏感值呈增加趨勢；M4策略的異常檢測敏感值呈遞減趨勢，但波動范圍不大。分析可知，由于M4的異常檢測結果有網絡粗粒化的影響，網絡被簡化后丟失了一部分原始網絡中存在的異常節點，所以異常節點加權機制對M4實驗結果的影響波動較小。綜上考慮，在經過簡化的網絡與原網絡中，ω取值在［0.6，0.7］時，實驗效果較好。

3.2.3 SCAD方法異常檢測穩定性分析

實驗在VAST、dept1和dept2以及Enron四個數據集中分析了鏈路預測節點相似性指標的穩定性，即節點相似性指標在不同策略中是否能檢測到異常發生，如果都能檢測成功，并且敏感值都不低，說明該指標穩定性好，普適性高。基于八種指標對四種策略進行實驗，輸出基于不同節點相似性指標的網絡演化波動值，在VAST和Enron數據集上的結果如圖2、3所示，圖中的數據都已進行正則化處理。

圖2是VAST數據集的網絡演化波動。在M4策略下，除了LNHS的其他指標都成功檢測到異常發生，PAS指標的異常檢測敏感性最高。由于VAST中節點和邊的比例較小，網絡結構較為簡單，M3和M4策略下的網絡經過粗粒化處理，網絡結構更為簡單，所以不適用于計算復雜的相似性指標，如LNHS，穩定性就很差，而如CNS、PAS這樣計算簡單的相似性指標就能更準確地檢測到異常，穩定性更好。

圖3是Enron數據集的網絡演化波動。在M4策略下，除HPIS和LNHS指標外的其他指標都能準確檢測到異常發生，但是SOS、JAS、SOS指標還檢測到了第17階段是異常事件，這是由于Enron數據集的多異常事件特性經過SCAD方法，將第17階段本身的異常放大，從而認為該階段也是異常時段。與VAST類似，Enron數據集中節點和邊的比例較小，粗粒化會對網絡結構造成較大影響，應用HPIS和LNHS這樣需要復雜計算的指標在粗粒化后的網絡上進行異常檢測的效果較差，而PAS這樣邏輯簡單的計算指標檢測的效果良好。

3.2.4 SCAD與其他異常檢測方法的對比分析

LinkEvent方法是基于鏈路預測的異常檢測算法中的經典算法，采用固定指標PAS進行異常檢測。NESO_ED方法是基于節點分階段優化的異常檢測算法，通過改進異常檢測時計算指標的選取方法提升了異常檢測的敏感性，這兩種方法在目前的異常檢測方法中具有參考價值。將上述兩種方法進行對比能夠更全面地分析SCAD方法的效果。VAST數據集是異常檢測的經典數據集，且規模適中，多種異常檢測方法在該數據集上的檢測效果較穩定準確。SUC是穩定性評價指標，指成功檢測異常時段的次數與算法運行時的檢測總次數的比值，比值越大，說明算法的穩定性越高。SEN是敏感性評價指標，指在網絡演化波動序列中異常時段波動值和正常演化波動值的均值之差與正常演化波動值均值的比值，比值越大，說明算法的敏感性越高。結合這兩種指標可以較為全面的評價異常檢測算法的效果。本文在VAST數據集上基于PAS指標進行對比實驗，通過SEN、SUC指標來對比分析LinkEvent、NESO_ED和SCAD方法的檢測效果，結果如表5所示。

分析表5可知，對于SEN指標，SCAD比LinkEvent提高了163%，比NESO_ED降低了69%；對于SUC指標，SCAD比NESO_ED提高了40%，比LinkEvent降低了30%。LinkEvent采用單一指標來進行網絡演化分析，該方法不受隨機性的影響，所以SUC指標最高。NESO_ED在每個階段都采用當前的最佳相似性指標進行檢測，將所有階段的最佳檢測效果綜合，所以SEN值很高。綜上分析，SCAD方法可以兼顧異常檢測的穩定性和敏感性，在敏感性較高的情況下，提高了異常檢測的穩定性，能夠更合理地描述網絡演化過程，從而更好地進行異常檢測。

3.2.5 閾值T的設定分析

依據2.3.2節的分析，閾值T的設定對檢測的敏感性有很大影響。由于各數據集中M4策略檢測效果最好，下面主要分析應用于原始網絡的M1和應用于粗粒化網絡的M4，依據能夠成功檢測異常事件指標的實驗結果來設定閾值T。各數據集在不同閾值下誤檢測的時段如表6所示。

在M1策略下，各數據集的情況如下：閾值設定在（0.5，0.7）時，在VAST中除了真實異常發生的第7、8時段，SAS、JAS、SOS和HPIS指標會將第1階段誤檢測為異常時段，LNHS指標會將第1、3階段檢測為異常時段；在dept1中除了真實發生異常的第13、14階段，CNS、AAS會將第2、3、9、10階段誤檢測為異常時段，SAS會將第2～10、15階段誤檢測為異常時段，JAS會將第3～5、7～10、15階段誤檢測為異常時段，SOS會將第2～5、7～10、15階段誤檢測為異常時段；在dept2中除了真實發生異常的第13、14階段，CNS、AAS、SAS、JAS會將第2、3階段誤檢測為異常時段，PAS會將第1～4、10階段誤檢測為異常時段，SOS會將第3階段誤檢測為異常時段，HPIS會將第2、3、5、6、8、10、11階段誤檢測為異常時段，LNHS會將第5、7～11、15階段誤檢測為異常時段；在Enron中除了真實發生異常的第27、28階段，PAS會將第1、3～5階段誤檢測為異常階段，SAS、JAS、SOS會將16、17、23～26階段誤檢測為異常階段。閾值設定在（0.7，0.8）時，在VAST中未出現誤檢測；在dept1中SAS會將第3、9、10誤檢測為異常階段，JAS、SOS會將第3、9階段誤檢測為異常時段；在dept2中CNS、AAS會將第3階段誤檢測為異常時段，PAS會將第2、3階段誤檢測為異常時段，HPIS會將第2、3、11階段誤檢測為異常時段，LNHS會將第8～10階段誤檢測為異常時段；在Enron中SAS、JAS、SOS會將第26階段誤檢測為異常時段。閾值設定在0.8以上時，則各數據集都不會出現誤檢測的情況。

在M4策略下，各數據集的情況如下：閾值設定在（0.5，0.7）時，在VAST中CNS和AAS指標會將第1、5階段誤檢測為異常階段，SAS、JAS、SOS和HPIS會將第1階段誤檢測為異常階段，LNHS會將第1、3階段誤檢測為異常階段；在dept1中CNS會將第2、3、9階段誤檢測為異常階段，AAS會將第2、9階段誤檢測為異常階段，SAS會將第2、3階段誤檢測為異常階段，SOS會將第3階段誤檢測為異常階段，HPIS會將第3、8、9階段誤檢測為異常階段，LNHS會將第3、8、11階段誤檢測為異常階段；在dept2中CNS和LNHS會將第2階段誤檢測為異常階段，HPIS會將第1、5、11階段誤檢測為異常階段；在Enron中SAS會將第7～18、20、21、24～26階段誤檢測為異常時段，JAS、SOS會將第7～11、13～18、20、21、24～26階段誤檢測為異常時段。閾值設定在（0.7，0.8）時，在VAST中未出現誤檢測；在dept1中CNS會將第2、9階段誤檢測為異常階段；在dept2中HPIS會將第5、11階段誤檢測為異常階段；在Enron中SAS、JAS、SOS會將第13、17、18、26階段誤檢測為異常時段。閾值設定在0.8以上時，則各數據集都不會出現誤檢測的情況。

以上實驗結果顯示閾值T較小時，在原始網絡和粗粒化網絡中不同檢測指標都容易產生誤檢測現象。閾值較小時，會將網絡演化中在正常范圍內波動的時段誤認為是異常時段，閾值無法起到篩選作用，導致檢測到錯誤的異常結果；閾值較大時，又會將異常時段也誤認為是正常演化時段。這兩種情況都不利于異常檢測，所以應將其值設置比較適中。SCAD方法結合以上實驗結果分析，將閾值T設定為0.8。

3.2.6 SCAD方法異常檢測敏感性分析

使用異常檢測敏感值客觀評價指標對四種策略下各節點相似性指標進行衡量對比，結果如表7～10所示。敏感值越大，說明在該相似性計算指標下網絡異常演化階段的波動越明顯，異常檢測的效果越好。表中出現負值是因為該階段的敏感值小于之前階段敏感值的平均值，說明該相似性計算指標沒有檢測出異常發生。

表7是在VAST數據集中，四種策略在不同節點相似性指標下的敏感值，M4相較于M1，在所有指標下均提高了敏感值。由表7中M2和M3分析得出，僅采用異常節點加權機制的敏感值要比僅進行網絡粗粒化處理的敏感值高，說明在VAST網絡中，采用異常節點加權機制對網絡演化分析作用更加突出，因為VAST網絡中有400個節點，異常節點數量也相對較多，考慮異常節點的影響后，異常檢測敏感性有較為明顯的提升。

表8和9分別是dept1和dept2中的敏感值變化情況。由兩表看出，采用異常節點加權機制和網絡粗粒化處理都提高了敏感性，并且都是同時引入SCAD方法的檢測效果最好。由表8和9中的M2和M3分析得出，僅進行粗粒化處理的的敏感值普遍比僅采用異常節點加權機制的敏感值高，說明在dept1和dept2中，網絡粗粒化在網絡演化分析中的作用更加突出。

表10是Enron中的敏感值變化情況。分析表10可知，M4策略相較于M1策略，在各指標下均提高了敏感值，且PAS提升最大。由表10中M2與M3得出，僅進行網絡粗粒化的敏感值比僅采用異常節點加權機制的敏感值高。Enron數據集點少邊多，在邏輯簡單的相似性指標上異常檢測的表現突出，而在計算復雜的指標上表現較差，因而在粗粒化網絡上異常檢測效果提升更大。

綜上所述，在各個數據集中，同時引入異常節點加權機制和進行網絡粗粒化處理的M4相較于M1，在所有相似性指標下均不同程度提高了敏感值，并且敏感性值最高，說明SCAD方法的檢測效果最好，有效提高了異常檢測敏感性。

3.2.7 最佳相似性指標的選取分析

選取最佳相似性指標主要分析M3和M4兩種情況。VAST中，PAS指標表現最為突出，四種情況下敏感值皆為最大值，所以選取PAS為VAST數據集的最佳指標。dept1中，結合網絡演化波動圖與敏感值結果，M1為原始情況，敏感值為負數說明沒有檢測成功，排除PAS指標。在剩余指標中LNHS的敏感值最大，但在后續情況下LNHS表現都不好。總體四種策略中JAS和SOS指標效果較好，且JAS效果相比更好，所以選取JAS指標為dept1數據集的最佳指標。dept2中，M3和M4情況下皆為JAS和LNHS表現最好，JAS在四種情況下效果都比LNHS要好，綜合情況后選取JAS為最佳指標。Enron中，PAS和AAS指標表現都較好，但PAS在四種情況下敏感值皆為最大值，所以選取PAS為VAST數據集的最佳指標。

綜上所述，實驗表明，SCAD方法不僅具有良好的穩定性，也有較高的異常檢測敏感性。并且僅引入異常節點加權機制和僅進行網絡粗粒化處理對敏感性的影響不同，雖都提高了敏感值，但相比引入異常節點加權機制，對網絡進行空間尺度粗粒化對提高異常檢測敏感性的貢獻更大。

3.2.8 算法時間復雜度分析

SCAD方法分為SC_NC和WAN_AD兩個步驟，下面分別分析它們的算法復雜度：a）SC_NC中的粗粒化算法是層次性貪心算法，設輸入網絡節點數為n，時間復雜度則是O（n log n）；b）WAN_AD中，設輸入網絡節點為n，LPI中的最高時間復雜度為h（上限為O（n）），|LPI|是鏈路預測算法集中包含的相似性指標個數，則識別異常節點算法時間復雜度O（h+n×|LPI|），異常檢測算法時間復雜度是O（（n-1）×n）。由于n遠大于|LPI|的值，所以WAN_AD時間復雜度為O（n²）。經SC_NC粗粒化后網絡規模降低了約64%，由于網絡規模大幅減小，SCAD方法的整體時間復雜度也相應降低。

4 結束語

針對當前社會網絡異常檢測方法中存在的網絡簡化效果不好和異常檢測效率不高的問題，本文提出了一種基于空間尺度粗粒化的社會網絡異常檢測方法。SC_NC方法對網絡進行快速粗粒化處理，且保持網絡拓撲結構性質不變；WAN_AD算法通過識別異常節點，并在異常檢測時對其進行加權處理。通過在VAST、EmailEU（dept1和dept2）和Enron數據集上的四種策略對算法進行驗證，表明SCAD方法能夠快速的簡化網絡，降低后續異常檢測的復雜度，從而提高檢測的效率；并且能夠更好的兼顧異常檢測的穩定性和敏感性，具有更好地檢測效果。本文方法在發生單一異常事件的社會網絡中表現非常好，在連續異常事件發生的社會網絡異常檢測中還有待繼續深入研究；并且節點相似性指標與網絡演化也存在一定的對應關系，下一步將考慮研究在網絡演化的不同階段選取相對應的最優指標進行異常檢測。

參考文獻：

［1］Rahimi F，Rezaei H.An event-triggered recursive state estimation approach for time-varying nonlinear complex networks with quantization effects［J］.Neurocomputing，2021，426：104-113.

［2］Imtiaz Z B，Manzoor A，Islam S U，et al.Discovering communities from disjoint complex networks using multi-layer ant colony optimization［J］.Future Generation Computer Systems，2020，115：659-670.

［3］An C，O’Malley A J，Rockmore D N.Towards intelligent complex networks：the space and prediction of information walks［J］.Applied Network Science，2019，4（1） 1-21.

［4］Wang Huan，Hu Wenbin，Qiu Zhenyu.Nodes’evolution diversity and link prediction in social networks［J］.IEEE Trans on Knowledge and Data Engineering，2017，29（10）：2263-2274.

［5］Chen Guangfu，Xu Chen，Wang Jingyi，et al.Graph regularization weighted nonnegative matrix factorization for link prediction in weighted complex network［J］.Neurocomputing，2019，369：50-60.

［6］Wang Zhenbao，Wang Yuxin，Ma Jinming，et al.Link prediction based on weighted synthetical influence of degree and H-index on complex networks［J］.Physica A：Statistical Mechanics and Its Applications，2019，527：121184.

［7］Wang Meihong，Qiu Linling，Wang Xiaoli.A survey on knowledge graph embeddings for link prediction［J］.Symmetry，2021，13（3）：485.

［8］胡文斌，彭超，梁歡樂，等.基于鏈路預測的社會網絡事件檢測方法［J］.軟件學報，2015，26（9）：2339-2355.（Hu Wenbin，Peng Chao，Liang Huanle，et al.Event detection method based on link prediction for social network evolution［J］.Journal of software，2015，26（9）：2339-2355.）

［9］Wang Huan，Hu Wenbin，Qiu Zhenyu，et al.An event detection me-thod for social networks based on evolution fluctuations of nodes［J］.IEEE Access，2017，6：12351-12359.

［10］Tran C，Shin W Y，Spitz A.Community detection in partially observable social networks［J］.ACM Trans on Knowledge Discovery from Data，2021，16（2）：1-24.

［11］Kim B J.Geographical coarse graining of complex networks［J］.Physical Review Letters，2004，93（16）：168701.

［12］Song C，Havlin S，Makse H A.Self-similarity of complex networks［J］.Nature，2005，433（7024）：392-395.

［13］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multiscale complexity in networks［J］.Nature，2010，466（7307）：761-764.

［14］Chen Juan，Lu Junan，Lu Xiaofei，et al.Spectral coarse graining of complex clustered networks［J］.Communications in Nonlinear Science and Numerical Simulation，2013，18（11）：3036-3045.

［15］Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks［J］.Journal of Statistical Mechanics：Theory and Experiment，2008，30（2）：155-168.

［16］羅浩，閆光輝，張萌，等.融合多元信息的多關系社交網絡節點重要性研究［J］.計算機研究與發展，2020，57（5）：954-970.（Luo Hao，Yan Guanghui，Zhang Meng，et al.Research on the importance of multi-relationship social network nodes with multiple information fusion［J］.Journal of Computer Research and Development，2020，57（5）：954-970.）

［17］江淼淼，孫更新，賓晟.多關系社交網絡中社團結構發現算法［J］.計算機科學與探索，2019，13（7）：1134-1144.（Jiang Miaomiao，Sun Gengxin，Bin Sheng.Community structure discovery algorithm in multi-relationship social networks［J］.Journal of Frontiers of Computer Science and Technology，2019，13（7）：1134-1144.）

［18］傅馨玉，顧益軍.融合節點重要性的無監督鏈路預測算法［J/OL］.計算機工程與應用.（2021-09-08）［2021-10-01］.http：//kns.cnki.net/kcms/detail/11.2127.TP.20210908.1040.008.html.（Fu Xinyu，Gu Yijun.Unsupervised link prediction algorithm fusing node importance［J/OL］.Computer Engineering and Applications.（2021-09-08）［2021-10-01］.http：//kns.cnki.net/kcms/detail/11.2127.TP.20210908.1040.008.html.）

［19］Zhan Qianyi，Zhang Jiawei，Yu P，et al.Community detection for emerging social networks［J］.World Wide Web，2017，20（6）：1409-1441.

［20］Newman M.Modularity and community structure in networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2006，103（23）：8577-8582.

［21］路蘭，孟曉宇，劉瑞超.基于試驗設計的鏈路預測算法應用研究［J］.數理統計與管理，2019，38（5）：873-881.（Lu Lan，Meng Xiaoyu，Liu Ruichao.Application of link prediction algorithm based on experimental design［J］.Journal of Applied Statistics and Management，2019，38（5）：873-881.）

［22］Grinstein G，Plaisant C，Laskowski S，et al.VAST 2008 challenge：introducing mini-challenges［C］//Proc of IEEE Symposium on Visual Analytics Science and Technology.Piscataway，NJ：IEEE Press，2008：195-196.

［23］Paranjape A，Benson A R，Leskovec J.Motifs in temporal networks［C］//Proc of the 10th ACM International Conference on Web Search and Data Mining.New York：ACM Press，2017：601-610.

［24］Rossi R A，Ahmed N K.The network data repository with interactive graph analytics and visualization［C］//Proc of the 29th AAAI Confe-rence on Artificial Intelligence.Palo Alto，AAAI Press，2015：4292-4293.

［25］富坤，仇倩，趙曉夢，等.基于節點演化分階段優化的事件檢測方法［J］.計算機科學，2020，47（5）：96-102.（Fu Kun，Qiu Qian，Zhao Xiaomeng，et al.An event detection method based on node evolution staged optimization［J］.Computer Science，2020，47（5）：96-102.）