基于随机游走的进化计算社区发现

网络结构关系错综复杂，在复杂网络上寻找最优的社区结构是一个NP-Hard问题，进化计算被认为是解决这类问题的有效方案，人们尝试利用群智能方法来搜索最优的社区结构。目前，针对包含节点属性的属性网络，基于进化计算的社区发现方法还面临若干挑战：（1）基因编码策略都直接或间接采用邻位编码，致使算法的搜索空间受限于拓扑结构，属性信息利用程度低，导致算法精度不足；（2）缺少对社区边缘度较小的节点的考虑，造成社区边界识别较低。针对上述问题，提出了一种基于随机游走的进化计算社区发现算法。首先，设计了一种基于拓扑及属性信息随机游走的社区初始化策略，以准确识别社区边界，提高社区发现的精度。其次，设计了综合考虑拓扑和属性的节点嵌入向量更新策略，使节点的属性信息能够在进化过程中被有效利用，以提高社区划分的质量。通过在真实和人工数据集上实验，验证了提出的新算法能够比现有方法得到更好的社区划分。

Community detection through random-walk-based evolutionary computation

It is a NP-hard problem to find the optimal community structure on complex networks. Evolutionary computation is considered to be an effective solution to this kind of problem. People try to search for the optimal community structure using swarm intelligence. At present, for attribute networks containing node attributes, community discovery methods based on evolutionary computation still face several challenges :(1) Their gene coding strategies directly or indirectly adopt adjacency coding, which results in the search space of the algorithm being limited by network topology and the low utilization of attribute information. The accuracy of the algorithms suffers ; (2) Lack of consideration of nodes with small community edge degree, resulting in the low community boundary identification. In this paper, a random walk based community discovery algorithm for evolutionary computing is proposed to solve these problems. First, a community initialization strategy based on the random walk on topology and attributes is designed to identify community boundaries precisely and improve the accuracy of community discovery. Second, a node embedding vector updating strategy considering topology and attributes is designed to allow the attribute information of nodes to be used in the evolution process effectively to improve the quality of community division. Experiments on real-world and artificial datasets verify that the proposed algorithm can achieve better community partitions than existing methods.