本文選題：復(fù)雜網(wǎng)絡(luò) + 重要結(jié)點��； 參考：《云南財經(jīng)大學(xué)》2016年碩士論文

【摘要】：復(fù)雜網(wǎng)絡(luò)(complex network)的研究持續(xù)數(shù)十載,在眾多應(yīng)用領(lǐng)域一直屬于熱門研究課題,它是普遍認(rèn)可的、剖析自然界和人類社會等多種復(fù)雜系統(tǒng)的有效工具與手段。因為海內(nèi)外眾多學(xué)者的推動,相關(guān)研究已滲入計算機科學(xué)、經(jīng)濟學(xué)、管理學(xué)、生命科學(xué)、社會學(xué)、物理學(xué),甚至是語言學(xué)、文學(xué)、藝術(shù)等多元領(lǐng)域。復(fù)雜網(wǎng)絡(luò)中存在一類被稱作“重要結(jié)點”的特殊結(jié)點,它們與網(wǎng)絡(luò)其余結(jié)點相比,對網(wǎng)絡(luò)的結(jié)構(gòu)和功能等方面的影響更加顯著。同時,確定復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵結(jié)點對優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)、增強網(wǎng)絡(luò)結(jié)構(gòu)魯棒性及掌握信息傳播動態(tài)等具有十分重要的理論意義與應(yīng)用價值。因此,伴隨網(wǎng)絡(luò)科學(xué)的快速發(fā)展,重要結(jié)點的發(fā)現(xiàn)研究引起了有識之士的廣泛關(guān)注。經(jīng)典重要結(jié)點識別算法有度中心性(degree centrality)、介數(shù)中心性(betweenness centrality)、緊密度中心性(closeness centrality)和K-核分解(k-shell decomposition)等方法,其中,度僅僅考慮到結(jié)點局部屬性;介數(shù)與緊密度這兩種全局評估指標(biāo)由于計算復(fù)雜,因而難以普及到大型網(wǎng)絡(luò);K-核分解利用結(jié)點的位置信息發(fā)現(xiàn)單源核心結(jié)點,然而,它對同層結(jié)點的重要性區(qū)分力度較差。這些方法相對簡單,能夠在一定程度上評估結(jié)點的重要性;然而,由于它們?nèi)狈Y(jié)點多方面特征的全面考察,導(dǎo)致算法的評判結(jié)果不夠理想,局限性較大。為更加有效的識別復(fù)雜網(wǎng)絡(luò)中的重要結(jié)點,本文提出兩個重要結(jié)點發(fā)現(xiàn)算法:基于“K-核影響矩陣”的重要結(jié)點發(fā)現(xiàn)算法(k-shell influence matrix,KsIM算法)和基于結(jié)點“三維集成特征”的重要結(jié)點發(fā)現(xiàn)算法(node importance of three dimensions,NI3算法)。KsIM算法從網(wǎng)絡(luò)拓?fù)鋵哟稳胧�、利用結(jié)點K-核屬性表征結(jié)點間的局部依賴強度,并結(jié)合結(jié)點效率構(gòu)建結(jié)點重要度評估矩陣,打破了常規(guī)方法用度刻畫結(jié)點之間重要度貢獻(xiàn)的局限,為重要度貢獻(xiàn)形式提供了新的量化標(biāo)準(zhǔn)。而NI3算法在分析結(jié)點橫向、縱向、分層三維特征基礎(chǔ)上,定義結(jié)點廣度、深度和強度指標(biāo):三者從結(jié)點的直接鄰居結(jié)點(廣度)、結(jié)點影響力所能到達(dá)的極遠(yuǎn)處(深度)以及結(jié)點施加其影響力于其它結(jié)點的效率(強度)三方面刻畫結(jié)點的影響程度,并集成為一個表征結(jié)點重要性的定量指標(biāo)。本文所述算法性能均通過SIR模型仿真實驗進行驗證。SIR模型可以很好地模擬信息、病毒的傳播過程,是理解相關(guān)傳播機制并對傳播過程進行理論分析的得力助手。借助SIR仿真模型、運用Kendall相關(guān)系數(shù)、不準(zhǔn)確率、相關(guān)熱度等多種評價標(biāo)準(zhǔn),在多個不同拓?fù)浣Y(jié)構(gòu)的真實網(wǎng)絡(luò)數(shù)據(jù)上獲取的實驗結(jié)果表明,基于“K-核影響矩陣”的重要結(jié)點發(fā)現(xiàn)算法KsIM和基于結(jié)點“三維集成特征”的重要結(jié)點發(fā)現(xiàn)算法NI3切實有效、識別重要結(jié)點的準(zhǔn)確性與針對不同拓?fù)浣Y(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)的魯棒性均勝過傳統(tǒng)算法。本文結(jié)構(gòu)安排如下:第一章為緒論,介紹了復(fù)雜網(wǎng)絡(luò)重要結(jié)點發(fā)現(xiàn)的研究背景、現(xiàn)狀與意義,表明本課題研究的重要性;第二章與第三章分別介紹了相關(guān)的重要算法模型和主要的算法評估標(biāo)準(zhǔn);之后,重點介紹基于結(jié)點“K-核影響矩陣”和“三維集成特征”的算法模型構(gòu)建,并在第五章給出詳細(xì)的實驗驗證過程;最后總結(jié)全文,展望今后的研究方向。
[Abstract]:The research of complex network (complex network) has lasted for decades and has been a popular research topic in many applications. It is an effective tool and means to analyze complex systems such as nature and human society. Because of the promotion of many scholars at home and abroad, the related research has infiltrated into computer science, economics, management, and so on. Life science, sociology, physics, even linguistics, literature, art and other fields. There is a special node called "important node" in complex networks. Compared with the rest of the network, they have a more significant impact on the structure and function of the network. At the same time, the key nodes in the complex network are determined to optimize the network. With the rapid development of network science, the discovery of important nodes has aroused wide attention of the people of insight. The classical important node identification method has the degree centrality (degree centrality) and the medium center. Betweenness centrality, compact degree centrality (closeness centrality) and K- kernel decomposition (K-shell decomposition), in which the degree only takes into account the local attribute of the node; the two global evaluation indexes of the number and the tightness are difficult to popularize to the large network because of the complexity of the computation; K- kernel decomposition uses the location information of the nodes. However, it is relatively simple and can evaluate the importance of the nodes to a certain extent. However, because of their lack of comprehensive investigation of the multifaceted features of the nodes, the results of the algorithm are not ideal and limited. Two important node discovery algorithms are proposed in this paper: the important node discovery algorithm based on the "K- kernel impact matrix" (K-shell influence matrix, KsIM algorithm) and the important node discovery algorithm based on the node "three dimensional integration features" (node importance of three dimensions, NI3 algorithm).KsIM algorithm from the network Starting with the topology level, using the node K- kernel attribute to characterize the local dependence intensity between nodes, and combining the node efficiency to construct the evaluation matrix of node importance, breaking the limitation of the important degree contribution between the nodes of the conventional methods and providing a new quantitative standard for the important degree contribution form, and the NI3 algorithm in the analysis of the horizontal and vertical nodes. On the basis of stratified 3D features, we define the breadth, depth and intensity of nodes: the three ones from the direct neighbor node (breadth) of the nodes, the extreme distance (depth) that the node influence can reach, and the three aspects of the efficiency (intensity) of the nodes exerting its influence on other nodes, and integrate it as a token node. The performance of the proposed algorithm is verified by the SIR model simulation experiment. The.SIR model can simulate the information well. The propagation process of the virus is the right assistant to understand the related propagation mechanism and analyze the propagation process. With the help of the SIR simulation model, the Kendall correlation coefficient, inaccuracy rate, and related heat are used. The experimental results obtained on real network data of multiple different topologies show that the important node discovery algorithm KsIM based on the "K- kernel impact matrix" and the important node discovery algorithm based on the node "3D integration feature" are effective, identifying the accuracy of important nodes and aiming at different topology nodes. The robustness of the complex network is better than the traditional algorithm. The structure of this paper is arranged as follows: the first chapter is the introduction, introducing the research background, the status and significance of the complex network important node discovery, and the importance of the research. The second chapter and the third chapter respectively introduce the important algorithm model and the main algorithm evaluation criteria; after that, This paper focuses on the construction of the algorithm model based on the node "K- kernel impact matrix" and "three dimensional integration features", and gives a detailed experimental verification process in the fifth chapter. Finally, it summarizes the full text and looks forward to the future research direction.
【學(xué)位授予單位】：云南財經(jīng)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 王紹恒;馮天祥;;新增結(jié)點下最小生成樹研究[J];數(shù)學(xué)雜志;2010年06期

2 胡廣朋;結(jié)點可同名的無向簡圖的相似度[J];微計算機應(yīng)用;2005年01期

3 ;[J];;年期

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

1 董小潔;夏寬理;;忍受犯規(guī)的開放式提交協(xié)議[A];第十二屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1994年

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

1 蔣杰 方力 竇文華;覆蓋控制[N];計算機世界;2004年

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

1 王立;城市結(jié)點文化特質(zhì)及其協(xié)同觀[D];重慶大學(xué);2006年

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

1 田艷;復(fù)雜網(wǎng)絡(luò)重要結(jié)點發(fā)現(xiàn)算法研究[D];云南財經(jīng)大學(xué);2016年

2 姜浩;對等網(wǎng)絡(luò)中路由中繼結(jié)點發(fā)現(xiàn)機制的研究[D];華中科技大學(xué);2007年

3 楊孟君;基于網(wǎng)絡(luò)認(rèn)知的無中心式系統(tǒng)交互的優(yōu)化方法[D];電子科技大學(xué);2015年

4 顧燁;P2P網(wǎng)絡(luò)邏輯拓?fù)鋬?yōu)化和結(jié)點組管理策略研究[D];浙江工商大學(xué);2010年

5 李丁丁;一種基于結(jié)點聚類的網(wǎng)絡(luò)定位算法[D];湖南大學(xué);2008年

6 孫宇奇;基于復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)研究[D];遼寧師范大學(xué);2011年

，

本文編號：2039927