【摘要】：網(wǎng)絡異常檢測是信號處理領域中的重要研究內容,廣泛應用于通信網(wǎng)絡、計算機網(wǎng)絡、社交網(wǎng)絡和生物網(wǎng)絡等眾多應用領域。通常情況,網(wǎng)絡中大量的數(shù)據(jù)是由網(wǎng)絡節(jié)點和節(jié)點之間的連接關系組成的,即所謂的“關系”數(shù)據(jù)。這“關系”數(shù)據(jù)往往呈現(xiàn)隨機特性,一般表示成隨機圖的形式加以處理。表示網(wǎng)絡連接關系的隨機圖模型有Erd?s-Rényi(ER)模型、統(tǒng)計塊模型和Chang-Lu(CL)模型等。其中,ER隨機圖是一種特殊的圖模型,其端點間的連接概率相同,圖結構特征較為簡單。統(tǒng)計塊模型和CL模型隨機圖則具有不均勻特性,不同塊內甚至任意端點間連接概率往往不同,具有較為復雜的圖結構特性。當網(wǎng)絡中存在惡意流量或威脅行為等異常情況時,網(wǎng)絡部分節(jié)點之間的連接處于異常頻繁的狀態(tài),在圖模型下表現(xiàn)為與異常端點對應子圖的邊概率增大的統(tǒng)計特性。本文的目的就是在背景圖(網(wǎng)絡正常情況下的圖模型)為統(tǒng)計塊模型和CL隨機圖等復雜模型下,根據(jù)觀測的“關系”數(shù)據(jù)或觀測圖判定網(wǎng)絡是否出現(xiàn)異常。因為網(wǎng)絡異常體現(xiàn)在部分節(jié)點間的關系數(shù)據(jù)異常,所以圖模型下的網(wǎng)絡異常檢測也稱為異常子圖檢測�？紤]圖數(shù)據(jù)為已有離線數(shù)據(jù)或實時的數(shù)據(jù)流形式,異常子圖檢測可進一步分為離線情況下的異常子圖檢測和在線的變點檢測兩種。離線異常子圖檢測是一種典型的二元檢測問題,其目的是根據(jù)已獲取的觀測圖確定該圖是屬于正常情況的背景圖模式或屬于部分端點對應子圖發(fā)生異常的情況�，F(xiàn)有典型的異常子圖檢測算法主要包括基于矩陣特征譜的異常檢測方法和似然比異常檢測方法。似然比方法能提供高的檢測性能,但一般假設背景圖為ER隨機圖模型,不適用于更復雜的統(tǒng)計塊模型或CL隨機圖模型�；诰仃囂卣髯V的異常檢測方法則可以應用于統(tǒng)計塊模型或CL隨機圖模型。與似然比方法相比,矩陣特征譜的異常檢測方法增強了異常檢測算法的實用性,但從檢測性能而言,似然比方法更優(yōu)。因此,探索基于特征譜的高檢測性能的異常檢測算法是必要和有意義的。在線異常子圖檢測(變點檢測)是一種動態(tài)異常檢測問題,它是根據(jù)觀測圖數(shù)據(jù)流來確定圖序列何時從正常的圖模式突變?yōu)楫惓顟B(tài),即估計網(wǎng)絡異常現(xiàn)象產(chǎn)生的時刻。值得指出的是,當異常時刻為無窮大時,則認為觀測的圖序列數(shù)據(jù)流為正常模式(或零假設)。本質上,變點檢測需要在每個觀測時刻對相應的觀測圖進行二元判決以判斷是否有異常產(chǎn)生。因此,變點檢測可看作系列二元檢測問題。由于圖序列是在線采集的,故衡量變點檢測性能的指標除了估計精度之外,還特別包括算法的實時性能或算法計算復雜度。目前,關于異常子圖的變點檢測方法主要有基于圖特征的變點檢測方法和似然比變點檢測方法。上述方法具有較好的估計精度,但其計算復雜度一般較高。如何降低算法的復雜度以提升算法的實時性能仍是亟需解決的問題。針對離線異常子圖檢測和在線異常子圖檢測(變點檢測)研究中存在的問題,本文在總結異常子圖檢測國內外研究的基礎之上,分析了ER隨機圖、統(tǒng)計塊模型等背景圖模型的特征譜特性,從隨機矩陣特征譜和圖特征等角度展開了復雜網(wǎng)絡背景下的異常檢測方法研究,具體工作如下:(1)根據(jù)統(tǒng)計塊隨機圖的鄰接矩陣的特征值特性,提出了統(tǒng)計塊模型下的特征譜異常子圖檢測算法。(2)在分析統(tǒng)計塊觀測圖在異常子圖嵌入前后節(jié)點介數(shù)特性變化的基礎上,探索了基于節(jié)點介數(shù)的異常子圖檢測方法。仿真實驗表明該方法具有高的檢測性能。(3)利用三角子圖等圖特征,提出了一種適用于CL隨機圖模型下的低復雜度的變點檢測算法。該方法與傳統(tǒng)檢測方法相比,具有更低的計算量,能滿足大維網(wǎng)絡背景下變點檢測的實時性要求。
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 田方;;一類稀疏隨機圖的距離匹配數(shù)（英文）[J];數(shù)學進展;2018年02期

2 溫亮;王莉雯;;基于C#的隨機圖像驗證碼的繪制[J];城市地理;2016年24期

3 王越乙;徐樅巍;;指數(shù)隨機圖(p*)模型不同描述的對比研究[J];清華大學學報(自然科學版);2015年04期

4 李木梓;徐柱;李志林;張紅;怓鵬;;基于層次隨機圖的道路選取方法[J];地球信息科學學報;2012年06期

5 郭子政;崔彥;吳曉薇;趙保利;;具有冪率度分布的隨機圖上的幸存者統(tǒng)計和平均位損傷[J];內蒙古師范大學學報(自然科學漢文版);2008年04期

6 王漢興;馬馳;;一類隨機圖的演化(英文)[J];運籌學學報;2006年01期

7 陳愛萍;俞琰;;基于指數(shù)隨機圖模型的網(wǎng)絡新聞媒體分析[J];金陵科技學院學報;2012年02期

8 許瓊方;王東;;基于幾何隨機圖模型的傳感器網(wǎng)絡拓撲分析[J];衡陽師范學院學報;2007年03期

9 馬文麒,馬文麒,楊俊忠,胡崗;耦合映象格子凍結化隨機圖樣模式的動力學特征(英文)[J];北京師范大學學報(自然科學版);1999年01期

10 陳志;范益政;杜文學;;隨機圖的譜矩(英文)[J];應用數(shù)學;2011年04期

相關會議論文 前7條

1 萬超崗;趙杰煜;張媛媛;;基于隨機圖的情感產(chǎn)生模型[A];第十四屆全國圖象圖形學學術會議論文集[C];2008年

2 李莉;耿顯民;;一類隨機圖的鄰點度數(shù)和[A];第十一屆中國不確定系統(tǒng)年會、第十五屆中國青年信息與管理學者大會論文集[C];2013年

3 張湘莉蘭;苑波;駱志剛;;競爭與合作——復雜網(wǎng)絡結構化形成的內因[A];第八屆全國信息隱藏與多媒體安全學術大會湖南省計算機學會第十一屆學術年會論文集[C];2009年

4 章忠志;周水庚;方錦清;;復雜網(wǎng)絡確定性模型研究的最新進展[A];第四屆全國網(wǎng)絡科學學術論壇暨研究生暑期學校論文集[C];2008年

5 章忠志;周水庚;;網(wǎng)絡建模[A];第五屆全國復雜網(wǎng)絡學術會議論文（摘要）匯集[C];2009年

6 王天驕;汪小帆;;加權網(wǎng)絡的搜索性研究[A];第三屆全國復雜動態(tài)網(wǎng)絡學術論壇論文集[C];2006年

7 鄭志剛;;前言[A];第三屆全國復雜動態(tài)網(wǎng)絡學術論壇論文集[C];2006年

相關重要報紙文章 前1條

1 福建 周京玲;廠家，我們需要隨機圖紙[N];電子報;2007年

相關博士學位論文 前10條

1 劉群;關于隨機圖和復雜網(wǎng)絡若干問題的研究[D];吉林大學;2018年

2 顏云志;有向無標度圖與二項隨機圖圖因子[D];上海大學;2007年

3 江波;基于圖理論與稀疏約束模型的圖像表示、匹配與識別[D];安徽大學;2015年

4 郇瀟;圖中匹配的可擴性研究[D];南開大學;2010年

5 賈嘯;復雜電磁環(huán)境下電子信息網(wǎng)絡的滲流與魯棒性研究[D];電子科技大學;2016年

6 馬世乾;配電網(wǎng)智能孤島劃分與隨機拓撲生成[D];天津大學;2016年

7 尚軼倫;隨機圖及對個體系統(tǒng)的一致性問題[D];上海交通大學;2010年

8 崔愛香;復雜網(wǎng)絡建模及其傳播動力學研究[D];電子科技大學;2014年

9 姚燕;廣域多播可靠傳輸控制機制研究[D];復旦大學;2008年

10 楊志虎;復雜網(wǎng)絡上的演化博弈與合作演化動力學研究[D];西安電子科技大學;2014年

相關碩士學位論文 前10條

1 閆志強;基于核分解無向隨機圖模型的貝葉斯推斷[D];吉林大學;2019年

2 黃倩楠;復雜網(wǎng)絡背景下的異常檢測方法研究[D];吉林大學;2018年

3 萬爽;基于指數(shù)隨機圖模型的物流網(wǎng)絡節(jié)點重要度研究[D];武漢理工大學;2016年

4 張俊;復雜網(wǎng)絡的統(tǒng)計分析[D];東南大學;2018年

5 高雪嬌;3-參數(shù)指數(shù)隨機圖的生成與參數(shù)估計[D];吉林大學;2017年

6 田甜;基于層次隨機圖模型的復雜腦網(wǎng)絡鏈路預測研究[D];太原理工大學;2015年

7 劉亮;基于指數(shù)隨機圖的社會網(wǎng)絡構建關鍵技術研究[D];國防科學技術大學;2013年

8 萬超崗;基于隨機圖的情感產(chǎn)生模型的研究[D];寧波大學;2009年

9 曹道通;Kn\E(H)圖和大規(guī)模隨機圖的染色算法研究[D];蘭州交通大學;2017年

10 尹波;隨機圖的色和可區(qū)別染色算法研究[D];蘭州交通大學;2016年

本文編號：2778248