發(fā)布時間：2018-07-13 19:02

【摘要】：復(fù)雜網(wǎng)絡(luò)中一些關(guān)鍵的核心節(jié)點對于網(wǎng)絡(luò)中其他節(jié)點具有很大的影響力,因此找到這些關(guān)鍵的核心節(jié)點對于研究復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)和節(jié)點的行為預(yù)測具有十分重要的意義。此外,復(fù)雜網(wǎng)絡(luò)中很多的技術(shù)研究都是在社團(tuán)劃分的基礎(chǔ)上進(jìn)行的,因此對復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的研究同樣具有非常重要的意義。經(jīng)過多年社團(tuán)劃分的研究,盡管出現(xiàn)了許多優(yōu)秀的劃分算法,但是在提高社團(tuán)劃分的準(zhǔn)確度及降低算法的復(fù)雜度上仍然面臨著挑戰(zhàn)。針對現(xiàn)存算法準(zhǔn)確度低復(fù)雜度高的問題,本文主要在如下幾個方面進(jìn)行研究和探索:(1)在劃分社團(tuán)之前,首先要準(zhǔn)確找到社團(tuán)中的核心節(jié)點,這涉及到節(jié)點重要度的評價。而當(dāng)前節(jié)點重要度評價算法考慮的因素比較單一,不能準(zhǔn)確找到社團(tuán)的核心節(jié)點。本文考慮到鄰居節(jié)點對節(jié)點自身重要度的影響,以及自身對鄰居節(jié)點的影響,給出了節(jié)點重要度貢獻(xiàn)矩陣,重要度貢獻(xiàn)矩陣中將節(jié)點的K-shell值、鄰居節(jié)點平均度及節(jié)點間的緊密度作為影響因素考慮在內(nèi)。然后綜合節(jié)點度和局部度中心節(jié)點等因素給出節(jié)點重要度的評價方法。(2)目前大多數(shù)的層次聚類算法劃分社團(tuán)的準(zhǔn)確度都比較低,本文利用多個核心節(jié)點作為初始社團(tuán)對復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類,在計算節(jié)點與初始社團(tuán)的相似度時,將初始社團(tuán)中的節(jié)點重要度考慮在內(nèi),從而更加準(zhǔn)確的計算出節(jié)點與初始社團(tuán)的相似度,提高算法劃分社團(tuán)的準(zhǔn)確度。最后對算法進(jìn)行并行化分析,將其應(yīng)用在分布式平臺上,提高算法的運(yùn)行效率。節(jié)點重要度的實驗在兩個簡單直觀、結(jié)構(gòu)清晰的網(wǎng)絡(luò)上進(jìn)行,將其與單一的評價指標(biāo)進(jìn)行比較分析。社團(tuán)劃分的實驗分別在真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上進(jìn)行,對其劃分結(jié)果進(jìn)行分析,同時將算法分別與其他節(jié)點重要度評價算法和層次聚類算法進(jìn)行對比分析。并將并行化的算法在大規(guī)模的數(shù)據(jù)集上進(jìn)行實驗,驗證算法的運(yùn)行效率。實驗結(jié)果表明,本文節(jié)點重要度評價算法能夠準(zhǔn)確有效的計算出節(jié)點的重要度,社團(tuán)劃分算法能夠快速準(zhǔn)確的劃分出復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu),算法并行化后能夠快速的處理大規(guī)模復(fù)雜網(wǎng)絡(luò)。
[Abstract]:Some key core nodes in complex networks have great influence on other nodes in the network, so it is very important to find these key core nodes to study the community structure and the behavior prediction of nodes in complex networks. In addition, many technical studies in complex networks are carried out on the basis of community division, so the study of community division in complex networks is also of great significance. After years of research on community partitioning, although there are many excellent partitioning algorithms, there are still challenges in improving the accuracy of community partitioning and reducing the complexity of the algorithm. Aiming at the problem of low accuracy and high complexity of existing algorithms, this paper mainly studies and explores the following aspects: (1) before dividing the community, we must first find the core nodes in the community accurately, which involves the evaluation of the importance of the nodes. However, the current node importance evaluation algorithm considers a single factor, and can not accurately find the core nodes of the community. In this paper, considering the influence of neighbor nodes on the importance degree of nodes and their own influence on neighbor nodes, the contribution matrix of importance degree of nodes is given, and the K-shell value of nodes is given in the contribution matrix of importance degree. The neighbor node average and the tightness between nodes are taken into account. Then the evaluation method of node importance is given by synthesizing node degree and local degree center node. (2) most hierarchical clustering algorithms have low accuracy in community division. In this paper, several core nodes are used as the initial community to cluster the complex network. When calculating the similarity between the nodes and the initial community, the importance of the nodes in the initial community is taken into account. Thus, the similarity between the nodes and the initial community can be calculated more accurately, and the accuracy of the algorithm can be improved. Finally, the parallelization analysis of the algorithm is carried out, and the algorithm is applied to the distributed platform to improve the efficiency of the algorithm. The experiment of node importance is carried out on two simple and intuitive networks with clear structure, which is compared with a single evaluation index. The experiments of community division are carried out on real network and artificial network respectively, and the results of classification are analyzed. At the same time, the algorithm is compared with other node importance evaluation algorithm and hierarchical clustering algorithm. The parallel algorithm is tested on a large scale data set to verify the efficiency of the algorithm. The experimental results show that the algorithm can calculate the importance of nodes accurately and effectively, and the community partition algorithm can quickly and accurately divide the community structure of complex networks. The parallel algorithm can deal with large scale complex networks quickly.
【學(xué)位授予單位】：西安理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5;TP301.6

【參考文獻(xiàn)】

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

1 馬曉慧;;一種改進(jìn)的可并行的K-medoids聚類算法[J];智能計算機(jī)與應(yīng)用;2016年03期

2 吳蔚蔚;劉功申;黃晨;;基于相似度的社團(tuán)劃分算法[J];計算機(jī)工程;2015年11期

3 梁宗文;楊帆;李建平;;基于節(jié)點相似性度量的社團(tuán)結(jié)構(gòu)劃分方法[J];計算機(jī)應(yīng)用;2015年05期

4 王興元;趙仲祥;;基于節(jié)點間依賴度的社團(tuán)結(jié)構(gòu)劃分方法[J];物理學(xué)報;2014年17期

5 任卓明;邵鳳;劉建國;郭強(qiáng);汪秉宏;;基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究[J];物理學(xué)報;2013年12期

6 袁超;柴毅;;基于簇相似度的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)探測算法[J];物理學(xué)報;2012年21期

7 施偉;傅鶴崗;張程;;基于連邊相似度的重疊社區(qū)發(fā)現(xiàn)算法研究[J];計算機(jī)應(yīng)用研究;2013年01期

8 李爭光;宋利;;基于結(jié)點相似性的層次化社團(tuán)發(fā)現(xiàn)算法[J];信息技術(shù);2012年05期

9 王千;王成;馮振元;葉金鳳;;K-means聚類算法研究綜述[J];電子設(shè)計工程;2012年07期

10 姜雅文;賈彩燕;于劍;;基于節(jié)點相似度的網(wǎng)絡(luò)社團(tuán)檢測算法研究[J];計算機(jī)科學(xué);2011年07期

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

1 姜雅文;復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)若干問題研究[D];北京交通大學(xué);2014年

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

1 朱安柱;基于Hadoop的Apriori算法改進(jìn)與移植的研究[D];華中科技大學(xué);2012年

，

本文編號：2120441