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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

6 王漢興;馬馳;;一類隨機(jī)圖的演化(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2006年01期

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

8 許瓊方;王東;;基于幾何隨機(jī)圖模型的傳感器網(wǎng)絡(luò)拓?fù)浞治鯷J];衡陽師范學(xué)院學(xué)報(bào);2007年03期

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

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

相關(guān)會(huì)議論文 前7條

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

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

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

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

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

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

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

相關(guān)重要報(bào)紙文章 前1條

1 福建 周京玲;廠家，我們需要隨機(jī)圖紙[N];電子報(bào);2007年

相關(guān)博士學(xué)位論文 前10條

1 劉群;關(guān)于隨機(jī)圖和復(fù)雜網(wǎng)絡(luò)若干問題的研究[D];吉林大學(xué);2018年

2 顏云志;有向無標(biāo)度圖與二項(xiàng)隨機(jī)圖圖因子[D];上海大學(xué);2007年

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

4 郇瀟;圖中匹配的可擴(kuò)性研究[D];南開大學(xué);2010年

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

6 馬世乾;配電網(wǎng)智能孤島劃分與隨機(jī)拓?fù)渖蒣D];天津大學(xué);2016年

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

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

9 姚燕;廣域多播可靠傳輸控制機(jī)制研究[D];復(fù)旦大學(xué);2008年

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

相關(guān)碩士學(xué)位論文 前10條

1 閆志強(qiáng);基于核分解無向隨機(jī)圖模型的貝葉斯推斷[D];吉林大學(xué);2019年

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

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

4 張俊;復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)分析[D];東南大學(xué);2018年

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

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

7 劉亮;基于指數(shù)隨機(jī)圖的社會(huì)網(wǎng)絡(luò)構(gòu)建關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2013年

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

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

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

本文編號(hào)：2778248