Research On Multi-Objective Community Detection Algorithm For Complex Networks And Decision-Making Strategies

There are a large number of complex systems in the real world, which can be abstractly described as complex networks. In recent years, complex network has attracted wide attention of scholars from different areas. Community structure is an important feature of complex network. Usually, the connection of nodes in the community is tight, while the connection of nodes between communities is relatively sparse. Detecting community structure can help analyzing the structure of complex network and finding potential functions of complex network. Thus, community detection for complex network is an important research topic, which has important theoretical meanings and realistic values. At present, multi-objective optimization algorithm is an important method to solve community detection problem. In this thesis, we study complex network community detection method based on multi-objective optimization and then propose a multi-objective community detection algorithm based on knee point. In order to help decision makers find the ideal partition from the partition set obtained by multi-objective community detection algorithm, two decision-making strategies for multi-objective community detection algorithm are proposed.The main research work and innovations of this thesis are shown as follows:(1) This thesis proposes a multi-objective community detection algorithm based on knee point. Current multi-objective community detection algorithms do not pay attention on key point appearing in the search process. Key point may correspond to good network community partition. In order to find potential good partition, this thesis proposes a multi-objective community detection algorithm based on knee point (KP-Net). The proposed algorithm can find knee point on the Pareto front, which refers to potential good partition. Different from other partitions, knee point corresponds to the partition where a small deterioration in one objective would lead to a large improvement in the other one. Thus, as key point on the front, knee point corresponds to the potential good partition. KP-Net is tested on both GN benchmark networks and real-world networks and compared with traditional typical community detection algorithms. Experimental results illustrate that KP-Net can better detect the community structures. Thus, KP-Net presented in this thesis is an effective community detection algorithm.(2) This thesis proposes two decision-making strategies for multi-objective community detection algorithm. As multi-objective community detection algorithm obtains a set of trade-off partitions, how to get an ideal partition from the large amount of partitions is a challenging problem for decision makers. Current multi-objective community detection algorithms usually select the partition with the highest value of modularity, but the partition with highest modularity value may not be the best partition. This thesis proposes two decision-making strategies for obtaining the ideal partition. The first one which based on knee point is to select the knee point from the set of partitions. Compared with other partitions in the set, knee point is interesting for decision makers. Thus, the first strategy selects knee point from the trade-off partitions and provides it to decision makers. The second strategy is to use the rule of majority voting, which means that two nodes are arranged into the same community if the two nodes belong to the same community in most of the partitions in the set. Thus, the second strategy provides a new partition based on all partitions get by multi-objective community detection algorithms. The proposed two decision-making strategies are then tested on both extended GN benchmark networks and real-world networks and compared with other typical community detection methods. Experimental results demonstrate that the proposed two strategies are effective and efficient to obtain an ideal partition of complex networks.