社会网络中社区发现与动态演化的研究

发布时间：2018-06-30 05:05

本文选题：社会网络 + 动态社区发现　；参考：《福州大学》2014年硕士论文

【摘要】：近年来,对社会网络中社区结构相关研究的关注程度已经超过了对社会网络中小世界、无标度、幂律特性等基本复杂网络属性的关注程度。挖掘社区结构对研究社会网络具有重要意义,社会网络的规模日益庞大且呈动态特性,给传统社区发现算法带来了巨大挑战。因此,本文将针对社区发现问题,开展了大规模社会网络中的社区结构挖掘及动态社会网络的社区发现快速算法的研究工作。本文将社区发现问题转换为优化问题,提出了分层优化框架,目的在于将社区发现问题分而治之,降低网络规模,增大传统优化方法适用范围以及提高解的质量。该分层框架包括三个层次,分别是：核心区域挖掘、孤立点修复以及在新构建的网络中进行优化。随后本文基于分层框架设计的思想提出了组合算法DBPSO,该算法包含：基于密度聚类的核心区域发现、三种孤立点修复策略以及在新构建的网络中利用改进粒子群算法优化模块度,文中证明在新构建的网络中优化模块度与在原网络中优化模块度的一致性。其中改进粒子群算法中引入了遗传算法的变异算子,加速粒子群优化算法的收敛性。在人工网络数据集和大量不同规模真实网络数据集中的实验表明,本文提出的算法能够有效发现网络社区结构。动态社会网络社区发现有助于进一步分析整体网络特性和发展规律。在动态网络分析中,本文基于增量分析的思想,提出标签传播与增量相关节点相结合的算法ILPA。该算法合理地利用了动态社会网络在相邻时段的社区结构变化缓慢的特性,仅对第一个采样时段的网络快照采用静态社区发现算法分析,研究t时段的网络的社区结构时,则以前面t-1时段的社区发现结果为基础,并结合t时段网络的网络增量相关节点共同决定当前网络的社区结构。ILPA算法既具有传统基于增量分析的动态社区检测算法的高效率,且无需社区数目的先验知识,并对网络结构自适应,对网络突变情况也有很好的处理结果。在人工动态网络数据集和真实动态网络数据集中的实验表明,ILPA算法能够有效挖掘动态网络中的社区结构,且具有较好的稳定性与较高的执行效率。
[Abstract]:In recent years, attention to community structure related research in social network has been paid more attention to the basic complex network attributes, such as small and medium world, scale-free, power law and so on. Mining community structure is of great significance to the research of social network. The scale of social network is increasingly large and dynamic, and it is given to the traditional society The area discovery algorithm has brought great challenges. Therefore, this paper will focus on community discovery problems, carry out the research work of community structure mining in large-scale social network and the fast algorithm of community discovery in dynamic social network. This paper transforms the community discovery problem into optimization problem, and proposes a hierarchical optimization framework. The purpose is to send the community to the community. This hierarchical framework includes three levels: core area mining, isolated point repair and Optimization in newly built networks. Then this paper proposes a combination algorithm DBPSO based on the idea of the design of the layered framework. The algorithm includes the core region discovery based on density clustering, three outlier restoration strategies and the optimization of the module degree by improved particle swarm optimization (PSO) in the newly constructed network. It is proved that the optimization of the module degree in the newly constructed network is consistent with the optimization of the module degree in the original network. The mutation operator of the algorithm accelerates the convergence of the particle swarm optimization algorithm. The experiments on the artificial network data set and a large number of real network data sets in different scale show that the proposed algorithm can effectively find the network community structure. The dynamic social network community discovery is helpful to analyze the overall network characteristics and the development rules. In dynamic network analysis, based on the idea of incremental analysis, this paper proposes a combination of label propagation and incremental correlation node (ILPA.). The algorithm makes use of the characteristics of the slow change of community structure in the dynamic social network in the adjacent period, and only the network snapshot of the first sampling period is analyzed by the static community discovery algorithm. The community structure in the T period is based on the community discovery results in the previous T-1 period, and combined with the network increment related nodes of the T period network to determine the community structure.ILPA algorithm of the current network not only has the efficiency of the traditional dynamic community detection algorithm based on the incremental analysis, but also does not need the prior knowledge of the community number. The adaptive network structure also has good results for the network mutation. The experiments on the artificial dynamic network data set and the real dynamic network data set show that the ILPA algorithm can effectively excavate the community structure in the dynamic network, and has better stability and higher execution efficiency.
【学位授予单位】：福州大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09

【相似文献】