本文選題：復雜網(wǎng)絡 + 社團檢測��； 參考：《西安理工大學》2017年碩士論文

【摘要】：現(xiàn)實生活中存在著各種各樣的復雜網(wǎng)絡,這些復雜網(wǎng)絡可以看作復雜系統(tǒng)的高度抽象。隨著對復雜網(wǎng)絡的深入研究,研究人員發(fā)現(xiàn)許多實際網(wǎng)絡都存在一些共同的拓撲特性,如小世界特性、冪律度分布以及社團結構等。其中,社團結構描述的是復雜網(wǎng)絡中各群組內部節(jié)點間的連接較為緊密,群組之間節(jié)點的連接相對稀疏的特性,是復雜網(wǎng)絡最重要的拓撲性質之一。因此,復雜網(wǎng)絡中的社團檢測問題受到了許多學者的廣泛研究,針對該問題,本文主要做了以下工作:1.首先介紹了復雜網(wǎng)絡中社團結構檢測問題的研究背景與意義,對經(jīng)典社團檢測算法進行了分類,并系統(tǒng)介紹了各算法對應的算法原理與思想基礎。重點分析了譜聚類算法的優(yōu)缺點,以及該算法在網(wǎng)絡社團檢測中的應用。2.針對譜聚類算法在復雜網(wǎng)絡社團檢測中存在的兩個問題:(1)僅選擇網(wǎng)絡矩陣的部分特征向量對網(wǎng)絡節(jié)點聚類,沒有充分考慮到網(wǎng)絡的全局拓撲結構;(2)矩陣特征向量的計算復雜度高,譜聚類算法無法適用于具有海量節(jié)點的網(wǎng)絡。本文對譜聚類算法進行了大幅改進,改進后的算法稱為全息譜聚類算法。全息譜聚類算法采用網(wǎng)絡矩陣的所有特征向量聚類,并利用譜圖理論中的Parseval公式,將網(wǎng)絡節(jié)點對應向量的余弦相似性進行了轉化,避免了對網(wǎng)絡矩陣特征向量的計算,降低了算法的計算復雜度。3.針對網(wǎng)絡矩陣的特征向量在網(wǎng)絡節(jié)點聚類中的重要性不同,引入了加權函數(shù),通過對網(wǎng)絡矩陣的所有特征向量加權,既充分考慮到了網(wǎng)絡的全局拓撲結構,又考慮到了不同的特征向量對網(wǎng)絡節(jié)點聚類的重要性問題。另外,為了使全息譜聚類算法可反映出網(wǎng)絡中社團結構的多尺度性,引入了尺度參數(shù),通過調節(jié)尺度參數(shù),控制加權函數(shù)對特征向量的加權,該算法可將網(wǎng)絡劃分為不同尺度的社團。實驗結果表明:相對譜聚類算法,全息譜聚類算法將計算復雜度和存儲復雜度降低到了線性級,使得該算法可應用于含有大量節(jié)點的網(wǎng)絡。另外,通過調節(jié)尺度參數(shù),全息譜聚類算法既能有效地檢測復雜網(wǎng)絡中的社團結構,又可反映出網(wǎng)絡中社團結構的多尺度特性。
[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.
【學位授予單位】：西安理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP311.13;O157.5

【參考文獻】

相關期刊論文 前3條

1 付立東;;復雜網(wǎng)絡社團的譜分檢測方法[J];計算機工程;2011年01期

2 蔡曉妍;戴冠中;楊黎斌;;譜聚類算法綜述[J];計算機科學;2008年07期

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

，

本文編號：1908245