本文關(guān)鍵詞：不確定圖上的Top-k稠密子圖挖掘算法

  更多相關(guān)文章： 不確定圖 top-k稠密子圖 期望稠密度 分支界限搜索 數(shù)據(jù)挖掘

【摘要】：該文研究了從不確定圖上挖掘top-k稠密子圖的問(wèn)題.由于圖數(shù)據(jù)具有內(nèi)生不確定性,確定圖上稠密子圖的定義和挖掘算法在不確定圖上均不適用.因此,該文提出了不確定圖上期望稠密度的概念,并給出了其在多項(xiàng)式時(shí)間內(nèi)的計(jì)算方法.基于此,該文定義了不確定圖中導(dǎo)出子圖之間的一種偏序關(guān)系.利用該偏序關(guān)系,將不確定圖中的導(dǎo)出子圖有效地組織成一棵搜索樹(shù).該文嚴(yán)格證明了此搜索樹(shù)中可以完整無(wú)重復(fù)地覆蓋不確定圖上的所有導(dǎo)出子圖.據(jù)此,該文提出了針對(duì)此搜索樹(shù)的一種分支界限搜索算法DS,用于精確挖掘top-k稠密子圖.該文還提出了不相交top-k稠密子圖的概念,并給出了一種基于束搜索的啟發(fā)式近似搜索算法LS.在多組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,文中提出的DS算法具有很高的效率和很好的擴(kuò)展性,可用于處理大規(guī)模圖數(shù)據(jù).啟發(fā)式近似搜索算法LS可以快速發(fā)現(xiàn)不相交top-k稠密子圖.
【作者單位】： 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【關(guān)鍵詞】： 不確定圖 top-k稠密子圖 期望稠密度 分支界限搜索 數(shù)據(jù)挖掘
【基金】：國(guó)家自然科學(xué)基金(61173023,61532015)資助
【分類號(hào)】：TP311.13
【正文快照】： 博士研究生,主要研究方向?yàn)閳D數(shù)據(jù)管理、數(shù)據(jù)庫(kù).E-mail:rongzhumr@gmail.com.鄒兆年,男,1979年生,博士,副教授,中國(guó)計(jì)算機(jī)學(xué)會(huì)(CCF)會(huì)員,主要研究方向?yàn)閿?shù)據(jù)庫(kù)、數(shù)據(jù)挖掘.李建中,男,1950年生,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)、無(wú)線傳感器網(wǎng)絡(luò).1引言近年來(lái),在科研和應(yīng)用

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王映龍;楊s，

本文編號(hào)：1005983