基于k-truss的圖社區(qū)發(fā)現(xiàn)算法研究.pdf

1、隨著現(xiàn)代化信息技術(shù)的迅猛發(fā)展，圖社區(qū)發(fā)現(xiàn)廣泛應(yīng)用于社交網(wǎng)絡(luò)、生物學、語義網(wǎng)和模式識別等領(lǐng)域。團問題是近幾年提出的圖社區(qū)發(fā)現(xiàn)問題的一個分支，查找極大k-truss是團問題的一種基本解決方法，但是現(xiàn)有的k-truss計算方法不夠高效。本文重點研究如何高效求解極大k-truss問題，通過對現(xiàn)有基于內(nèi)存的極大k-truss算法進行分析，發(fā)現(xiàn)現(xiàn)有算法存在過濾效果差、求解過程中存在大量冗余計算以及無法處理大圖等問題。具體研究內(nèi)容如下。
　　首

2、先，針對已有的基于內(nèi)存的極大k-truss算法在過濾階段存在過濾效果差的問題，考慮到網(wǎng)絡(luò)圖中頂點度越高越可能形成極大k-truss，提出基于頂點度的過濾策略和以此為基礎(chǔ)的算法，在同樣的時間復(fù)雜度上減少了計算量，縮短了查找時間。
　　其次，針對現(xiàn)存的方法在計算過程中存在大量冗余計算以及不能有效處理大圖的問題，提出了基于下界值的極大k-truss算法和基于上界值的極大k-truss算法。前者通過將大圖劃分成小圖以及為圖中的每條邊確定一