AN ENHANCED EVOLUTIONARY ALGORITHM WITH LOCAL HEURISTIC APPROACH FOR DETECTING COMMUNITY IN COMPLEX NETWORKS

摘要

These days, the properties of numerous systems in biology, engineering and sociology paradigms can be captured and analysed as networks of connected communities. The increasing emergence of these networked systems has fuelled the desire to study and analyse them into several sub-networks called communities. Community detection in a complex network is an ill-defined problem. Evolutionary Algorithms (EAs) have shown promising performance in community detection, but it's difficult to identify natural divisions included in such complex networks accurately and effectively without designing a problem-specific operator that exploits domain knowledge and guides the search process. Moreover, most of the contemporary studies only employ EA-based models to detect communities, which may not be adequate to represent the real community structure of networks due to the limitation in their topological properties. Thus, to enhance the predictive power of the state-of-the-art EA-based models, the main contribution of this research work is to put forward a framework that integrates evolutionary algorithm (EA) with a local heuristic approach. In the experiments, we select and optimise four well-known community detection models within the evolutionary algorithm framework, i.e. expansion model, scaled cost function model, conductance model, and internal density model. Then, the proposed heuristic approach is employed to locally aid along with the optimisation model, in which the nodes having dense intra-connections with nodes of other communities are moved to neighbouring communities. In the experiments, the performance of the optimisation models has been examined on both synthetic and real-world networks that are publicly available. The results show that the put forward local heuristic approach has a positive effect that significantly enhanced the existing optimisation models? detection ability.