1、碩士學(xué)位論文統(tǒng)計(jì)顯著子圖發(fā)現(xiàn)及統(tǒng)計(jì)顯著子圖發(fā)現(xiàn)及其應(yīng)用應(yīng)用DetectingStatisticallySignificantSubgraphsItsApplications作者姓名：趙璨學(xué)科、專業(yè)：軟件工程學(xué)號(hào)：21417037指導(dǎo)教師：何增有完成日期：2017.3.20大連理工大學(xué)DalianUniversityofTechnology大連理工大學(xué)碩士學(xué)位論文I摘要子圖發(fā)現(xiàn)是現(xiàn)代網(wǎng)絡(luò)科學(xué)的一個(gè)重要研究課題，是展示并解析網(wǎng)絡(luò)結(jié)構(gòu)的重要手

2、段，其目標(biāo)是從一張完整的圖結(jié)構(gòu)中，尋找一個(gè)或多個(gè)具有某種特殊定義的子圖的集合。但是目前研究人員主要將重心放在稠密子圖發(fā)現(xiàn)上，而統(tǒng)計(jì)顯著性子圖的研究經(jīng)常被忽略。由于目前存在的方法鑒定出的稠密子圖可能是沒(méi)有統(tǒng)計(jì)意義的，如何從網(wǎng)絡(luò)中尋找具有統(tǒng)計(jì)顯著性子圖，是當(dāng)前迫切需要解決的問(wèn)題。本文就統(tǒng)計(jì)顯著性子圖發(fā)現(xiàn)問(wèn)題提出了一個(gè)新穎的可擴(kuò)展的算法框架SSF，算法主要基于單個(gè)節(jié)點(diǎn)的統(tǒng)計(jì)顯著性來(lái)尋找統(tǒng)計(jì)顯著子圖的。該框架主要分為2個(gè)模塊：統(tǒng)計(jì)顯著子圖發(fā)現(xiàn)，

3、和結(jié)果去冗余處理。在統(tǒng)計(jì)顯著子圖發(fā)現(xiàn)方面，首先確定一個(gè)種子節(jié)點(diǎn)，使用該節(jié)點(diǎn)構(gòu)建初始子圖，之后通過(guò)循環(huán)迭代尋找一個(gè)統(tǒng)計(jì)顯著性子圖，循環(huán)上述過(guò)程，直到?jīng)]有種子節(jié)點(diǎn)可選擇為止，此時(shí)尋找到的所有的子圖即為統(tǒng)計(jì)顯著子圖。實(shí)際上，單個(gè)迭代過(guò)程其實(shí)是一個(gè)多重假設(shè)檢驗(yàn)的過(guò)程，采用FWER來(lái)控制錯(cuò)誤率。在結(jié)果去冗余方面，將結(jié)果冗余轉(zhuǎn)化為集合覆蓋問(wèn)題，采用貪心的算法來(lái)得到近似解，從而過(guò)濾掉大量的冗余結(jié)果。本文基于仿真數(shù)據(jù)以及真實(shí)數(shù)據(jù)做了一系列的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)