【摘要】：復(fù)雜網(wǎng)絡(luò)中一些關(guān)鍵的核心節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)中其他節(jié)點(diǎn)具有很大的影響力,因此找到這些關(guān)鍵的核心節(jié)點(diǎn)對(duì)于研究復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)和節(jié)點(diǎn)的行為預(yù)測(cè)具有十分重要的意義。此外,復(fù)雜網(wǎng)絡(luò)中很多的技術(shù)研究都是在社團(tuán)劃分的基礎(chǔ)上進(jìn)行的,因此對(duì)復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的研究同樣具有非常重要的意義。經(jīng)過(guò)多年社團(tuán)劃分的研究,盡管出現(xiàn)了許多優(yōu)秀的劃分算法,但是在提高社團(tuán)劃分的準(zhǔn)確度及降低算法的復(fù)雜度上仍然面臨著挑戰(zhàn)。針對(duì)現(xiàn)存算法準(zhǔn)確度低復(fù)雜度高的問(wèn)題,本文主要在如下幾個(gè)方面進(jìn)行研究和探索:(1)在劃分社團(tuán)之前,首先要準(zhǔn)確找到社團(tuán)中的核心節(jié)點(diǎn),這涉及到節(jié)點(diǎn)重要度的評(píng)價(jià)。而當(dāng)前節(jié)點(diǎn)重要度評(píng)價(jià)算法考慮的因素比較單一,不能準(zhǔn)確找到社團(tuán)的核心節(jié)點(diǎn)。本文考慮到鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)自身重要度的影響,以及自身對(duì)鄰居節(jié)點(diǎn)的影響,給出了節(jié)點(diǎn)重要度貢獻(xiàn)矩陣,重要度貢獻(xiàn)矩陣中將節(jié)點(diǎn)的K-shell值、鄰居節(jié)點(diǎn)平均度及節(jié)點(diǎn)間的緊密度作為影響因素考慮在內(nèi)。然后綜合節(jié)點(diǎn)度和局部度中心節(jié)點(diǎn)等因素給出節(jié)點(diǎn)重要度的評(píng)價(jià)方法。(2)目前大多數(shù)的層次聚類(lèi)算法劃分社團(tuán)的準(zhǔn)確度都比較低,本文利用多個(gè)核心節(jié)點(diǎn)作為初始社團(tuán)對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類(lèi),在計(jì)算節(jié)點(diǎn)與初始社團(tuán)的相似度時(shí),將初始社團(tuán)中的節(jié)點(diǎn)重要度考慮在內(nèi),從而更加準(zhǔn)確的計(jì)算出節(jié)點(diǎn)與初始社團(tuán)的相似度,提高算法劃分社團(tuán)的準(zhǔn)確度。最后對(duì)算法進(jìn)行并行化分析,將其應(yīng)用在分布式平臺(tái)上,提高算法的運(yùn)行效率。節(jié)點(diǎn)重要度的實(shí)驗(yàn)在兩個(gè)簡(jiǎn)單直觀、結(jié)構(gòu)清晰的網(wǎng)絡(luò)上進(jìn)行,將其與單一的評(píng)價(jià)指標(biāo)進(jìn)行比較分析。社團(tuán)劃分的實(shí)驗(yàn)分別在真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上進(jìn)行,對(duì)其劃分結(jié)果進(jìn)行分析,同時(shí)將算法分別與其他節(jié)點(diǎn)重要度評(píng)價(jià)算法和層次聚類(lèi)算法進(jìn)行對(duì)比分析。并將并行化的算法在大規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證算法的運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明,本文節(jié)點(diǎn)重要度評(píng)價(jià)算法能夠準(zhǔn)確有效的計(jì)算出節(jié)點(diǎn)的重要度,社團(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：O157.5;TP301.6

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2120441