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

在審

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

本發明公開一種從動態屬性圖中檢測多異常子圖演化算法。首先獲取動態網絡數據集；對數據進行預處理，篩選實驗中所需要的數據字段，對數據缺失值進行刪除或者補全的處理；構建動態網絡；將動態圖和參數M輸入到算法模型DE?MASS中，輸出一組演化異常子圖Ψ^ω使目標函數的值最大；將演化異常子圖Ψ^ω在動態圖中可視化出來，直觀地發現異常子圖的演化模式和演化特點。該算法能夠有效在動態圖中檢測多異常子圖的演化過程，可以應用于多個領域實際問題中。

技術領域

本發明屬于數據挖掘和異常檢測領域，是一種從動態屬性圖中檢測多異常子圖演化算法，從而進一步直觀地分析異常子圖在動態圖中演化的過程。

背景技術

一個屬性圖由一個節點集合和一個邊集合構成，異常子圖檢測是指在一個由節點集合和邊集合構成的連通屬性圖中檢測出異常連通子圖的過程。異常子圖檢測方法已成功地應用于社交媒體網絡事件檢測、道路網絡交通擁擠檢測等任務中，但對屬性圖中異常子圖動態演化的研究卻很少。目前，異常子圖檢測算法主要包括精確算法和近似算法，精確算法能在可接受的時間內，對圖的節點數量小于1000的小規模問題求解。一種搜索算法FlexScan用于識別由一個中心和它的k-1鄰域的一個連通子集構成的所有連通子圖中最不規則的連通子圖。Speakman和Neillet等人通過應用線性時間子集掃描(LTSS)來過濾次優子集，并為圖結構數據設計新的分支定界算法，有效提高了FlexScan的性能。另一方面，學術界也已經提出了許多用于異常子圖掃描的近似算法。Duczmal等人提出了一種具有模擬退火策略的啟發式算法，該算法通過在子圖的緊縮性上加入正則化來擴展。Speakman等人提出了一種基于dijkstra的算法的可加子圖檢測算法。Rozenshtein等人應用半定規劃和GW算法來識別緊湊但不一定連接的異常子圖。Chen和Neil提出了一種基于迭代子圖展開和線性時間子集掃描的貪婪算法。Wu等人將屬性圖近似于樹形拓撲結構，提出了基于動態規劃的TSPSD的算法。近似算法可以在大規模數據集上使用，但是對于返回的子圖的質量沒有理論上的保證。

發明內容

該模型可以從動態屬性圖中檢測多異常子圖，從而進一步直觀地分析異常子圖在動態圖中演化的過程，具有較高的應用價值。例如，(1)交通擁堵檢測問題：將城市交通道路網絡構建成一個網絡圖，通過車速和車流量來檢測道路網絡中的異常子圖，并通過直觀的異常子圖演化分析，可以得知哪些區域的路網結構是經常性發生擁堵的，可以為未來城市道路發展作為參考；(2)社交媒體事件檢測問題：通過社交媒體數據(例如微博數據)構建一個以人為節點的社交網絡，通過某個事件的語料庫檢測動態社交網絡中的異常子圖，從而可以直觀地分析該時間在社交網絡中傳播的過程，可以通過影響一些關鍵節點來影響輿論的傳播。

本發明的技術方案是一種從動態屬性圖中檢測多異常子圖演化算法，以下描述步驟：

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

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

第三步:構建動態網絡；

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

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

該方法模型的理論技術主要包含如下：

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

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