We use cookies to improve your experience with our site.

基于多目标免疫算法的动态社会网络社区检测

Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm

  • 摘要: 1. 该文创新点
    社区结构是社会网络的重要特征之一,近年来,网络社区检测得到了极大的关注.在动态网络中,社区结构会随着时间不断演化,因此提出了比静态社区检测更具挑战性的任务.本文提出了一种带有局部搜索的多目标免疫算法,来解决动态网络中的社区检测问题.与传统的两步骤社区检测算法不同,本文所提出的算法可以在每个时间段,自动的提供一个能够同时平衡社区质量和时空代价的解. 2. 实现方法
    新算法采用非支配近邻免疫算法的框架同时优化模块度和归一化互信息两个目标,其中,模块度用于度量社区划分的质量,归一化互信息用于度量连续时刻网络划分的一致性.针对社区检测问题,设计了相应的重组算子、变异算子和局部搜索策略. 3. 结论及未来待解决的问题
    通过四个合成数据集和两个真实数据集,证明了与代表先进水平的算法相比,新算法不仅可以准确的发现社区结构,追踪社区演化,而且结果也更加稳定. 4.实用价值或应用前景
    本文算法能够发现自然和社会网络中随时间变化的社区结构演化规律,具有广泛的应用前景,可应用于社会组织识别与结构管理等社会网络分析、新陈代谢网络分析、蛋白质交互网络分析和蛋白质功能预测等生物网络分析,以及Web 社区挖掘和基于主题词的Web文档聚类和搜索引擎等众多领域.

     

    Abstract: Community structure is one of the most important properties in social networks, and community detection has received an enormous amount of attention in recent years. In dynamic networks, the communities may evolve over time so that pose more challenging tasks than in static ones. Community detection in dynamic networks is a problem which can naturally be formulated with two contradictory objectives and consequently be solved by multiobjective optimization algorithms. In this paper, a novel multiobjective immune algorithm is proposed to solve the community detection problem in dynamic networks. It employs the framework of nondominated neighbor immune algorithm to simultaneously optimize the modularity and normalized mutual information, which quantitatively measure the quality of the community partitions and temporal cost, respectively. The problem-specific knowledge is incorporated in genetic operators and local search to improve the effectiveness and efficiency of our method. Experimental studies based on four synthetic datasets and two real-world social networks demonstrate that our algorithm can not only find community structure and capture community evolution more accurately but also be more steadily than the state-of-the-art algorithms.

     

/

返回文章
返回