雙網(wǎng)絡(luò)由具有相同頂點集合但不同邊集合的物理圖和概念圖構(gòu)成,能夠反映頂點間不同層面的交互關(guān)系.雙網(wǎng)絡(luò)中稠密子圖發(fā)現(xiàn)問題旨在發(fā)現(xiàn)物理圖中連通而概念圖中稠密的子圖,在協(xié)作者網(wǎng)絡(luò)分析、社區(qū)發(fā)現(xiàn)和疾病功能團檢測等方面具有廣泛應(yīng)用.但現(xiàn)有稠密子圖模型存在以下問題:(1)基于最密集子圖模型的稠密子圖發(fā)現(xiàn)問題本質(zhì)上是NP-難的,導(dǎo)致精確的子圖發(fā)現(xiàn)算法在效率上存在很大問題;(2)基于k-核的模型雖然解決了效率問題,但是發(fā)現(xiàn)的稠密子圖并不真正"稠密".針對以上問題,本文(1)提出了k-連通truss子圖(k-CT)模型.該模型更加稠密,因此允許子圖間存在重疊;(2)為了發(fā)現(xiàn)k-連通truss子圖,提出了一種高效的精確亞線性算法用于發(fā)現(xiàn)雙網(wǎng)絡(luò)中所有的k-CT子圖;(3)基于k-CT子圖,提出了最大連通truss子圖(MCT)概念,對當前k-CT子圖不存在任何非空(k+1)-CT子圖;(4)提出了自頂向下、自底向上和二分法三種不同策略的MCT子圖發(fā)現(xiàn)算法.大量基于真實和合成雙網(wǎng)絡(luò)數(shù)據(jù)的實驗結(jié)果證明了本文提出算法的高效性和有效性.

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


本文編號：3894078