复杂网络社区挖掘中若干关键问题研究

发布时间：2018-05-11 09:19

本文选题：复杂网络 + 社区挖掘　；参考：《吉林大学》2012年博士论文

【摘要】：复杂网络社区挖掘是近十年最前沿的多学科交叉研究热点之一，已被广泛应用于恐怖组织识别、蛋白质功能预测、搜索引擎等诸多领域。本文基于蚁群算法、遗传算法、马尔科夫动力学方法，对社区挖掘问题进行研究。提出基于蚁群算法的社区挖掘方法RWACO。它结合了马尔科夫随机游走模型及集成学习思想，通过“强化社区内连接、弱化社区间连接”这一进化策略使社区结构逐渐呈现。实验表明，RWACO较一些代表性算法具有更高的聚类精度。提出基于遗传算法的社区挖掘方法GALS。它采用了基于图的编码策略LAR，以模块性函数Q作为目标函数。针对传统变异方法之不足，，我们面向LAR编码给出边缘基因的概念；推导出模块性函数Q之局部单调性；在上述两点的基础上提出了一个快速有效的局部搜索变异算法。在人工网络及真实网络上进行测试，并与当前代表性算法进行比较，实验表明了GALS的有效性。提出基于马尔科夫动力学的重叠社区挖掘算法UEOC。首先将原始网络与相应的退火网络融合为一个集成网络，在集成网络上给出一个基于约束的马尔科夫动力学新模型，以逐步呈现网络中的每个社区。然后基于局部社区函数“导电率”，设计一个有效的截方法，将已呈现出的社区抽取出来。如果网络具有重叠结构，被抽取出的社区则天然呈现重叠现象。实验表明，UEOC可快速有效的发现重叠社区结构。
[Abstract]:The mining of complex online communities is one of the most advanced interdisciplinary research hotspots in the past decade. It has been widely used in terrorist tissue identification, protein function prediction, search engine and many other fields. Based on ant colony algorithm, genetic algorithm and Markov dynamics, community mining problem is studied in this paper. A community mining method based on ant colony algorithm (RWACO) is proposed. It combines Markov random walk model with the idea of integrated learning, and makes the community structure appear gradually through the evolutionary strategy of "strengthen the connection within the community and weaken the connection between the communities". Experiments show that RWACO has higher clustering accuracy than some representative algorithms. A community mining method based on genetic algorithm (GALS-based) is proposed. It adopts the graph-based coding strategy LAR and takes the modular function Q as the objective function. In view of the shortcomings of traditional mutation methods, we give the concept of edge gene for LAR coding, deduce the local monotonicity of modular function Q, and propose a fast and effective local search mutation algorithm based on the above two points. The experiments on artificial network and real network show the effectiveness of GALS. An overlapping community mining algorithm based on Markov dynamics is proposed. Firstly, the original network and the corresponding annealing network are merged into an integrated network, and a new constrained Markov dynamics model is presented in the integrated network to gradually present each community in the network. Then, based on the local community function "conductivity", an effective truncation method is designed to extract the existing community. If the network has overlapping structure, the extracted community is naturally overlapped. Experiments show that UUOC can quickly and effectively find overlapping community structures.
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP311.13;O157.5

【参考文献】