[發明專利]一種高階控制圖模式檢測方法、系統、存儲介質及應用

在審

• 申請號: 202010570175.1
• 申請日: 2020-06-21
• 公開（公告）號: CN111831860A
• 公開（公告）日: 2020-10-27
• 發明（設計）人: 王炳波;馬秀娟;高琳;胡潔;王存熾;王玙
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06K9/62
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 何畏

本發明屬于數據挖掘技術領域，公開了一種高階控制圖模式檢測方法、系統、存儲介質及應用，基于圖的最大匹配識別方法，從結構可控性角度將復雜系統中每一層的連邊關系分類為：關鍵邊、普通邊、冗余邊；用量化指標度量普通邊在多層之間的一致性，構建帶權重的多層一致控制網絡；給出改進的最大權重匹配檢測方法，識別由普通邊構成的每一層網絡中匹配邊的集合；結合每一層的匹配邊及關鍵邊檢測出一致控制網絡的高階控制圖模式。本發明具有高效、抗數據噪聲、檢測的高階控制圖模式具有唯一確定性的優點，為多層復雜系統中的知識發現提供工具支持；可刻畫多層網絡的共性和特性。

技術領域

本發明屬于數據挖掘技術領域，尤其涉及一種高階控制圖模式檢測方法、系統、存儲介質及應用。

背景技術

目前，隨著技術的發展及進步使得大量的數據可以被收集，而在一些網絡數據的建模中，多層網絡的建模相對于單層網絡而言，更利于對網絡的研究且它們更易被建模為多層網絡。例如，生物網絡中，多層基因共表達網絡的建立被用于檢測有生物意義的模塊；社交網絡中，基于個體間的多種關系建模的多層相互作用網絡使得個體關系被清楚地展示；生態網絡中，多層網絡的比對用于發現多層網絡間有不同外圍的相同主干。挖掘復雜一致網絡的高階控制圖模式時，第一步需要確定多層復雜系統的形式，然后將結構可控性控制理論及改進的最大權重匹配檢測過程應用于多層復雜系統中檢測高階控制圖模式。

(1)多層網絡模型

任意一個多層網絡可以表示為其中G_l＝(V_l,E_l)表示第l層網絡，V_l為G_l中的節點集合，E_l為G_l中邊的集合。且交叉層：

是不同網絡層G_l和G_k中節點之間的連邊關系集合。E_l中的元素被稱為層內連接，與之相反，E_lk中的元素被稱為層間連接。

(2)復雜系統的可控性

一個系統是可控的，當且僅當它可以在有限時間內從任意初始狀態被驅動到期望的終止狀態。一個遵循標準的線性時不變過程的系統可以表示為：

向量x(t)＝(x₁(t),...,x_N(t))^T表示t時刻系統中N個節點的狀態，u(t)＝(u₁(t),...,u_M(t))^T表示外部控制器添加的時變輸入信號；分別表示狀態矩陣以及輸入矩陣。A用于刻畫系統中的連接關系；B用于確定被外部控制器所控制的節點。

式(2)所描述的系統可以被描述為是可控的，當且僅當滿足Kalman的可控性秩條件：

其中

(3)圖的最大匹配

對于一個圖G＝(V,E)而言，最大匹配是有向邊子集中的邊，且M滿足：對任意兩條邊v_i,v_j∈M和v_m,v_n∈M，v_i≠v_m，v_j≠v_n，使得|M|的值達到最大。最大匹配中的邊所形成的路徑稱為控制路徑，M將有向圖G＝(V,E)劃分成不相交的徑、環結構，其中的每條有向邊即為形成控制路徑的控制流，稱這里的控制路徑為高階控制圖。