社区结构分析关键技术研究

发布时间：2018-06-16 03:34

本文选题：社会网络 + 社区发现　；参考：《国防科学技术大学》2012年硕士论文

【摘要】：随着电子信息技术的发展，网络作为一个重要的媒介走进了千家万户，微博，facebook，QQ已经成为人们日常交往不可或缺的工具。这些由人与人之间的交互关系抽象成的网络称之为社会网络，广义的社会网络还包含基因网络，论文引用关系网等自然形成的网络，也称之为自然网络。这些网络内部蕴含着丰富的信息等待我们去发现，对自然网络的研究已经成为当前的一个热点研究课题。本文主要就社会网络分析中的社区发现和链接分析排名进行研究。自然网络最重要的特性就是聚簇结构，其聚簇内部连接紧密，聚簇之间连接稀疏。准确识别网络中的聚簇结构称之为社区发现。其可以广泛应用于恐怖组织识别、蛋白质作用分析、电子商务等领域。本文首先分类介绍了社区发现的经典算法，然后分析了复杂度较低的WF算法，并针对其算法的不足，通过改进流模型引入节点的聚簇优先遍历以及新的社区评价准则，提出一种复杂度较低的社区发现算法。通过网络分析基准数据，验证了算法的有效性。传统的社区发现都是针对整个网络数据，其划分的结果是整个网络的社区结构。计算效率不高且大部分社区对用户没有意义，同时部分自然网络无法获取完整的数据。本文在聚簇优先遍历的基础上，通过二次切割的思想提出一种局部社区发现算法，在利用网络部分数据的基础上，提取出种子节点的自然归属社区，通过基准数据和人工生成的数据进行试验，试验结果显示，本文算法能够很好的发现种子节点的局部社区结构，且复杂度较低。网络中节点的重要程度是不同的，对网络中节点按照某种需求进行重要程度排名称之为链接分析排名，其可以广泛应用在搜索引擎，文献影响因子，以及发现恐怖组织重要成员等领域。本文首先介绍了链接分析排名的背景，随后分析比较了桥接点排名的经典算法的性能，，并重点分析了随机游走中心性算法，对其算法的主要复杂度进行改进，提出一种随机游走中心性快速算法。经过基准数据和人工生成数据的测试，快速算法能够很好的发现网络中流通性较好的节点，并极大的降低了算法复杂度。
[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

【参考文献】