隨著信息技術(shù)的發(fā)展,大量的數(shù)據(jù)使用圖來建模實(shí)體之間的關(guān)系。從復(fù)雜的圖數(shù)據(jù)中挖掘出有效的信息具有重要的理論意義和應(yīng)用價(jià)值。稠密子圖抽取是圖數(shù)據(jù)挖掘的基本任務(wù)之一,目標(biāo)在于從復(fù)雜的圖中,抽取出結(jié)點(diǎn)間連接緊密的子圖,被廣泛地應(yīng)用在社交網(wǎng)絡(luò)、生物信息學(xué)和社會學(xué)等領(lǐng)域中。本文提出一種基于最大加權(quán)k-團(tuán)密度的稠密子圖抽取方法。首先定義了加權(quán)k-團(tuán)密度來衡量子圖的稠密程度,然后提出了最大加權(quán)k-團(tuán)密度問題,一種新的稠密子圖抽取方式。對于最大加權(quán)k-團(tuán)密度問題,本文設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的精確算法,通過將問題分解為一系列的最小割問題來求解。同時(shí),本文還設(shè)計(jì)了一個(gè)更高效的近似算法,并證明了該近似算法的近似比。在大量數(shù)據(jù)集上的實(shí)驗(yàn)表明,提出的基于最大加權(quán)k-團(tuán)密度的稠密子圖抽取方法能夠有效地抽取出稠密子圖,并且抽取出的子圖的密度都要優(yōu)于現(xiàn)有的稠密子圖抽取方法。最后,本文將稠密子圖抽取方法應(yīng)用于異常檢測的特征選擇任務(wù)上。通過構(gòu)造特征異常圖,來捕獲特征本身和特征對組合的異常度。在特征異常圖上使用提出的稠密子圖抽取算法進(jìn)行稠密子圖抽取,抽取出的子圖頂點(diǎn)即代表與異常檢測相關(guān)的特征。實(shí)驗(yàn)表明,該算法能夠有效過濾... 

【文章來源】：華南理工大學(xué)廣東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：67 頁

【學(xué)位級別】：碩士

【部分圖文】：

桶隊(duì)列結(jié)構(gòu)示意圖

華南理工大學(xué)碩士學(xué)位論文14就將以父節(jié)點(diǎn)為根的子樹，從樹中移除，掛在根鏈表中。同時(shí)，如果修改后的值比當(dāng)前min指針指向的節(jié)點(diǎn)值還小，需要更新min指針。整個(gè)操作的時(shí)間復(fù)雜度為(1)。圖2-2斐波那契堆修改頂點(diǎn)示例圖2-2給出了修改節(jié)點(diǎn)的值的操作過程。節(jié)點(diǎn)填充白色，表示標(biāo)志位為假，填充黑色表示標(biāo)志位為真。對節(jié)點(diǎn)藍(lán)色方框內(nèi)的節(jié)點(diǎn)的值進(jìn)行減少，變?yōu)?。由于破壞了最小堆性質(zhì)，因此將以其為根的子樹，整個(gè)掛到根鏈表中，更新父節(jié)點(diǎn)的標(biāo)志位為真，所以值為7的節(jié)點(diǎn)被填充上黑色。而因?yàn)?比當(dāng)前min指針指向的4還小，因此，更新min指針指向3。而斐波那契堆刪除最小節(jié)點(diǎn)是最復(fù)雜的操作。首先把最小節(jié)點(diǎn)的所有子樹都直接掛在根鏈表中。接著和二項(xiàng)堆類似，需要將所有度相等的樹合并，直到?jīng)]有度相等的樹存在。整個(gè)操作的時(shí)間復(fù)雜度為(log).2.3稠密子圖抽取基準(zhǔn)算法在這個(gè)小節(jié)中，主要介紹常用的幾種稠密子圖抽取算法。這些算法將會在實(shí)驗(yàn)小節(jié)中和本文提出的算法，在大量數(shù)據(jù)集上進(jìn)行對比�；谶叺某槿》椒℅oldberg[12]提出平均邊度1來衡量一個(gè)子圖的稠密程度，并提出了最大平均邊度問題，即在給定圖中找到一個(gè)平均邊度最大的子圖。通過構(gòu)造一個(gè)特殊的流網(wǎng)絡(luò)，將最大化平均邊度的優(yōu)化問題轉(zhuǎn)化為一系列在流網(wǎng)絡(luò)上的最大流最小割問題來求解，通過二分法不斷逼近圖中最稠密的子圖的平均邊度。這個(gè)基于最大平均邊度的稠密子圖抽取算法被稱為DS算法（densestsubgraph）。

華南理工大學(xué)碩士學(xué)位論文16定義2-2（TGDS問題）給定一個(gè)無向圖1=(1,1)，在其構(gòu)造的三角形圖′=(′,′)中找到一個(gè)子圖，使得平均頂點(diǎn)權(quán)重最大：maxV′∑()∈||(2-9)其中頂點(diǎn)的權(quán)重()被定義為頂點(diǎn)在圖1所對應(yīng)的三角形的邊集合中，參與的三角形數(shù)量最小的邊，其參與的三角形個(gè)數(shù)。對于TGDS問題，Nikolentzos通過二分法搜索最大密度，將最大化三角形圖密度函數(shù)分解為一系列超模優(yōu)化，該算法簡稱為精確TGDS算法。精確TGDS算法的整體算法復(fù)雜度較高，為(||32+(|()|5(|()|+||)+|()|6)log|()|)。圖2-3輸入圖轉(zhuǎn)換成三角形圖示例Nikolentzos同時(shí)也提供了一種基于貪心策略的近似算法。在該貪心算法的每次迭代中，都從三角形圖′中選擇權(quán)重最小的頂點(diǎn)從圖中刪除，直到刪除所有的頂點(diǎn)。然后，保留下迭代刪除過程中產(chǎn)生的子圖中三角形圖密度最高的作為稠密子圖�；跍�(zhǔn)團(tuán)的抽取方法Tsourakakis[16]使用了準(zhǔn)團(tuán)密度來表示圖的稠密程度，給定一個(gè)無向圖=(,)和參數(shù)α∈(0,1)，V1V，定義準(zhǔn)團(tuán)密度為α(V1)=|E1|α(|V1|2)(2-10)其中E1是由頂點(diǎn)集V1誘導(dǎo)的子圖1=(1,1)的邊集。參數(shù)α控制抽取的稠密子圖的稠密程度的參考值�；跍�(zhǔn)團(tuán)密度，Tsourakakis提出了最優(yōu)準(zhǔn)團(tuán)問題：定義2-3（最優(yōu)準(zhǔn)團(tuán)問題）給定一個(gè)無向圖1=(1,1)和參數(shù)，找到一個(gè)子圖=(,)使得準(zhǔn)團(tuán)密度最大:maxV1()(2-11)


本文編號：3320862