【摘要】：隨著互聯(lián)網(wǎng)應(yīng)用的日益普及,越來越多的大數(shù)據(jù)應(yīng)用問題采用圖來表示其數(shù)據(jù)結(jié)構(gòu)。圖(graph),也被稱為網(wǎng)絡(luò)(network),是一種重要的數(shù)據(jù)結(jié)構(gòu)。在傳統(tǒng)的圖模型中,節(jié)點(diǎn)為單一類型,例如,商品,用戶等;邊也為單一類型,表示兩個節(jié)點(diǎn)的關(guān)系,如好友關(guān)系等。社區(qū)是圖中的一組頂點(diǎn)集合,其內(nèi)部節(jié)點(diǎn)間聯(lián)系較內(nèi)部與外部節(jié)點(diǎn)間聯(lián)系更為緊密。k-核是一種社區(qū),由于其簡潔的定義和高效的算法而被廣泛采用。k-核社區(qū)發(fā)現(xiàn)和搜索是兩類基于圖的重要問題。以往對這兩類問題的研究都是基于傳統(tǒng)的圖模型。隨著應(yīng)用問題的復(fù)雜,一些問題使用傳統(tǒng)的圖模型難以表達(dá),例如,社交網(wǎng)絡(luò)中,人們想要找到物理位置接近,同時互為好友關(guān)系的那些用戶,而這種問題通常可以采用多層網(wǎng)絡(luò)中的k-核社區(qū)來建模。多層網(wǎng)絡(luò)的各層中共享頂點(diǎn),具有不同類型的邊。不同的層表示系統(tǒng)中頂點(diǎn)之間不同方面的交互關(guān)系,從而能夠表達(dá)更為廣泛的概念和更復(fù)雜的問題。因此,近年來,多層網(wǎng)絡(luò)的相關(guān)研究成為新的研究熱點(diǎn)。針對基于多層網(wǎng)絡(luò)的研究還剛剛起步,相關(guān)研究還比較少,本文研究了多層網(wǎng)絡(luò)中的連通k-核社區(qū)發(fā)現(xiàn)和搜索問題。本文提出了一種新的模型:連通k-核,用于建模多層網(wǎng)絡(luò)中的k-核社區(qū)。本文主要研究三類問題:連通k-核社區(qū)發(fā)現(xiàn)問題,最大連通k-核社區(qū)發(fā)現(xiàn)問題和連通k-核社區(qū)搜索問題。(1)連通k-核社區(qū)發(fā)現(xiàn)問題指的是給定多層網(wǎng)絡(luò)G和向量k,找到多層網(wǎng)絡(luò)上所有連通k-核。本文提出了一種近似線性的算法,用于發(fā)現(xiàn)多層網(wǎng)絡(luò)G中的所有連通k-核。(2)最大連通k-核社區(qū)發(fā)現(xiàn)問題是指找出多層網(wǎng)絡(luò)上所有最大連通k-核。最大連通k-核是圖中所有連通k-核中度數(shù)閾值k最大的連通k-核。對于多層網(wǎng)絡(luò)的特殊情況雙層網(wǎng)絡(luò),本文提出了最大連通k-核社區(qū)發(fā)現(xiàn)的自底向上和自頂向下的算法,并在最后提出了一種高效的二分搜索算法。對于一般的多層網(wǎng)絡(luò),本文提出了基于寬度優(yōu)先搜索策略的多層最大連通k-核社區(qū)發(fā)現(xiàn)的高效算法。(3)連通k-核社區(qū)搜索問題是找出圖中包含給定頂點(diǎn)集合的連通k-核的問題。在多層網(wǎng)絡(luò)中,本文設(shè)計了高效的索引結(jié)構(gòu)來查找包含一組查詢頂點(diǎn)的連通k-核�；谒岢龅乃饕Y(jié)構(gòu),本文給出了高效的查詢處理算法和多項(xiàng)式時間索引構(gòu)造算法。本文在包括引用網(wǎng)絡(luò),推薦網(wǎng)絡(luò),地理社交網(wǎng)絡(luò),社交網(wǎng)絡(luò)等多種領(lǐng)域的大型公開真實(shí)數(shù)據(jù)集對本文所提出的算法性能和有效性進(jìn)行了評估。同時,通過公開的滿足典型的社會網(wǎng)絡(luò)的模式的隨機(jī)圖生成器合成了大型合成數(shù)據(jù)集,對算法的性能和可擴(kuò)展性進(jìn)行了評估。本文的實(shí)驗(yàn)結(jié)果證實(shí)了本文提出的算法在各個場景下均具有良好的性能,在數(shù)據(jù)集規(guī)模增加時,算法仍然具有良好的可擴(kuò)展性和魯棒性,不會發(fā)生時間開銷不可接受的情況。同時,在Gowalla[7]數(shù)據(jù)集上進(jìn)行的與最稠密連通子圖[28]進(jìn)行比較的案例分析證實(shí)了本文提出的連通k-核模型具有良好的性質(zhì)。連通k-核中各個頂點(diǎn)均具有較高度數(shù),不會出現(xiàn)度數(shù)較低的離群點(diǎn),能夠更好地表示網(wǎng)絡(luò)中具有內(nèi)聚屬性的社區(qū)。
【圖文】：

山東大學(xué)碩士學(xué)位論文簡單情況，本文首先研宄了雙層網(wǎng)絡(luò)。在雙層網(wǎng)絡(luò)組分別只包含一層網(wǎng)絡(luò)，因此可以將其稱為物圖１－１中的雙層網(wǎng)絡(luò)，該網(wǎng)絡(luò)是根據(jù)社交網(wǎng)絡(luò)構(gòu)用戶之間的物理聯(lián)系，，因此被構(gòu)造為物理網(wǎng)絡(luò)。用戶之間興趣愛好的相似程度。當(dāng)相似度大于一被構(gòu)造為概念網(wǎng)絡(luò)。值得注意的是，兩個擁有相

鉀3刁
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP311.12

【相似文獻(xiàn)】

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

1 王林;李陽;周媛媛;于文濤;;基于層次覆蓋的多層網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法[J];計算機(jī)測量與控制;2018年07期

2 馬夏夏;蔡永明;;基于復(fù)雜網(wǎng)絡(luò)的鐵路-航空多層網(wǎng)絡(luò)的魯棒性研究[J];山東科學(xué);2017年05期

3 周鐵柱;周春艷;;多層網(wǎng)絡(luò)結(jié)構(gòu)系統(tǒng)安全的幾個關(guān)鍵技術(shù)[J];山西電子技術(shù);2007年01期

4 李守偉;解一葦;楊坤;龔晨;;商業(yè)銀行多層網(wǎng)絡(luò)結(jié)構(gòu)對系統(tǒng)性風(fēng)險影響研究[J];東南大學(xué)學(xué)報(哲學(xué)社會科學(xué)版);2019年04期

5 龔晨;何建敏;李守偉;;銀行多層網(wǎng)絡(luò)與系統(tǒng)性風(fēng)險研究進(jìn)展[J];現(xiàn)代經(jīng)濟(jì)探討;2018年11期

6 李守偉;文世航;王磊;;基于多層網(wǎng)絡(luò)視角的企業(yè)擔(dān)保結(jié)構(gòu)研究[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2018年04期

7 劉曉燕;王晶;單曉紅;楊娟;;基于多層網(wǎng)絡(luò)的創(chuàng)新網(wǎng)絡(luò)節(jié)點(diǎn)間技術(shù)融合機(jī)理[J];科學(xué)學(xué)研究;2019年06期

8 石兵;閔帆;周明天;李興明;;多層網(wǎng)絡(luò)抗毀機(jī)制的研究[J];計算機(jī)科學(xué);2002年01期

9 張鴻賓;;訓(xùn)練多層網(wǎng)絡(luò)的樣本數(shù)問題[J];自動化學(xué)報;1993年01期

10 陸君安;;從單層網(wǎng)絡(luò)到多層網(wǎng)絡(luò)——結(jié)構(gòu)、動力學(xué)和功能[J];現(xiàn)代物理知識;2015年04期

相關(guān)會議論文 前3條

1 鄒慶云;李樹丞;李林;李信儒;;多層網(wǎng)絡(luò)與局部連接[A];發(fā)展的信息技術(shù)對管理的挑戰(zhàn)——99’管理科學(xué)學(xué)術(shù)會議專輯（上）[C];1999年

2 胡海龍;邱倩琳;;立體多層網(wǎng)絡(luò)架構(gòu)在CBD覆蓋中的應(yīng)用[A];2012全國無線及移動通信學(xué)術(shù)大會論文集（下）[C];2012年

3 劉丁;;組合神經(jīng)網(wǎng)絡(luò)的非線性最優(yōu)控制方法[A];1993中國控制與決策學(xué)術(shù)年會論文集[C];1993年

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

1 中興通訊 龐玲;開啟融合組網(wǎng)新紀(jì)元[N];通信產(chǎn)業(yè)報;2014年

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

1 魯立;異構(gòu)多層網(wǎng)絡(luò)中資源優(yōu)化[D];華中科技大學(xué);2017年

2 朱亮;核反應(yīng)系統(tǒng)的多層網(wǎng)絡(luò)結(jié)構(gòu)特征研究[D];中國科學(xué)院研究生院(上海應(yīng)用物理研究所);2016年

3 李圓媛;基于網(wǎng)絡(luò)的復(fù)雜疾病的研究[D];武漢大學(xué);2016年

4 張曉光;網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與傳播動力學(xué)分析[D];中北大學(xué);2014年

5 蘇揚(yáng);多層通信網(wǎng)絡(luò)業(yè)務(wù)流疏導(dǎo)問題研究[D];西安電子科技大學(xué);2007年

6 顏登程;基于人類動力學(xué)和復(fù)雜網(wǎng)絡(luò)的開發(fā)者行為及興趣研究[D];中國科學(xué)技術(shù)大學(xué);2017年

7 王贏飛;復(fù)雜動力網(wǎng)絡(luò)的拓?fù)渥R別：從單層到多層[D];武漢大學(xué);2016年

8 王云艷;基于多層網(wǎng)絡(luò)模型的全極化SAR圖像分類[D];武漢大學(xué);2015年

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

1 岳靈茜;多層網(wǎng)絡(luò)中的連通k-核社區(qū)發(fā)現(xiàn)和搜索問題研究[D];山東大學(xué);2019年

2 安寧波;多層網(wǎng)絡(luò)上傳播動力學(xué)與偏好游走的相互作用[D];安徽大學(xué);2019年

3 劉倩;多層網(wǎng)絡(luò)中的混沌同步[D];北京郵電大學(xué);2019年

4 王德華;基于機(jī)器學(xué)習(xí)及多層網(wǎng)絡(luò)的SNP位點(diǎn)探究及可靠性分析[D];哈爾濱工業(yè)大學(xué);2017年

5 王小東;二分及多層網(wǎng)絡(luò)上的社團(tuán)檢測算法研究[D];西安電子科技大學(xué);2018年

6 于瑩瑩;基于疾病—基因—藥物數(shù)據(jù)的多層網(wǎng)絡(luò)構(gòu)建和分析[D];西安電子科技大學(xué);2018年

7 姚順宇;基于多層網(wǎng)絡(luò)模塊性的復(fù)雜疾病相關(guān)模式研究[D];西安電子科技大學(xué);2018年

8 劉敏;基于多層網(wǎng)絡(luò)的銀行系統(tǒng)性風(fēng)險研究[D];東南大學(xué);2018年

9 楊遠(yuǎn)景;中國金融系統(tǒng)性風(fēng)險的多層網(wǎng)絡(luò)特征及其傳染機(jī)制研究[D];湖南大學(xué);2017年

10 馬蒙周;基于多層網(wǎng)絡(luò)的關(guān)鍵基因識別方法研究[D];西安理工大學(xué);2018年

本文編號：2658705