【作者】 吕伟明；

【导师】 陈晓云；

【作者基本信息】 兰州大学 ， 计算机软件与理论， 2013， 硕士

【摘要】 21世纪,随着信息技术的普及发展以及各种社交网站的流行,研究人员可以便捷地收集复杂社会网络数据集,这极大程度上促进了人们对复杂社会网络的研究分析。研究表明复杂社会网络具有小世界性、无尺度性、模块性等特性。社团目前尚无明确统一的定义,一般认为是满足社团内部节点联系紧密而社团间节点联系稀疏的节点集合。社团检测算法一直是复杂社会网络中的一大研究热点,主要研究如何从复杂社会网络中发现高质量的社团结构。清晰的社团结构对研究分析复杂社会网络问题有极大的帮助。本文的主要工作是社团检测算法研究,文中共提出了三个社团检测相关算法。第一,本文提出一种基于随机游走改进的节点相似性计算方法(RWS),可用于根据网络的拓扑图及权重信息快速计算网络中节点的相似性：第二,本文提出一种基于线性阈值模型的社团检测算法(LTCD),该算法通过初始社团不断激活边界节点的方式来扩展社团；第三,本文还提出一种基于协同方法的社团检测算法(CMCD),该算法旨在提高社团检测算法的性能。这三个算法出发点和侧重点各不相同,RWS是用来计算节点相似性,LTCD是一种简单的社团检测算法,而CMCD是一种提升社团结构检测质量的框架算法。本文在多个真实和人工合成社会网络数据集上进行实验,从模块度、准确率和标准互信息等方面对实验结果进行分析。实验结果表明本文提出的算法能得到较高质量的社团结构。更多还原

【Abstract】 Since the21st century, with the development and popularization of information technology, and a variety of popular social networking sites, researchers can easily collect the complex social network datasets, which has largely inspired researchers to study complex social networks. Studies have shown that complex social networks have certain features such as small-world, scale-free and modularity. Generally, community is identified as a set of nodes whose links inside are more densely than links outside. Community detection algorithm which has always been a hot research topic, mainly studies how to find the high-quality of the community structure in complex social network. Good community structure is useful for complex social network analysis.Community detection is the key issue of finding the structure and understanding the function of many natural and artificial systems. In this paper, the community detection algorithm is the main study which is we focused on, we have achieved some results. First, we present a similarity calculation method based on random walks (RWS), which is used to quickly calculate the nodes’ similarity according to the topology and weight information of the network. Second, a community detection algorithm (LTCD) based on the linear threshold model is proposed, which continuously activated the boundary node to extend the initial community. Finally, the paper also proposes a method based on cooperative method (CMCD), which is used to optimize the community structure found by community detection algorithm and improve its stability.In this paper, experiments on some real and artificial synthetic social network datasets prove that three algorithms mentioned above are feasible and can detect high-quality community structure.更多还原