块模型和复杂网络社区检测

发布时间：2018-07-05 16:01

本文选题：进化算法 + 块模型　；参考：《西安电子科技大学》2014年硕士论文

【摘要】：本文以进化算法为基础,先后研究了基于图分割的块模型问题和基于分解的多目标进化在社区检测上的问题。论文主要进行了以下三个工作:1.研究进化算法求解块模型问题。算法过程包括利用提取完全子图的思想进行种群初始化,采用冲突交叉算子产生子代,再采用修复操作优化子代。最后,经过反复迭代,算法逐渐收敛,目标函数值达到最大。通过在四组不同来源的网络上分别用进化算法EA和分组遗传算法GGA做块模型分割,证明了本章提出了基于进化算法EA的块模型方法在处理大规模网络上具有明显的优势,尤其在节点数较多和边密度较大的网络上。2.提出了一种基于模块度的符号网络多目标社区检测方法。文中针对符号网络的特性,首先定义了两个目标函数,然后采用分解的方法使得种群不断进化,其中遗传操作过程包括采用提取完全子图的方法对种群进行初始化,单路交叉算子产生子代和基于正邻居的变异操作,从而使个体不断向最优解收敛。实验中通过分析符号网络呈现的Pareto前端验证了本章提出的两个多目标函数在符号网络社区检测上是可行的,通过与对比算法的实验结果比较、分析,证明了本章提出的基于模块的MOEA/D在呈现网络不同层次结构和提取小社区方向上具有明显的优势。3.提出了一种基于密度型的多目标社区检测算法。此算法在是第二个工作的基础上,重新定义了两个目标函数,使得此算法不仅可以检测符号网络的社区结构还可以检测无符号网络的社区结构。文中详细描述了目标函数的具体定义和其动机来源,遗传操作同样包括提取完全子图的方法、单路交叉算子和基于邻居的变异。通过分别对符号网络和无符号网络做社区检测,验证了本章提出的两个多目标函数在社区检测上是可行的,通过与基于模块度MOEA/D及其他算法的实验结果比较,证明了本章提出的基于密度型的MOEA/D是一种更全面更高效的社区检测方法。
[Abstract]:In this paper, based on evolutionary algorithm, the block model problem based on graph segmentation and the problem of multi-objective evolution based on decomposition in community detection are studied successively. The thesis mainly carries on the following three work: 1. The evolutionary algorithm is studied to solve the block model problem. The algorithm includes initializing the population using the idea of extracting the complete subgraph, using the collision crossover operator to generate the offspring, and then using the repair operation to optimize the offspring. Finally, after repeated iteration, the algorithm converges gradually and the value of the objective function reaches the maximum. By using evolutionary algorithm EA and packet genetic algorithm GGA as block model segmentation in four groups of networks from different sources, it is proved that the block model method based on evolutionary algorithm EA has obvious advantages in dealing with large-scale networks. Especially in the network with more nodes and more edge density. In this paper, a multi-target community detection method based on modularity is proposed. In this paper, two objective functions are defined for the characteristics of symbolic networks, and then the decomposition method is used to make the population evolve continuously. The genetic operation process includes the initialization of the population by extracting the complete subgraph. The single path crossover operator generates offspring and mutation operations based on positive neighbors, which makes the individual converge to the optimal solution. In the experiment, the Pareto front-end presented by symbolic network is analyzed to verify the feasibility of the two multi-objective functions proposed in this chapter in community detection of symbolic networks. It is proved that MOEA / D proposed in this chapter has obvious advantages in presenting different network hierarchies and extracting small communities. A density-based multi-objective community detection algorithm is proposed. This algorithm redefines two objective functions on the basis of the second work so that the algorithm can not only detect the community structure of the symbolic network but also the community structure of the unsigned network. In this paper, the definition of objective function and its motive source are described in detail. The genetic operation also includes the method of extracting complete subgraph, single path crossover operator and neighbor based mutation. The two multiobjective functions proposed in this chapter are proved to be feasible in community detection by doing community detection for symbolic network and unsigned network, respectively. The results are compared with the experimental results based on Modular MOEA-D and other algorithms. It is proved that the density-based MOEA / D is a more comprehensive and efficient method for community detection.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O157.5;TP393.09

【相似文献】