基于社区性质的社区发现和基于局部视图的社区演变追踪研究

发布时间：2018-03-09 19:47

本文选题：社区发现　切入点：真实社区　出处：《电子科技大学》2016年博士论文　论文类型：学位论文

【摘要】：网络是对许多现实系统的一种既简单又形象的表达方式,对网络进行研究有助于人们理解真实世界。许多现实网络,比如社交网、作者合作网、蛋白质交互网、万维网等,都具有一种重要的中观结构——社区结构。一个网络中的社区结构是网络中的社区划分,即将节点划分到不同的社区,社区内节点连接更加紧密,而社区之间的连接相对稀疏。社区发现能够探知网络的隐藏结构,发现网络的潜在信息,对认识和理解网络的拓扑结构起着重要的作用;社区演变追踪能够探知社区的改变情况,揭示网络的内在动向,对捕捉和掌握网络的发展趋势起着不可忽略的作用。因此,对社区发现和社区演变追踪开展研究具有重要的意义。在社区发现方面,本文研究了个人社交网络中的社交圈发现和现实大规模网络中的社区发现,提出了相关的社区发现算法。在社区演变追踪方面,本文研究了动态网络在每个时刻的社区发现和相邻时刻的社区结构匹配,提出了相关的社区演变追踪算法。本文的主要工作如下:1.针对个人社交网络中的社交圈发现问题,提出了基于加强链聚类的社交圈发现算法。社交圈发现属于社区发现,本文在对真实社交圈分析的基础上,将节点属性信息和网络结构信息整合到边上,提出了一种加强链聚类算法。实验结果表明,与目前的社交圈发现算法相比,所提出的算法可以更快速更准确地完成个人社交网络中的社交圈发现。2.为了能更加准确地发现现实大规模网络中的社区,提出了两种基于加权策略的社区发现算法。首先研究了大规模网络中的真实社区结构,发现了社区结构具有的一种性质;然后基于此设计了一种加权策略,并在此加权策略的基础上提出了两种社区发现算法。在现实网络上的实验结果表明,所提出的基于加权策略的算法可以更准确地发现真实社区。3.提出一种基于加权局部视图的社区发现算法。该算法结合分析到的社区性质探索节点对社区结构的局部视图,然后整合节点的局部视图得到社区结构。在现实网络上的实验结果表明,所提出的基于加权局部视图的算法在发现大规模网络中的社区时存在效率优势,且能更准确地发现真实社区。4.在社区演变追踪方面,提出了一种增量式的局部动态社区演变追踪算法。该算法分两个步骤:1)为了快速发现动态网络在每个时刻的社区结构,该算法在每个时刻只关注网络中发生变化的节点,通过探索变化节点的局部视图对社区结构进行更新;2)为了快速地匹配相邻时刻的社区结构以追踪社区的演变行为,该算法基于变化节点在变化前后的社区归属关系,构建一个部分社区演变图,并通过搜索部分社区演变图对社区的演变行为进行追踪。实验结果表明,当网络变化平滑时,所提出的局部动态社区演变追踪算法能更快速地完成社区演变追踪;当网络变化剧烈时,所提出的算法也具有一定的优势。
[Abstract]:The network is a kind of simple and vivid expression of many real systems, the network research can help people understand the real world. Many real networks, such as social networks, the author collaboration network, protein interaction networks, the world wide web, there is a kind of important intermediate structure, community structure community structure. A network is a network of community division, will be divided into different nodes within the community, community and community connections more closely, the connection between the relatively sparse. Community discovery can detect hidden structure of the network, find the potential information network, plays an important role in understanding the network topology; to ascertain the change of community evolution track community, internal trends reveal network, to capture and plays an irreplaceable role to grasp the development trend of the network. Therefore, the community discovery and community play Change tracking research has important significance. Found in the community, this paper studies the personal social network in the social circle and reality found in large-scale network community discovery, put forward the relevant community discovery algorithm. In the evolution of the community tracking, in this paper, the dynamic network community structure at each time was found and the adjacent community moment, put forward the relevant community evolution tracking algorithm. The main work of this paper are as follows: 1. for the personal social network social circle to find problems, put forward to strengthen the clustering algorithm that chain based social circle social circle. That belongs to the community, based on the analysis of the real social circle, the attribute node information and network information integration to the side, put forward a kind of enhanced chain clustering algorithm. The experimental results show that with the current social circle discovery algorithm, proposed the The algorithm can more quickly and more accurately complete the personal social network social circle found.2. more accurately find the real large-scale network community to, put forward two kinds of community discovery algorithm based on weighted strategy. Firstly, the real large-scale network community structure, found a community structure with nature; then based on this design a weighted strategy, and based on the weighted strategy put forward two kinds of community detection algorithms in real network. The experimental results show that the proposed algorithm based on weighted strategy can more accurately find the real community discovery algorithm.3. proposed a weighted partial view of community based on the algorithm. With the exploration of community property of local view of community structure analysis to the local node, then the node view integration community structure. Experimental results on the network in reality The results show that the proposed algorithm based on weighted local view in the discovery of large scale network community has efficiency advantages, and can more accurately find the real community.4. in the community evolution tracking, we propose a local dynamic community an incremental evolution tracking algorithm. The algorithm consists of two steps: 1) in order to quickly find the community structure of the dynamic network at each time, the algorithm only focus on changes in the network nodes in each moment, the community structure was updated by local view to explore changes of nodes; 2) to community structure quickly match the adjacent time to track the evolution of the community, based on the change of the node before and after the changes belonging to the community relations, construct a part of the community evolution map, and search through community evolution evolution behavior of Community Tracking. The experimental results show that when the network changes When smoothing, the proposed local dynamic community evolution tracking algorithm can track community evolution more quickly. When the network changes dramatically, the proposed algorithm has certain advantages.

【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.09;TP311.13

【相似文献】