近年來,隨著互聯(lián)網(wǎng)的高速發(fā)展,社交網(wǎng)絡(luò)已經(jīng)成為了人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠?例如臉書,推特等,對社交網(wǎng)絡(luò)的研究也成為了近年來的熱點。為了衡量社交網(wǎng)絡(luò)中子圖的稠密程度,許多子圖模型被提出,例如k-core,k-truss,k-plex,完全圖(clique)等等。其中k-plex,完全圖對子圖的要求比較嚴格,而且無法在多項式時間內(nèi)求解,在實際場景中的應(yīng)用范圍相對比較局限。而k-core和k-truss是兩種比較簡單的模型,能夠在多項時間內(nèi)求解,在許多實際問題中得到了廣泛的應(yīng)用。在社交網(wǎng)絡(luò)中,用戶之間的關(guān)系強弱對社交網(wǎng)絡(luò)的穩(wěn)定性有很大的影響。用戶是否選擇繼續(xù)使用某個社交網(wǎng)絡(luò),往往受到他在這個社交網(wǎng)絡(luò)中朋友數(shù)量的影響,而用戶之間的關(guān)系,也往往受到他們之間的共同好友數(shù)量的影響。所以,對社交網(wǎng)絡(luò)中關(guān)鍵點,關(guān)鍵邊的挖掘,對社交網(wǎng)絡(luò)的維護,構(gòu)建都有著重要的意義,這也成為了近年來學(xué)術(shù)界研究的熱點。本文使用k-core,k-truss這兩種子圖模型來衡量子圖的稠密程度,并提出了兩個新問題k-core最小化問題和k-truss最小化問題來檢測社交網(wǎng)絡(luò)中的關(guān)鍵邊。給定一個圖G,一個正整數(shù)b,我們需要找到b條關(guān)鍵邊,使得刪除這b條邊后,剩余的k-core,k-truss最小。本文首先證明了這兩個問題是NP難問題,并且目標函數(shù)不具有子模性,無法在多項式時間內(nèi)得到一個有近似率保證的解。由于問題的復(fù)雜性,本文提出了一種基于貪心的啟發(fā)式算法,并且提出了一些剪枝策略加快了計算的過程。在k-truss最小化問題中,本文還提出了一種上界算法進一步提高了算法效率。最后,在多個真實社交網(wǎng)絡(luò)數(shù)據(jù)集上的對比實驗,證明了本文所提出的算法的有效性和高效性。并且本文比較了兩種模型尋找稠密子圖的效果,證明了 truss模型優(yōu)于core模型。
【學(xué)位單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TP301.6;C912.3
【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
    1.2 研究現(xiàn)狀
    1.3 本文主要內(nèi)容
    1.4 本文組織結(jié)構(gòu)
第二章 背景知識和相關(guān)工作
    2.1 準備?作
    2.2 k-core 及相關(guān)算法介紹
    2.3 k-truss 及相關(guān)算法介紹
    2.4 其他?圖模型介紹
    2.5 本章小節(jié)
第三章 基于刪邊方法的k-core最小化問題
    3.1 問題定義
    3.2 問題復(fù)雜性證明
    3.3 基礎(chǔ)算法
    3.4 剪枝策略
    3.5 實驗結(jié)果及分析
    3.6 本章小節(jié)
第四章 基于刪邊方法的k-truss最小化問題
    4.1 問題定義
    4.2 問題復(fù)雜性證明
    4.3 基礎(chǔ)算法
    4.4 剪枝策略
    4.5 上界算法
    4.6 實驗結(jié)果及分析
    4.7 本章小節(jié)
第五章 總結(jié)與展望
    5.1 本文工作總結(jié)
    5.2 未來工作展望
參考文獻
發(fā)表論文和科研情況
致謝

【相似文獻】

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

1 朱煒杰;基于k-core和k-truss模型的社交網(wǎng)絡(luò)關(guān)鍵邊檢測方法研究[D];華東師范大學(xué);2019年

2 楊李;基于擴散K-truss分解算法識別最有影響力節(jié)點及其應(yīng)用研究[D];南京郵電大學(xué);2018年

3 王巖;基于k-truss的圖社區(qū)發(fā)現(xiàn)算法研究[D];燕山大學(xué);2016年

本文編號：2856128