本文選題：復(fù)雜網(wǎng)絡(luò) + 社團(tuán)檢測(cè)��； 參考：《西安理工大學(xué)》2017年碩士論文

【摘要】：現(xiàn)實(shí)生活中存在著各種各樣的復(fù)雜網(wǎng)絡(luò),這些復(fù)雜網(wǎng)絡(luò)可以看作復(fù)雜系統(tǒng)的高度抽象。隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究,研究人員發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都存在一些共同的拓?fù)涮匦?如小世界特性、冪律度分布以及社團(tuán)結(jié)構(gòu)等。其中,社團(tuán)結(jié)構(gòu)描述的是復(fù)雜網(wǎng)絡(luò)中各群組內(nèi)部節(jié)點(diǎn)間的連接較為緊密,群組之間節(jié)點(diǎn)的連接相對(duì)稀疏的特性,是復(fù)雜網(wǎng)絡(luò)最重要的拓?fù)湫再|(zhì)之一。因此,復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)問(wèn)題受到了許多學(xué)者的廣泛研究,針對(duì)該問(wèn)題,本文主要做了以下工作:1.首先介紹了復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)檢測(cè)問(wèn)題的研究背景與意義,對(duì)經(jīng)典社團(tuán)檢測(cè)算法進(jìn)行了分類(lèi),并系統(tǒng)介紹了各算法對(duì)應(yīng)的算法原理與思想基礎(chǔ)。重點(diǎn)分析了譜聚類(lèi)算法的優(yōu)缺點(diǎn),以及該算法在網(wǎng)絡(luò)社團(tuán)檢測(cè)中的應(yīng)用。2.針對(duì)譜聚類(lèi)算法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)中存在的兩個(gè)問(wèn)題:(1)僅選擇網(wǎng)絡(luò)矩陣的部分特征向量對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類(lèi),沒(méi)有充分考慮到網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu);(2)矩陣特征向量的計(jì)算復(fù)雜度高,譜聚類(lèi)算法無(wú)法適用于具有海量節(jié)點(diǎn)的網(wǎng)絡(luò)。本文對(duì)譜聚類(lèi)算法進(jìn)行了大幅改進(jìn),改進(jìn)后的算法稱(chēng)為全息譜聚類(lèi)算法。全息譜聚類(lèi)算法采用網(wǎng)絡(luò)矩陣的所有特征向量聚類(lèi),并利用譜圖理論中的Parseval公式,將網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)應(yīng)向量的余弦相似性進(jìn)行了轉(zhuǎn)化,避免了對(duì)網(wǎng)絡(luò)矩陣特征向量的計(jì)算,降低了算法的計(jì)算復(fù)雜度。3.針對(duì)網(wǎng)絡(luò)矩陣的特征向量在網(wǎng)絡(luò)節(jié)點(diǎn)聚類(lèi)中的重要性不同,引入了加權(quán)函數(shù),通過(guò)對(duì)網(wǎng)絡(luò)矩陣的所有特征向量加權(quán),既充分考慮到了網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu),又考慮到了不同的特征向量對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類(lèi)的重要性問(wèn)題。另外,為了使全息譜聚類(lèi)算法可反映出網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的多尺度性,引入了尺度參數(shù),通過(guò)調(diào)節(jié)尺度參數(shù),控制加權(quán)函數(shù)對(duì)特征向量的加權(quán),該算法可將網(wǎng)絡(luò)劃分為不同尺度的社團(tuán)。實(shí)驗(yàn)結(jié)果表明:相對(duì)譜聚類(lèi)算法,全息譜聚類(lèi)算法將計(jì)算復(fù)雜度和存儲(chǔ)復(fù)雜度降低到了線性級(jí),使得該算法可應(yīng)用于含有大量節(jié)點(diǎn)的網(wǎng)絡(luò)。另外,通過(guò)調(diào)節(jié)尺度參數(shù),全息譜聚類(lèi)算法既能有效地檢測(cè)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),又可反映出網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的多尺度特性。
[Abstract]:There are a variety of complex networks in real life. These complex networks can be regarded as highly abstract of complex systems. With the in-depth study of complex networks, researchers have found that many practical networks have some common topology characteristics, such as small-world characteristics, power-law distribution and community structure. Among them, community structure is one of the most important topological properties of complex network, which describes the connection between the nodes of each group in complex network is relatively close, and the connection between the nodes between groups is relatively sparse, which is one of the most important topological properties of the complex network. Therefore, the problem of community detection in complex networks has been widely studied by many scholars. Aiming at this problem, this paper mainly does the following work: 1. This paper introduces the research background and significance of community structure detection in complex networks, classifies the classical community detection algorithms, and systematically introduces the algorithm principle and ideological basis of each algorithm. The advantages and disadvantages of spectral clustering algorithm and its application in network community detection are analyzed. Aiming at the two problems of spectral clustering algorithm in complex network community detection, we only select partial eigenvector of network matrix to cluster network nodes. The computational complexity of the eigenvector of the global topological structure of the network is not fully considered, so the spectral clustering algorithm can not be applied to the network with massive nodes. In this paper, the spectral clustering algorithm is greatly improved, the improved algorithm is called holographic spectral clustering algorithm. The holographic spectral clustering algorithm uses all eigenvector clustering of the network matrix and transforms the cosine similarity of the corresponding vectors of the network nodes by using the Parseval formula in the spectrum theory, thus avoiding the calculation of the eigenvector of the network matrix. The computational complexity of the algorithm is reduced by 3. 3. In view of the different importance of the eigenvector of the network matrix in the network node clustering, the weighting function is introduced. By weighting all the eigenvectors of the network matrix, the global topological structure of the network is fully considered. The importance of different Eigenvectors to network node clustering is also considered. In addition, in order to make the holographic spectral clustering algorithm reflect the multi-scale nature of the community structure in the network, the scale parameters are introduced, and the weighting function of the eigenvector is controlled by adjusting the scale parameters. The algorithm can divide the network into different scales of community. The experimental results show that the holographic spectral clustering algorithm reduces the computational complexity and storage complexity to a linear level, which makes the algorithm applicable to networks with a large number of nodes. In addition, by adjusting the scale parameters, the holographic spectral clustering algorithm can not only effectively detect the community structure in the complex network, but also reflect the multi-scale characteristics of the community structure in the network.
【學(xué)位授予單位】：西安理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：TP311.13;O157.5

【參考文獻(xiàn)】

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

1 付立東;;復(fù)雜網(wǎng)絡(luò)社團(tuán)的譜分檢測(cè)方法[J];計(jì)算機(jī)工程;2011年01期

2 蔡曉妍;戴冠中;楊黎斌;;譜聚類(lèi)算法綜述[J];計(jì)算機(jī)科學(xué);2008年07期

3 王林,戴冠中;復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)——理論與應(yīng)用[J];科技導(dǎo)報(bào);2005年08期

，

本文編號(hào)：1908245