【摘要】：圖作為一種能有效描述現(xiàn)實(shí)世界中各類實(shí)體之間復(fù)雜關(guān)系的數(shù)據(jù)結(jié)構(gòu),被廣泛地應(yīng)用于社會(huì)關(guān)系網(wǎng)絡(luò)、合著者網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)等實(shí)際領(lǐng)域。隨著這些新興大規(guī)模網(wǎng)絡(luò)的快速發(fā)展,相關(guān)的各類應(yīng)用不斷地涌現(xiàn)和豐富,圖數(shù)據(jù)也急劇地增長(zhǎng)和頻繁地更新,使得對(duì)大規(guī)模圖的處理需求也愈加迫切。密集子圖查詢是圖數(shù)據(jù)處理中的熱點(diǎn)研究問(wèn)題,在復(fù)雜網(wǎng)絡(luò)分析中扮演著非常重要的角色。給定一個(gè)圖,密集子圖查詢旨在尋找到有一定聯(lián)系緊密程度的子圖。然而,大部分現(xiàn)有的密集子圖查詢方法沒(méi)有考慮頂點(diǎn)的權(quán)值的影響,在許多現(xiàn)實(shí)圖中,頂點(diǎn)有不同重要性。例如,目前社交網(wǎng)絡(luò)中,有很多QQ群,微信群等等,如何計(jì)算一定范圍內(nèi)平均聯(lián)系最密集的群可以轉(zhuǎn)化為頂點(diǎn)加權(quán)圖的最密集子圖問(wèn)題。而一個(gè)群的人數(shù)可以作為一個(gè)圖的頂點(diǎn)的權(quán)值。本文引進(jìn)了頂點(diǎn)加權(quán)圖的最密集子圖問(wèn)題,并提出計(jì)算頂點(diǎn)加權(quán)圖的最密集子圖的多項(xiàng)式時(shí)間算法。提出的算法的基本思想是:給定一個(gè)頂點(diǎn)加權(quán)圖G,假設(shè)最密集子圖的密度為D,給D一個(gè)猜測(cè)的值為g,然后構(gòu)建一個(gè)無(wú)向圖,并且建立這個(gè)g值與該圖一個(gè)最小割值的關(guān)系,然后通過(guò)二分法查找逐步求解D的值,最終找到頂點(diǎn)加權(quán)圖G的最密集子圖。進(jìn)一步分析了該算法的時(shí)間復(fù)雜度和證明了該算法是正確的。然后通過(guò)仿真實(shí)驗(yàn)和實(shí)際圖數(shù)據(jù)的實(shí)驗(yàn)來(lái)驗(yàn)證算法的有效性,得到相關(guān)結(jié)論。并且針對(duì)數(shù)據(jù)量比較大的頂點(diǎn)加權(quán)圖的最密集子圖問(wèn)題,提出了一種基于貪心策略的近似算法,該算法通過(guò)不斷的迭代刪除掉平均最小值的頂點(diǎn),以得到近似的密集子圖,并且證明了這個(gè)近似算法的近似比。
【圖文】：

圖 1-1 中國(guó)網(wǎng)民規(guī)模和互聯(lián)網(wǎng)普及率[1]ig.1-1 The scale of Chinese netizens and Internet penetration[1]

1圖 1-2 中國(guó)手機(jī)網(wǎng)民規(guī)模及其占網(wǎng)民比例[1]Fig.1-2 The scale and proportion of mobile netizens[1]
【學(xué)位授予單位】：廣州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 苑春佼;;《吉祥多子圖》臨摹[J];大眾文藝;2018年10期

2 魯宗貴;;吉祥多子圖頁(yè)[J];中國(guó)書(shū)畫(huà);2018年09期

3 印安濤;錢(qián)鋼;施歡歡;;在復(fù)雜網(wǎng)絡(luò)中查找k個(gè)有限重疊的密集子圖[J];計(jì)算機(jī)應(yīng)用與軟件;2016年12期

4 魯宗貴;;吉祥多子圖[J];文藝研究;2017年03期

5 梁瑤;;吉祥多子圖[J];美與時(shí)代(中);2017年06期

6 魯宗貴;;《吉祥多子圖》[J];老年教育(書(shū)畫(huà)藝術(shù));2016年01期

7 王苗苗;;《吉祥多子圖》[J];明日風(fēng)尚;2016年08期

8 周姍;;《吉祥多子圖》[J];參花(上);2016年06期

9 楊利民;圖K_n~k和C_n~t的理想子圖的計(jì)數(shù)[J];大理師專學(xué)報(bào)(自然科學(xué)版);1995年01期

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

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

1 劉桂珍;徐周波;;最大公共子圖問(wèn)題的約束符號(hào)求解技術(shù)[A];廣西計(jì)算機(jī)學(xué)會(huì)2016年學(xué)術(shù)年會(huì)論文集[C];2016年

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

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

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

5 陳榮斯;;非正則冠狀系統(tǒng)[A];面向21世紀(jì)的科技進(jìn)步與社會(huì)經(jīng)濟(jì)發(fā)展（上冊(cè)）[C];1999年

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

7 韓璐;王朝坤;阮文靜;歐曉平;仇萍;;基于MapReduce的不確定子圖查詢處理[A];第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

8 周楊;王峰;;FSM——基于子圖同構(gòu)和結(jié)構(gòu)同構(gòu)的頻繁子圖挖掘算法[A];第二十四屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2007年

9 張麗麗;殷兆麟;張愛(ài)娟;王竹曉;;以結(jié)點(diǎn)為中心的WordNet子圖的可視化[A];2006年全國(guó)開(kāi)放式分布與并行計(jì)算學(xué)術(shù)會(huì)議論文集（二）[C];2006年

相關(guān)重要報(bào)紙文章 前1條

1 王圣立;“五子圖”罐再現(xiàn)成化風(fēng)彩[N];中國(guó)商報(bào);2003年

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

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

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

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

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

5 鄒磊;圖數(shù)據(jù)庫(kù)中的子圖查詢算法研究[D];華中科技大學(xué);2009年

6 崔耀祖;基于復(fù)雜網(wǎng)絡(luò)邊的密度探索社團(tuán)結(jié)構(gòu)算法研究[D];大連理工大學(xué);2016年

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

8 馬登舉;曲面的極小禁用子圖與圖的虧格[D];華東師范大學(xué);2011年

9 石海佳;基于復(fù)雜網(wǎng)絡(luò)的產(chǎn)業(yè)生態(tài)系統(tǒng)結(jié)構(gòu)復(fù)雜性研究[D];清華大學(xué);2015年

10 洪艷梅;圖連通度與非分離子圖[D];上海大學(xué);2012年

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

1 鄒艷梅;關(guān)于圖的Hamilton性的禁用子圖條件[D];華東師范大學(xué);2018年

2 閆靚;穩(wěn)定頻繁子圖挖掘算法研究[D];遼寧大學(xué);2018年

3 姜麗雁;大規(guī)模動(dòng)態(tài)有向標(biāo)簽圖子圖查詢方法研究[D];遼寧大學(xué);2018年

4 劉鐘凌;頂點(diǎn)加權(quán)圖的最密集子圖算法設(shè)計(jì)與實(shí)現(xiàn)[D];廣州大學(xué);2018年

5 陳科第;基于頻繁子圖模式挖掘的群體性抗議事件檢測(cè)技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2016年

6 張迎;面向大圖數(shù)據(jù)的子圖相似匹配算法研究與實(shí)現(xiàn)[D];東北大學(xué);2015年

7 王凱;基于MapReduce的圖數(shù)據(jù)庫(kù)頻繁子圖挖掘[D];華中科技大學(xué);2016年

8 賈俊;不確定圖數(shù)據(jù)庫(kù)上基于預(yù)裁剪的頻繁子圖挖掘[D];華中科技大學(xué);2016年

9 劉文艷;基于深度優(yōu)先策略的頻繁導(dǎo)出子圖挖掘算法[D];西安電子科技大學(xué);2009年

10 朱杰;k核心子圖查詢算法研究[D];燕山大學(xué);2016年

，

本文編號(hào)：2684136