緊密子圖挖掘是圖數(shù)據(jù)分析領(lǐng)域的研究熱點(diǎn),可用于社區(qū)發(fā)現(xiàn)、分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及網(wǎng)絡(luò)行為和功能預(yù)測(cè)等。圖中頂點(diǎn)核值是反映頂點(diǎn)所在子圖緊密性的重要指標(biāo),被廣泛應(yīng)用于緊密子圖挖掘。以往的研究多集中于靜態(tài)圖中核值計(jì)算,在更為常見的動(dòng)態(tài)數(shù)據(jù)圖中如何避免重復(fù)計(jì)算,實(shí)現(xiàn)動(dòng)態(tài)核值維護(hù),因多邊插入/刪除時(shí)頂點(diǎn)核值變化量難以確定等難題,還未有高效算法提出。為解決上述難題,基于邊分組思想的核值維護(hù)算法得以提出。根據(jù)一定約束條件將插入/刪除的邊分為多個(gè)組,使得同一個(gè)組內(nèi)的邊插入/刪除時(shí)造成的頂點(diǎn)核值變化量可確定,將多邊更新時(shí)的核值維護(hù)問題分解為邊分組和尋找核值變化的頂點(diǎn)兩個(gè)子問題,從而高效解決動(dòng)態(tài)核值更新問題。更具體地,通過證明滿足“匹配”和“優(yōu)邊集”性質(zhì)的邊集在被同時(shí)處理時(shí),能夠保證頂點(diǎn)的核值變化量為確定值,給出基于“匹配”和“優(yōu)邊集”兩種不同的邊分組策略,得到高效核值維護(hù)算法。其中,基于匹配的算法具有更少的預(yù)處理時(shí)間,而基于優(yōu)邊集的算法可同時(shí)處理更多的邊,減少處理輪數(shù)。相比于傳統(tǒng)基于單邊處理算法的多邊順序處理方式,基于分組策略的處理算法不僅極大降低核值更新的時(shí)間,提高核值更新效率,而且可以有效減少單邊處理算... 

【文章來源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

包含0,1,2,3核的圖

圖 1-2 輔助數(shù)組 vert, pos, bin 的對(duì)應(yīng)關(guān)系作者考慮了當(dāng)圖太大無法放入內(nèi)存中的情況，e，該算法采用自頂向下的方法，首先計(jì)算核值較核值。算法主要包括三個(gè)部分：一方面是一個(gè)頂點(diǎn)核值上界的機(jī)制，以及一個(gè)遞歸的自頂向遍歷圖一次便可以將圖分成若干個(gè)小塊，這樣載入內(nèi)存。估計(jì)頂點(diǎn)核值上界的機(jī)制保證了自

圖 1-3 圖中同時(shí)插入兩條邊內(nèi)容工作如下：究了現(xiàn)有的核值維護(hù)算法，介紹了相關(guān)算法的在的問題，提出了同時(shí)處理多條邊的核值維護(hù)單邊核值維護(hù)算法處理多邊插入/刪除時(shí)存在出了一種能夠解決多條邊插入/刪除的方法。其除的邊根據(jù)一定的約束條件分成若干組，每次然后進(jìn)行核值更新。通過理論論證，本文證明，可以保證圖中所有頂點(diǎn)的核值變化最多為值需要更新的頂點(diǎn)。解決思路，本文首先提出一種稱為“匹配”的邊分成若干匹配，通過理論證明了一個(gè)匹配


本文編號(hào)：3000071