本文選題：k核心子圖 + 全局搜索　； 參考：《燕山大學(xué)》2016年碩士論文

【摘要】：給定圖G、查詢結(jié)點(diǎn)v以及用戶指定的k值,k核心子圖查詢用于從G中返回包含結(jié)點(diǎn)v且任意結(jié)點(diǎn)的度均大于或者等于k的一個(gè)子圖。k核心子圖主要應(yīng)用于朋友推薦、社交網(wǎng)絡(luò)中的廣告宣傳、疾病控制和語義擴(kuò)張等方面。在此從以下幾個(gè)方面對k核心子圖查詢問題進(jìn)行了深入研究。首先,通過深入分析現(xiàn)有的k核心子圖查詢處理方法,發(fā)現(xiàn)現(xiàn)有算法在生成k核心子圖時(shí)存在冗余遍歷問題。其次,提出對圖進(jìn)行預(yù)處理的pre_CST算法。該算法對每個(gè)結(jié)點(diǎn)的鄰居結(jié)點(diǎn)按度數(shù)進(jìn)行排序,同時(shí)記錄鄰居中度數(shù)大于或者等于k的結(jié)點(diǎn)數(shù)目,以便為后續(xù)k核心子圖求解提供便利。再次,提出高效的k核心子圖求解算法CST。該算法充分利用預(yù)處理得到的信息,提出三種避免冗余遍歷的策略,包括(1)當(dāng)遍歷當(dāng)前結(jié)點(diǎn)的鄰居結(jié)點(diǎn)時(shí),如果發(fā)現(xiàn)某個(gè)鄰居結(jié)點(diǎn)的度數(shù)小于k,那么對該結(jié)點(diǎn)之后的所有結(jié)點(diǎn)無需進(jìn)行訪問;(2)當(dāng)鄰居中度數(shù)大于或者等于k的結(jié)點(diǎn)數(shù)目小于k時(shí),當(dāng)前結(jié)點(diǎn)不會(huì)加入到候選子圖中;(3)利用優(yōu)先隊(duì)列對要加入到k核心子圖中的候選結(jié)點(diǎn)進(jìn)行排序,優(yōu)先加入與當(dāng)前k核心里有最多關(guān)聯(lián)邊的候選結(jié)點(diǎn),從而減少k核心子圖查詢時(shí)無效結(jié)點(diǎn)的加入。以上三種策略都能避免對無用結(jié)點(diǎn)的處理,從而減少冗余遍歷,提高查詢效率。最后,基于真實(shí)數(shù)據(jù)集,通過不同評價(jià)指標(biāo),對提出算法的高效性進(jìn)行了驗(yàn)證。
[Abstract]:Advertising, disease control and semantic expansion in social networks. In this paper, the query problem of k-core subgraph is studied from the following aspects. Firstly, by analyzing the existing query processing methods of k-core subgraph, it is found that the existing algorithm has redundant traversal problem in generating k-core subgraph. Secondly, the pre_CST algorithm is proposed to preprocess the graph. In this algorithm, the neighbor nodes of each node are sorted by degrees, and the number of nodes whose degree is greater than or equal to k in the neighbor is recorded, so as to facilitate the solution of subsequent k-core subgraphs. Thirdly, an efficient k-core subgraph solution algorithm, CST, is proposed. Taking full advantage of the preprocessing information, the algorithm proposes three strategies to avoid redundant traversal, including 1) when traversing the neighbor nodes of the current node. If it is found that the degree of a neighbor node is less than k, then all nodes after that node do not need to be accessed) when the number of nodes in the neighbor whose degree is greater than or equal to k is less than k, The current node will not be added to the candidate subgraph.) priority queue is used to sort the candidate node to join the k-core subgraph, and the candidate node with the most associated edges in the current k-core is added first. In order to reduce the k-core subgraph query invalid nodes added. The above three strategies can avoid the processing of useless nodes, thus reducing redundant traversal and improving query efficiency. Finally, based on the real data set, the efficiency of the proposed algorithm is verified by different evaluation indexes.
【學(xué)位授予單位】：燕山大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5;TP391.3

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 孫亮;葉淼林;;圖的子圖匹配數(shù)與圖的標(biāo)準(zhǔn)化拉普拉斯譜[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年04期

2 陳賜平;;帶虧數(shù)的[1,n]-子圖[J];北京農(nóng)業(yè)工程大學(xué)學(xué)報(bào);1987年03期

3 李學(xué)良;;有向1-因子圖[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年02期

4 李傳湘;層次結(jié)構(gòu)中封閉子圖的映射[J];數(shù)學(xué)物理學(xué)報(bào);1990年04期

5 郭思平;;立方圖中一類具有極大邊數(shù)子圖的性質(zhì)[J];云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1991年04期

6 謝力同,范紅兵;關(guān)于局部子圖可重構(gòu)性的一個(gè)新結(jié)果(英文)[J];數(shù)學(xué)進(jìn)展;1997年05期

7 龍和平,謝力同,顏謹(jǐn),劉桂真;邊型帶權(quán)核子圖的邊可重構(gòu)性[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2002年02期

8 李慰萱;;圖的結(jié)構(gòu)多項(xiàng)式與子圖恒等式[J];長沙鐵道學(xué)院學(xué)報(bào);1979年03期

9 郭知熠;關(guān)于完全k-邊可染子圖[J];華中工學(xué)院學(xué)報(bào);1985年06期

10 辛林，徐恭勤;子圖個(gè)數(shù)的計(jì)算問題[J];教學(xué)與教材研究;1994年03期

相關(guān)會(huì)議論文 前4條

1 徐以凡;;層分解和子圖識(shí)別問題[A];2001年全國數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

2 陶劍文;丁佩芬;趙杰煜;;csgIndex:一種可擴(kuò)展的對比子圖索引模型[A];第二十七屆中國控制會(huì)議論文集[C];2008年

3 吳衛(wèi)江;李國和;;Apriori算法思想在頻繁子圖挖掘中應(yīng)用的研究[A];第六屆全國信息獲取與處理學(xué)術(shù)會(huì)議論文集（2）[C];2008年

4 吳穎華;周皓峰;袁晴晴;洪銘勝;汪衛(wèi);施伯樂;;Topology:一個(gè)快速的頻繁連通子圖的挖掘算法[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

相關(guān)博士學(xué)位論文 前5條

1 李斌龍;重子圖條件下圖的Hamilton性及相關(guān)問題[D];西北工業(yè)大學(xué);2016年

2 藺厚元;禁用子圖與圖的哈密爾頓性[D];華中師范大學(xué);2012年

3 毛玲;基于層次因子圖的心電圖自動(dòng)診斷方法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

4 崔慶;Tutte子圖方法及其應(yīng)用[D];南開大學(xué);2009年

5 吳云建;一致星因子圖與籠的連通性[D];南開大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 范淦;高效的龐大圖的頻繁子圖挖掘方法研究[D];遼寧大學(xué);2015年

2 魏真真;大規(guī)模不確定圖緊密子圖挖掘算法研究[D];燕山大學(xué);2015年

3 齊寶雷;面向不確定圖數(shù)據(jù)的子圖模式挖掘算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2013年

4 王會(huì)會(huì);精確子圖數(shù)據(jù)庫查詢技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2014年

5 白楊;復(fù)雜網(wǎng)絡(luò)圖中高密度子圖檢測方法與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

6 王鵬;基于局部鄰域的最大密度子圖檢測方法研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

7 趙路;圖的Q-特征值與圖結(jié)構(gòu)[D];青海師范大學(xué);2015年

8 王璐璐;不確定圖上Top-k子圖相似性查詢技術(shù)研究[D];東北大學(xué);2014年

9 張?zhí)烀?大圖上頻繁子圖挖掘算法的研究[D];東北大學(xué);2014年

10 王峰;基于眾核平臺(tái)子圖匹配算法研究[D];北京理工大學(xué);2016年

，

本文編號(hào)：1792932