[發明專利]一種從動態屬性圖中檢測多異常子圖演化算法

在審

• 申請號: 202011448687.7
• 申請日: 2020-12-09
• 公開（公告）號: CN112417303A
• 公開（公告）日: 2021-02-26
• 發明（設計）人: 潘沛凱;武南南;王文俊;劉春鳳
• 申請（專利權）人: 天津大學
• 主分類號: G06F16/9535
• 分類號: G06F16/9535;G06F16/9536;G06F16/9537;G06Q50/00
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 程小艷

1.一種從動態屬性圖中檢測多異常子圖演化算法，其特征在于，以下描述步驟：

第一步：獲取動態網絡數據集；

第二步：對數據進行預處理，篩選實驗中所需要的數據字段，對數據缺失值進行刪除或者補全的處理；

第三步:構建動態網絡；

第四步：將動態圖和參數M輸入到算法模型DE-MASS中，輸出一組演化異常子圖Ψ^ω使目標函數的值最大；

第五步：將演化異常子圖Ψ^ω在動態圖中可視化出來，直觀地發現異常子圖的演化模式和演化特點。

2.根據權利要求1所述的一種從動態屬性圖中檢測多異常子圖演化算法，其特征在于，該方法模型的理論技術主要包含如下：

1)動態圖和演化異常子圖的符號定義

動態圖：在每個時間片上是一個無向連通圖，隨著時間的演化動態圖的結構是不變的，其中是頂點集，l是頂點總數，表示邊集，T＝{1,…,n}表示動態圖中包含的所有時間片；

根據時間片集將圖G分為{G¹,…,Gⁿ}，是經驗p值的集合，p^t:表示在時間片上具有p值(p^t(v))的每個頂點，t∈T；

演化異常子圖：給定時間片t上的異常子圖每個異常子圖在G^t中為連通的，i∈{1,…,m}，有和演化的異常子圖是一個滿足以下條件的異常子圖序列：

(a)存在一個連續的時間片序列ω(j,k)，它表示時間片集合{j,j+1,…,k}，ω中每個時間片的異常子圖集合不為空；

(b)在時間片序列ω中，相鄰時間片的異常子圖之間至少共享一個頂點，例如對于中的異常子圖滿足

2)多異常子圖掃描的目標函數

給定一個動態圖用非參數掃描統計量來檢測演化異常子圖，Ψ^ω是指在時間周期ω(j,k)內演化的異常子圖，即N(Ψ^ω)表示Ψ^ω中的總節點數，N_α(Ψ^ω)定義為N_α(Ψ^ω)＝∑_{v∈V(Ψ)，t∈ω}δ(p^t(v)≤α)，其中表示演化異常子圖Ψ中的頂點集，α是預定義的符號值；如果輸入為真，函數δ(.)＝1；反之，δ(.)＝0；

動態圖G中非參數掃描統計量的一般形式定義為：

式中表示Ψ^ω中正常節點的數目，M為正常節點數量的上限；基于非參數掃描統計量φ，演化異常子圖的檢測可形式化為以下優化問題：

相當于如下問題：

其中是集合{α_max}與不超過中α_max的不同p值集合的并集；

3)問題重構

由于NPGS問題包含一個非線性的目標函數，提出在動態圖中將NPGS問題轉化為一系列子問題；

當在Ψ^ω中固定正常節點的數量，在滿足連通的約束下，求Ψ^ω的最大異常數，從而得到最優的Ψ^ω；

進一步地，推廣到在Ψ^ω中正常節點數預算約束的問題：

令和NPGS問題(4)相當于以下問題：

其中，每個對于是正常節點的個數，通過優化預算節點Prize-Collecting Steiner Tree問題(B-PCST)得到的異常子圖

其中，表示子樹；

設置利潤π_α(v)＝1和成本c_α(v)＝0如果p(v)≤α；否則，π_α(v)＝0，c_α(v)＝1；

此問題的步驟表示為利用兩個異常子圖在連續時間片內至少擁有一個公共頂點，建立一個樹集：

其中，S為問題(6)的一個異常子圖，其中收益π_α＝N_α(S)，花費是動態異常子圖，我們設

問題(7)的過程用問題(6)的異常子圖集ω表示為

3.根據權利要求2所述的一種從動態屬性圖中檢測多異常子圖演化算法，其特征在于，DE-MASS近似算法:為求出式(5)的解，提出一種近似算法：DE-MASS，首先在算法1中引入了幾個概念：

a)TSPSD(G,α)：輸出靜態圖G中最異常的連通子圖；

b)Nei(ω)：與時間集合ω相鄰的兩個時間片集。例如，如果ω＝{t,…,2t}，Nei(ω)＝{t-1,2t+1}；

c)將S_K時間τ內頂點的p值設為1.0，即p^τ(v)＝1.0，

d)Tree(S^ω)：去掉演化圖S^ω中的一些邊，輸出一個樹集

e)DP1(K,G)：使用動態規劃來尋找最優解K。輸入為budget-K和圖G；

f)用動態規劃法求最優解Ψ^ω，輸入為budget-m和異常子圖集合commonNode(S^τ,S^τ+1)：|{S^τ∩S^τ+1}|，公共節點函數計算圖形中S^τ和S^τ+1的公共頂點個數。