本文關(guān)鍵詞：基于復(fù)雜網(wǎng)絡(luò)拓撲特性的搜索算法的研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 拓撲特性 最大度 搜索算法

【摘要】：隨著以因特網(wǎng)為代表的信息技術(shù)的興起,復(fù)雜網(wǎng)絡(luò)的研究逐漸引起了人們的注意。在眾多的復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中,搜索問題是其中最具有實用性的課題。它涉及網(wǎng)絡(luò)中指定文件或數(shù)據(jù)的尋找及網(wǎng)絡(luò)中節(jié)點間最短路徑的確定,為互聯(lián)網(wǎng)中搜索引擎的設(shè)計、社交網(wǎng)絡(luò)中人與人的交往行為等問題的研究提供了理論指導。實際的復(fù)雜網(wǎng)絡(luò)中普遍存在多種拓撲特性,本文將兼顧復(fù)雜網(wǎng)絡(luò)中存在的不同拓撲特性,對搜索算法進行深入的研究、分析和改進。首先,提出了最大度-最小距離搜索算法。該算法針對含有度量空間的實際復(fù)雜網(wǎng)絡(luò),建立一個參數(shù)可調(diào)的無標度空間網(wǎng)絡(luò)模型。在此基礎(chǔ)上,將度量距離與度這兩個影響搜索性能的度量值相結(jié)合,使該算法既可以做到不使傳遞信息的方向偏離所要搜索的目的節(jié)點,又可以把搜索信息傳遞給含有長程連接的具有較大度的節(jié)點。其次,提出了最小聚集系數(shù)-最大度搜索算法。通過分析最大度搜索算法缺陷的成因,找到一個分界值,使得對該分界值范圍內(nèi)節(jié)點的搜索過程符合“按度序列”搜索的設(shè)想�；谠摲纸缰�,將節(jié)點的度與聚集系數(shù)這兩個度量值相結(jié)合,使該算法既利用了冪率指數(shù)在一定范圍內(nèi)最大度搜索算法的明顯優(yōu)勢,又兼顧了超出這個范圍使用最小聚集系數(shù)搜索算法的高效。最后,本文使用C++編程語言,對幾個拓撲特征不同的真實復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進行了仿真實驗。依據(jù)平均搜索時間和平均搜索步數(shù)這兩個指標,對幾個不同復(fù)雜網(wǎng)絡(luò)搜索算法進行了比較、分析和評價,從而驗證了最大度-最小距離搜索算法和最小聚集系數(shù)-最大度搜索算法的正確性和高效性。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 拓撲特性 最大度 搜索算法
【學位授予單位】：燕山大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP391.3
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 緒論10-16
• 1.1 課題背景及研究的目的和意義10-11
• 1.2 國內(nèi)外研究現(xiàn)狀11-14
• 1.3 復(fù)雜網(wǎng)絡(luò)搜索算法中存在的問題14
• 1.4 本文的主要研究內(nèi)容14-15
• 1.5 本文的組織結(jié)構(gòu)15-16
• 第2章 相關(guān)理論與技術(shù)16-24
• 2.1 復(fù)雜網(wǎng)絡(luò)拓撲模型16-20
• 2.1.1 小世界網(wǎng)絡(luò)16-18
• 2.1.2 無標度網(wǎng)絡(luò)18-20
• 2.2 復(fù)雜網(wǎng)絡(luò)中的搜索算法20-22
• 2.2.1 廣度優(yōu)先搜索算法20-21
• 2.2.2 隨機游走搜索算法21-22
• 2.2.3 最大度搜索算法22
• 2.3 本章小結(jié)22-24
• 第3章 基于最大度-最短距離的復(fù)雜網(wǎng)絡(luò)搜索方法24-33
• 3.1 引言24-25
• 3.2 相關(guān)問題及定義25-27
• 3.2.1 平均路徑長度25-26
• 3.2.2 度與度分布26-27
• 3.3 最大度-最小距離算法設(shè)計27-30
• 3.3.1 無標度空間網(wǎng)絡(luò)模型的建立27-28
• 3.3.2 搜索過程描述28-29
• 3.3.3 算法描述29-30
• 3.4 最大度-最小距離算法分析30-32
• 3.4.1 節(jié)點間距離的確定30
• 3.4.2 貪婪算法的缺陷30-31
• 3.4.3 算法性能分析31-32
• 3.5 本章小結(jié)32-33
• 第4章 基于最小聚集系數(shù)-最大度的復(fù)雜網(wǎng)絡(luò)搜索方法33-43
• 4.1 引言33-34
• 4.2 相關(guān)問題及定義34-38
• 4.2.1 冪律分布特性34-35
• 4.2.2 聚集系數(shù)35-38
• 4.3 最小聚集系數(shù)-最大度算法設(shè)計38-41
• 4.3.1 最大度搜索算法的缺陷38-39
• 4.3.2 算法描述39-41
• 4.4 最小聚集系數(shù)-最大度算法分析41-42
• 4.4.1 分界值k0值的選取41
• 4.4.2 算法性能分析41-42
• 4.5 本章小結(jié)42-43
• 第5章 實驗與結(jié)果分析43-54
• 5.1 最大度-最小距離搜索算法43-47
• 5.1.1 環(huán)境及數(shù)據(jù)集的設(shè)置43
• 5.1.2 實際復(fù)雜網(wǎng)絡(luò)中的搜索效果43-47
• 5.2 最小聚集系數(shù)-最大度算法47-54
• 5.2.1 環(huán)境及數(shù)據(jù)集的設(shè)置47-48
• 5.2.2 分界值k_0的選取48-50
• 5.2.3 實際復(fù)雜網(wǎng)絡(luò)中的搜索效果50-54
• 結(jié)論54-56
• 參考文獻56-60
• 攻讀碩士學位期間承擔的科研任務(wù)與主要成果60-61
• 致謝61-62
• 作者簡介62

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前6條

1 湯蓉;唐常杰;徐開闊;楊寧;;基于局部聚合的復(fù)雜網(wǎng)絡(luò)自動聚簇算法[J];電子科技大學學報;2014年03期

2 鄧小清;周竹榮;程向榮;;基于螞蟻算法的網(wǎng)格資源發(fā)現(xiàn)模型[J];計算機應(yīng)用;2007年10期

3 秦李;楊子龍;黃曙光;;復(fù)雜網(wǎng)絡(luò)的節(jié)點重要性綜合評價[J];計算機科學;2015年02期

4 吳泓潤;覃俊;易云飛;李德毅;鄭波盡;;基于優(yōu)化理論的社區(qū)無標度網(wǎng)絡(luò)模型[J];計算機學報;2015年02期

5 程曉濤;劉彩霞;劉樹新;;基于局域信息的社交網(wǎng)絡(luò)信息傳播模型[J];計算機應(yīng)用;2015年02期

6 張方風;劉軍;;復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)與演化模型研究綜述(一)[J];系統(tǒng)科學學報;2014年02期

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 俞峰;復(fù)雜動態(tài)隨機網(wǎng)絡(luò)最短路徑問題研究[D];浙江大學;2009年

，

本文編號：697178