稠密子圖抽取及其應用
發(fā)布時間：2021-08-04 02:58
隨著信息技術(shù)的發(fā)展,大量的數(shù)據(jù)使用圖來建模實體之間的關(guān)系。從復雜的圖數(shù)據(jù)中挖掘出有效的信息具有重要的理論意義和應用價值。稠密子圖抽取是圖數(shù)據(jù)挖掘的基本任務之一,目標在于從復雜的圖中,抽取出結(jié)點間連接緊密的子圖,被廣泛地應用在社交網(wǎng)絡、生物信息學和社會學等領域中。本文提出一種基于最大加權(quán)k-團密度的稠密子圖抽取方法。首先定義了加權(quán)k-團密度來衡量子圖的稠密程度,然后提出了最大加權(quán)k-團密度問題,一種新的稠密子圖抽取方式。對于最大加權(quán)k-團密度問題,本文設計了一個多項式時間復雜度的精確算法,通過將問題分解為一系列的最小割問題來求解。同時,本文還設計了一個更高效的近似算法,并證明了該近似算法的近似比。在大量數(shù)據(jù)集上的實驗表明,提出的基于最大加權(quán)k-團密度的稠密子圖抽取方法能夠有效地抽取出稠密子圖,并且抽取出的子圖的密度都要優(yōu)于現(xiàn)有的稠密子圖抽取方法。最后,本文將稠密子圖抽取方法應用于異常檢測的特征選擇任務上。通過構(gòu)造特征異常圖,來捕獲特征本身和特征對組合的異常度。在特征異常圖上使用提出的稠密子圖抽取算法進行稠密子圖抽取,抽取出的子圖頂點即代表與異常檢測相關(guān)的特征。實驗表明,該算法能夠有效過濾...
【文章來源】：華南理工大學廣東省 211工程院校 985工程院校 教育部直屬院校
【文章頁數(shù)】：67 頁
【學位級別】：碩士
【部分圖文】：
桶隊列結(jié)構(gòu)示意圖
華南理工大學碩士學位論文14就將以父節(jié)點為根的子樹，從樹中移除，掛在根鏈表中。同時，如果修改后的值比當前min指針指向的節(jié)點值還小，需要更新min指針。整個操作的時間復雜度為(1)。圖2-2斐波那契堆修改頂點示例圖2-2給出了修改節(jié)點的值的操作過程。節(jié)點填充白色，表示標志位為假，填充黑色表示標志位為真。對節(jié)點藍色方框內(nèi)的節(jié)點的值進行減少，變?yōu)?。由于破壞了最小堆性質(zhì)，因此將以其為根的子樹，整個掛到根鏈表中，更新父節(jié)點的標志位為真，所以值為7的節(jié)點被填充上黑色。而因為3比當前min指針指向的4還小，因此，更新min指針指向3。而斐波那契堆刪除最小節(jié)點是最復雜的操作。首先把最小節(jié)點的所有子樹都直接掛在根鏈表中。接著和二項堆類似，需要將所有度相等的樹合并，直到?jīng)]有度相等的樹存在。整個操作的時間復雜度為(log).2.3稠密子圖抽取基準算法在這個小節(jié)中，主要介紹常用的幾種稠密子圖抽取算法。這些算法將會在實驗小節(jié)中和本文提出的算法，在大量數(shù)據(jù)集上進行對比。基于邊的抽取方法Goldberg[12]提出平均邊度1來衡量一個子圖的稠密程度，并提出了最大平均邊度問題，即在給定圖中找到一個平均邊度最大的子圖。通過構(gòu)造一個特殊的流網(wǎng)絡，將最大化平均邊度的優(yōu)化問題轉(zhuǎn)化為一系列在流網(wǎng)絡上的最大流最小割問題來求解，通過二分法不斷逼近圖中最稠密的子圖的平均邊度。這個基于最大平均邊度的稠密子圖抽取算法被稱為DS算法（densestsubgraph）。
華南理工大學碩士學位論文16定義2-2（TGDS問題）給定一個無向圖1=(1,1)，在其構(gòu)造的三角形圖′=(′,′)中找到一個子圖，使得平均頂點權(quán)重最大：maxV′∑()∈||(2-9)其中頂點的權(quán)重()被定義為頂點在圖1所對應的三角形的邊集合中，參與的三角形數(shù)量最小的邊，其參與的三角形個數(shù)。對于TGDS問題，Nikolentzos通過二分法搜索最大密度，將最大化三角形圖密度函數(shù)分解為一系列超模優(yōu)化，該算法簡稱為精確TGDS算法。精確TGDS算法的整體算法復雜度較高，為(||32+(|()|5(|()|+||)+|()|6)log|()|)。圖2-3輸入圖轉(zhuǎn)換成三角形圖示例Nikolentzos同時也提供了一種基于貪心策略的近似算法。在該貪心算法的每次迭代中，都從三角形圖′中選擇權(quán)重最小的頂點從圖中刪除，直到刪除所有的頂點。然后，保留下迭代刪除過程中產(chǎn)生的子圖中三角形圖密度最高的作為稠密子圖。基于準團的抽取方法Tsourakakis[16]使用了準團密度來表示圖的稠密程度，給定一個無向圖=(,)和參數(shù)α∈(0,1)，V1V，定義準團密度為α(V1)=|E1|α(|V1|2)(2-10)其中E1是由頂點集V1誘導的子圖1=(1,1)的邊集。參數(shù)α控制抽取的稠密子圖的稠密程度的參考值�；跍蕡F密度，Tsourakakis提出了最優(yōu)準團問題：定義2-3（最優(yōu)準團問題）給定一個無向圖1=(1,1)和參數(shù)，找到一個子圖=(,)使得準團密度最大:maxV1()(2-11)
本文編號：3320862
【文章來源】：華南理工大學廣東省 211工程院校 985工程院校 教育部直屬院校
【文章頁數(shù)】：67 頁
【學位級別】：碩士
【部分圖文】：
桶隊列結(jié)構(gòu)示意圖
華南理工大學碩士學位論文14就將以父節(jié)點為根的子樹，從樹中移除，掛在根鏈表中。同時，如果修改后的值比當前min指針指向的節(jié)點值還小，需要更新min指針。整個操作的時間復雜度為(1)。圖2-2斐波那契堆修改頂點示例圖2-2給出了修改節(jié)點的值的操作過程。節(jié)點填充白色，表示標志位為假，填充黑色表示標志位為真。對節(jié)點藍色方框內(nèi)的節(jié)點的值進行減少，變?yōu)?。由于破壞了最小堆性質(zhì)，因此將以其為根的子樹，整個掛到根鏈表中，更新父節(jié)點的標志位為真，所以值為7的節(jié)點被填充上黑色。而因為3比當前min指針指向的4還小，因此，更新min指針指向3。而斐波那契堆刪除最小節(jié)點是最復雜的操作。首先把最小節(jié)點的所有子樹都直接掛在根鏈表中。接著和二項堆類似，需要將所有度相等的樹合并，直到?jīng)]有度相等的樹存在。整個操作的時間復雜度為(log).2.3稠密子圖抽取基準算法在這個小節(jié)中，主要介紹常用的幾種稠密子圖抽取算法。這些算法將會在實驗小節(jié)中和本文提出的算法，在大量數(shù)據(jù)集上進行對比。基于邊的抽取方法Goldberg[12]提出平均邊度1來衡量一個子圖的稠密程度，并提出了最大平均邊度問題，即在給定圖中找到一個平均邊度最大的子圖。通過構(gòu)造一個特殊的流網(wǎng)絡，將最大化平均邊度的優(yōu)化問題轉(zhuǎn)化為一系列在流網(wǎng)絡上的最大流最小割問題來求解，通過二分法不斷逼近圖中最稠密的子圖的平均邊度。這個基于最大平均邊度的稠密子圖抽取算法被稱為DS算法（densestsubgraph）。
華南理工大學碩士學位論文16定義2-2（TGDS問題）給定一個無向圖1=(1,1)，在其構(gòu)造的三角形圖′=(′,′)中找到一個子圖，使得平均頂點權(quán)重最大：maxV′∑()∈||(2-9)其中頂點的權(quán)重()被定義為頂點在圖1所對應的三角形的邊集合中，參與的三角形數(shù)量最小的邊，其參與的三角形個數(shù)。對于TGDS問題，Nikolentzos通過二分法搜索最大密度，將最大化三角形圖密度函數(shù)分解為一系列超模優(yōu)化，該算法簡稱為精確TGDS算法。精確TGDS算法的整體算法復雜度較高，為(||32+(|()|5(|()|+||)+|()|6)log|()|)。圖2-3輸入圖轉(zhuǎn)換成三角形圖示例Nikolentzos同時也提供了一種基于貪心策略的近似算法。在該貪心算法的每次迭代中，都從三角形圖′中選擇權(quán)重最小的頂點從圖中刪除，直到刪除所有的頂點。然后，保留下迭代刪除過程中產(chǎn)生的子圖中三角形圖密度最高的作為稠密子圖。基于準團的抽取方法Tsourakakis[16]使用了準團密度來表示圖的稠密程度，給定一個無向圖=(,)和參數(shù)α∈(0,1)，V1V，定義準團密度為α(V1)=|E1|α(|V1|2)(2-10)其中E1是由頂點集V1誘導的子圖1=(1,1)的邊集。參數(shù)α控制抽取的稠密子圖的稠密程度的參考值�；跍蕡F密度，Tsourakakis提出了最優(yōu)準團問題：定義2-3（最優(yōu)準團問題）給定一個無向圖1=(1,1)和參數(shù)，找到一個子圖=(,)使得準團密度最大:maxV1()(2-11)
本文編號：3320862
本文鏈接：http://sikaile.net/kejilunwen/yysx/3320862.html
最近更新
教材專著
