本文選題：社會(huì)網(wǎng)絡(luò) + 社區(qū)發(fā)現(xiàn)��； 參考：《國(guó)防科學(xué)技術(shù)大學(xué)》2012年碩士論文

【摘要】：隨著電子信息技術(shù)的發(fā)展，網(wǎng)絡(luò)作為一個(gè)重要的媒介走進(jìn)了千家萬(wàn)戶，微博，facebook，QQ已經(jīng)成為人們?nèi)粘＝煌豢苫蛉钡墓ぞ�。這些由人與人之間的交互關(guān)系抽象成的網(wǎng)絡(luò)稱之為社會(huì)網(wǎng)絡(luò)，廣義的社會(huì)網(wǎng)絡(luò)還包含基因網(wǎng)絡(luò)，論文引用關(guān)系網(wǎng)等自然形成的網(wǎng)絡(luò)，也稱之為自然網(wǎng)絡(luò)。這些網(wǎng)絡(luò)內(nèi)部蘊(yùn)含著豐富的信息等待我們?nèi)グl(fā)現(xiàn)，對(duì)自然網(wǎng)絡(luò)的研究已經(jīng)成為當(dāng)前的一個(gè)熱點(diǎn)研究課題。本文主要就社會(huì)網(wǎng)絡(luò)分析中的社區(qū)發(fā)現(xiàn)和鏈接分析排名進(jìn)行研究。 自然網(wǎng)絡(luò)最重要的特性就是聚簇結(jié)構(gòu)，其聚簇內(nèi)部連接緊密，聚簇之間連接稀疏。準(zhǔn)確識(shí)別網(wǎng)絡(luò)中的聚簇結(jié)構(gòu)稱之為社區(qū)發(fā)現(xiàn)。其可以廣泛應(yīng)用于恐怖組織識(shí)別、蛋白質(zhì)作用分析、電子商務(wù)等領(lǐng)域。本文首先分類介紹了社區(qū)發(fā)現(xiàn)的經(jīng)典算法，然后分析了復(fù)雜度較低的WF算法，并針對(duì)其算法的不足，通過(guò)改進(jìn)流模型引入節(jié)點(diǎn)的聚簇優(yōu)先遍歷以及新的社區(qū)評(píng)價(jià)準(zhǔn)則，提出一種復(fù)雜度較低的社區(qū)發(fā)現(xiàn)算法。通過(guò)網(wǎng)絡(luò)分析基準(zhǔn)數(shù)據(jù)，驗(yàn)證了算法的有效性。 傳統(tǒng)的社區(qū)發(fā)現(xiàn)都是針對(duì)整個(gè)網(wǎng)絡(luò)數(shù)據(jù)，其劃分的結(jié)果是整個(gè)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。計(jì)算效率不高且大部分社區(qū)對(duì)用戶沒(méi)有意義，同時(shí)部分自然網(wǎng)絡(luò)無(wú)法獲取完整的數(shù)據(jù)。本文在聚簇優(yōu)先遍歷的基礎(chǔ)上，通過(guò)二次切割的思想提出一種局部社區(qū)發(fā)現(xiàn)算法，在利用網(wǎng)絡(luò)部分?jǐn)?shù)據(jù)的基礎(chǔ)上，提取出種子節(jié)點(diǎn)的自然歸屬社區(qū)，通過(guò)基準(zhǔn)數(shù)據(jù)和人工生成的數(shù)據(jù)進(jìn)行試驗(yàn)，試驗(yàn)結(jié)果顯示，本文算法能夠很好的發(fā)現(xiàn)種子節(jié)點(diǎn)的局部社區(qū)結(jié)構(gòu)，且復(fù)雜度較低。 網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度是不同的，對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)按照某種需求進(jìn)行重要程度排名稱之為鏈接分析排名，其可以廣泛應(yīng)用在搜索引擎，文獻(xiàn)影響因子，以及發(fā)現(xiàn)恐怖組織重要成員等領(lǐng)域。本文首先介紹了鏈接分析排名的背景，隨后分析比較了橋接點(diǎn)排名的經(jīng)典算法的性能，，并重點(diǎn)分析了隨機(jī)游走中心性算法，對(duì)其算法的主要復(fù)雜度進(jìn)行改進(jìn)，提出一種隨機(jī)游走中心性快速算法。經(jīng)過(guò)基準(zhǔn)數(shù)據(jù)和人工生成數(shù)據(jù)的測(cè)試，快速算法能夠很好的發(fā)現(xiàn)網(wǎng)絡(luò)中流通性較好的節(jié)點(diǎn)，并極大的降低了算法復(fù)雜度。
[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.
【學(xué)位授予單位】：國(guó)防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP393.09

【參考文獻(xiàn)】

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

1 淦文燕;李德毅;王建民;;一種基于數(shù)據(jù)場(chǎng)的層次聚類方法[J];電子學(xué)報(bào);2006年02期

2 王莉軍;楊炳儒;謝永紅;;一種基于數(shù)據(jù)場(chǎng)的社區(qū)發(fā)現(xiàn)算法[J];計(jì)算機(jī)應(yīng)用研究;2011年11期

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

本文編號(hào)：2025091