本文關(guān)鍵詞：向心路徑結(jié)點定義的子圖劃分與聚類子圖邊交叉數(shù)計算，由筆耕文化傳播整理發(fā)布。

【摘要】：在數(shù)據(jù)時代,伴隨著信息量的驟增,圖作為重要的信息載體,日益受到研究者的重視。如何更好地呈現(xiàn)與分析圖數(shù)據(jù)業(yè)已成為研究的熱點。為了更好地理解圖的結(jié)構(gòu)和衡量圖布局的優(yōu)劣,本文采用圖論中的路徑分析、計算幾何中的線段求交和計算機仿真等方法,主要研究子圖劃分和圖的邊交叉數(shù)計算問題。其中,子圖劃分為邊的交叉數(shù)計算提供了基礎(chǔ)。主要結(jié)論和創(chuàng)新點體現(xiàn)在下面三個方面：(1)子圖劃分研究。依據(jù)子類中心節(jié)點對于同一個類別中其它節(jié)點具有更強的控制力的思想,提出了子類中心點的概念及其確定方法,進一步給出上通路和向心路徑的定義。在子類中心節(jié)點基礎(chǔ)上通過計算向心路徑數(shù)量,實現(xiàn)網(wǎng)絡(luò)節(jié)點的快速聚類算法,即向心路徑節(jié)點聚類算法(Toward to Subheart Roads Defining NetworkClustering Algorithm)。相比于傳統(tǒng)算法,TSRDNCA算法具有較高的網(wǎng)絡(luò)社區(qū)判斷的準確性。(2)分類圖的邊交叉數(shù)計算研究。充分利用分類(子)圖自身已有的節(jié)點分類信息,將分類圖中的邊劃分為兩類分別進行交叉數(shù)計算,即類內(nèi)邊交叉數(shù)計算與類間邊交叉數(shù)計算,在類間邊數(shù)較少的情況下,提高了計算時間效率。(3)人工圖的生成研究。依據(jù)節(jié)點的無尺度特性與圖結(jié)構(gòu)分析理論,將人工圖的生成過程分為子圖構(gòu)建與子圖聯(lián)接兩部分。在子圖構(gòu)建階段,主要研究邊的構(gòu)建思路,即節(jié)點傾向于與高節(jié)點度相連。在子圖聯(lián)接階段,我們采用兩個概率優(yōu)先原則：連接兩個子圖的頂點有較大概率選擇在邊緣處的點；在后續(xù)增加子圖之間的邊時,有較大概率選擇已經(jīng)處于連接子圖關(guān)系的頂點。我們的人工圖生成算法可依據(jù)用戶需求生成相應(yīng)規(guī)格的分類圖,構(gòu)造的圖具有較好的仿真效果。此外,生成的人工圖為邊交叉數(shù)計算提供了各種例子。
【關(guān)鍵詞】：交叉數(shù) 子圖劃分 圖結(jié)構(gòu) 人工圖
【學位授予單位】：北京林業(yè)大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要3-4
• ABSTRACT4-7
• 1. 引言7-11
• 1.1. 研究背景7-8
• 1.2. 網(wǎng)絡(luò)分析8
• 1.3. 圖結(jié)構(gòu)分析8-9
• 1.4. 本文研究方向9-10
• 1.5. 本文結(jié)構(gòu)安排10-11
• 2. 相關(guān)理論與方法11-24
• 2.1. 圖論相關(guān)知識11-12
• 2.2. 復(fù)雜網(wǎng)絡(luò)特性12
• 2.3. 復(fù)雜網(wǎng)絡(luò)中心性12-14
• 2.4. 圖劃分算法14-17
• 2.5. 邊交叉數(shù)計算17-19
• 2.6. 圖布局算法19-24
• 2.6.1. 力導引布局算法20-22
• 2.6.2. 圓形布局算法22-24
• 3. 基于圖論的圖劃分算法24-35
• 3.1. 子類中心節(jié)點計算24-28
• 3.2. 非中心節(jié)點子類劃分28-30
• 3.3. 圖劃分算法實驗30-33
• 3.3.1. 海豚網(wǎng)絡(luò)社區(qū)劃分30-31
• 3.3.2. 美國西部電力網(wǎng)絡(luò)社區(qū)劃分31-32
• 3.3.3. 算法比較32-33
• 3.4. 小結(jié)33-35
• 4. 聚類圖的交叉數(shù)計算35-45
• 4.1. 人工分類圖構(gòu)造算法35-39
• 4.1.1. 分類子圖生成算法36-37
• 4.1.2. 子圖連接算法37-38
• 4.1.3. 算法歸納與實驗38-39
• 4.2. 聚類圖邊交叉計算算法39-41
• 4.3. 實驗41-44
• 4.3.1. 人工圖邊交叉數(shù)計算實驗41-42
• 4.3.2. 真實網(wǎng)絡(luò)聚類圖邊交叉數(shù)計算實驗42-44
• 4.4. 小結(jié)44-45
• 5. 總結(jié)與展望45-46
• 5.1. 總結(jié)45
• 5.2. 展望45-46
• 參考文獻46-50
• 個人簡介50-51
• 導師簡介51-52
• 獲得成果目錄52-53
• 致謝53

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

中國重要會議論文全文數(shù)據(jù)庫 前4條

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  本文關(guān)鍵詞：向心路徑結(jié)點定義的子圖劃分與聚類子圖邊交叉數(shù)計算，由筆耕文化傳播整理發(fā)布。

本文編號：400364