本文選題：社會網絡 + 社區(qū)發(fā)現��； 參考：《國防科學技術大學》2012年碩士論文

【摘要】：隨著電子信息技術的發(fā)展，網絡作為一個重要的媒介走進了千家萬戶，微博，facebook，QQ已經成為人們日常交往不可或缺的工具。這些由人與人之間的交互關系抽象成的網絡稱之為社會網絡，廣義的社會網絡還包含基因網絡，論文引用關系網等自然形成的網絡，也稱之為自然網絡。這些網絡內部蘊含著豐富的信息等待我們去發(fā)現，對自然網絡的研究已經成為當前的一個熱點研究課題。本文主要就社會網絡分析中的社區(qū)發(fā)現和鏈接分析排名進行研究。 自然網絡最重要的特性就是聚簇結構，其聚簇內部連接緊密，聚簇之間連接稀疏。準確識別網絡中的聚簇結構稱之為社區(qū)發(fā)現。其可以廣泛應用于恐怖組織識別、蛋白質作用分析、電子商務等領域。本文首先分類介紹了社區(qū)發(fā)現的經典算法，然后分析了復雜度較低的WF算法，并針對其算法的不足，通過改進流模型引入節(jié)點的聚簇優(yōu)先遍歷以及新的社區(qū)評價準則，提出一種復雜度較低的社區(qū)發(fā)現算法。通過網絡分析基準數據，驗證了算法的有效性。 傳統(tǒng)的社區(qū)發(fā)現都是針對整個網絡數據，其劃分的結果是整個網絡的社區(qū)結構。計算效率不高且大部分社區(qū)對用戶沒有意義，同時部分自然網絡無法獲取完整的數據。本文在聚簇優(yōu)先遍歷的基礎上，通過二次切割的思想提出一種局部社區(qū)發(fā)現算法，在利用網絡部分數據的基礎上，提取出種子節(jié)點的自然歸屬社區(qū)，通過基準數據和人工生成的數據進行試驗，試驗結果顯示，本文算法能夠很好的發(fā)現種子節(jié)點的局部社區(qū)結構，且復雜度較低。 網絡中節(jié)點的重要程度是不同的，對網絡中節(jié)點按照某種需求進行重要程度排名稱之為鏈接分析排名，其可以廣泛應用在搜索引擎，文獻影響因子，以及發(fā)現恐怖組織重要成員等領域。本文首先介紹了鏈接分析排名的背景，隨后分析比較了橋接點排名的經典算法的性能，，并重點分析了隨機游走中心性算法，對其算法的主要復雜度進行改進，提出一種隨機游走中心性快速算法。經過基準數據和人工生成數據的測試，快速算法能夠很好的發(fā)現網絡中流通性較好的節(jié)點，并極大的降低了算法復雜度。
[Abstract]:With the development of electronic information technology, the network, as an important medium, has entered thousands of households. Weibo / Facebook QQ has become an indispensable tool for people's daily communication. These networks, which are abstracted from the interaction between people, are called social networks, and the generalized social networks also contain genetic networks, which are also called natural networks. These networks contain abundant information waiting for us to find out. The research on natural networks has become a hot research topic. This paper mainly studies the rank of community discovery and link analysis in social network analysis. The most important feature of natural network is clustering structure, which is closely connected and sparse. Accurate identification of the clustering structure in the network is called community discovery. It can be widely used in terrorist tissue identification, protein action analysis, electronic commerce and other fields. In this paper, the classical algorithm of community discovery is classified and introduced, and then the low complexity WF algorithm is analyzed. In view of the shortcomings of the algorithm, the clustering priority traversal of nodes and the new community evaluation criteria are introduced through the improved flow model. A community discovery algorithm with low complexity is proposed. The validity of the algorithm is verified by analyzing the datum data of the network. The traditional community discovery is based on the whole network data, and the result is the community structure of the whole network. Computing efficiency is low, most communities are meaningless to users, and some natural networks are unable to obtain complete data. On the basis of clustering priority traversal, this paper proposes a local community discovery algorithm based on the idea of secondary cutting. Based on the partial data of network, the natural community of seed nodes is extracted. The experimental results show that the algorithm can find the local community structure of the seed node well and the complexity is low. The importance of nodes in the network is different. The ranking of the importance of nodes in the network according to a certain demand is called link analysis ranking, which can be widely used in search engines, literature impact factors, And find important members of terrorist organizations and other areas. This paper first introduces the background of link analysis ranking, then analyzes and compares the performance of the classical algorithm of bridging point ranking, and focuses on the analysis of random walk centrality algorithm, and improves the main complexity of the algorithm. A fast algorithm of random walk centrality is proposed. Through the test of datum data and artificial generated data, the fast algorithm can find the nodes with good liquidity in the network, and greatly reduce the complexity of the algorithm.
【學位授予單位】：國防科學技術大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP393.09

【參考文獻】

相關期刊論文 前5條

1 淦文燕;李德毅;王建民;;一種基于數據場的層次聚類方法[J];電子學報;2006年02期

2 王莉軍;楊炳儒;謝永紅;;一種基于數據場的社區(qū)發(fā)現算法[J];計算機應用研究;2011年11期

3 何東曉;周栩;王佐;周春光;王U

本文編號：2025091