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

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

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