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

【摘要】：給定圖G、查詢結點v以及用戶指定的k值,k核心子圖查詢用于從G中返回包含結點v且任意結點的度均大于或者等于k的一個子圖。k核心子圖主要應用于朋友推薦、社交網(wǎng)絡中的廣告宣傳、疾病控制和語義擴張等方面。在此從以下幾個方面對k核心子圖查詢問題進行了深入研究。首先,通過深入分析現(xiàn)有的k核心子圖查詢處理方法,發(fā)現(xiàn)現(xiàn)有算法在生成k核心子圖時存在冗余遍歷問題。其次,提出對圖進行預處理的pre_CST算法。該算法對每個結點的鄰居結點按度數(shù)進行排序,同時記錄鄰居中度數(shù)大于或者等于k的結點數(shù)目,以便為后續(xù)k核心子圖求解提供便利。再次,提出高效的k核心子圖求解算法CST。該算法充分利用預處理得到的信息,提出三種避免冗余遍歷的策略,包括(1)當遍歷當前結點的鄰居結點時,如果發(fā)現(xiàn)某個鄰居結點的度數(shù)小于k,那么對該結點之后的所有結點無需進行訪問;(2)當鄰居中度數(shù)大于或者等于k的結點數(shù)目小于k時,當前結點不會加入到候選子圖中;(3)利用優(yōu)先隊列對要加入到k核心子圖中的候選結點進行排序,優(yōu)先加入與當前k核心里有最多關聯(lián)邊的候選結點,從而減少k核心子圖查詢時無效結點的加入。以上三種策略都能避免對無用結點的處理,從而減少冗余遍歷,提高查詢效率。最后,基于真實數(shù)據(jù)集,通過不同評價指標,對提出算法的高效性進行了驗證。
[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.
【學位授予單位】：燕山大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5;TP391.3

【相似文獻】

相關期刊論文 前10條

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

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

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

4 李傳湘;層次結構中封閉子圖的映射[J];數(shù)學物理學報;1990年04期

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

6 謝力同,范紅兵;關于局部子圖可重構性的一個新結果(英文)[J];數(shù)學進展;1997年05期

7 龍和平,謝力同,顏謹,劉桂真;邊型帶權核子圖的邊可重構性[J];山東大學學報(理學版);2002年02期

8 李慰萱;;圖的結構多項式與子圖恒等式[J];長沙鐵道學院學報;1979年03期

9 郭知熠;關于完全k-邊可染子圖[J];華中工學院學報;1985年06期

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

相關會議論文 前4條

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

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

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

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

相關博士學位論文 前5條

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

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

3 毛玲;基于層次因子圖的心電圖自動診斷方法研究[D];國防科學技術大學;2009年

4 崔慶;Tutte子圖方法及其應用[D];南開大學;2009年

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

相關碩士學位論文 前10條

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

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

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

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

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

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

7 趙路;圖的Q-特征值與圖結構[D];青海師范大學;2015年

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

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

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

，

本文編號：1792932