Research Of Community Detection Algorithms Based On Multi-attribute Decision Making And Genetic Strategy

Real world systems can be modeled as complex networks,using nodes and edges to represent the participants in the system and their interactions.Community is one of the important characteristics of complex networks.By studying community structure and exploring the corresponding relationship between structural and functional characteristics,it is possible to optimize the functions of complex networks and real systems.Therefore,community detection is of great significance for understanding network structure and fully exerting network value.Multiplex network is a network composed of multiple single-layer networks,which is a special case of multi-layer networks.In multiplex networks,each layer corresponds to a type of interaction,which can be used to represent different interaction modes between the same entities,and can more fully reflect the information in the actual system.Community detection in multiple networks often requires aggregating the connection information of nodes in each layer to more accurately detect the community structure.Based on previous research,this paper proposes a single layer network community detection algorithm TMGA using genetic strategy,and multiplex network community detection algorithms MTMGA and TLVA using hierarchical fusion based on the multi-attribute decision making technology TOPSIS(Technology for Order Preference by Similarity to an Ideal Solution).(1)Community detection algorithm TMGA based on genetic strategy.This algorithm uses the TOPSIS method in multi-attribute decision making technology to synthesize the advantages of the four similarity measures in a single layer network,obtaining a similarity score of T-Score that can measure the similarity relationship between nodes in the network,and using T-Score as the weight of edges between nodes to obtain a new single layer weighted graph.TMGA uses matrix encoding and the framework of NSGAII algorithm on this weighted graph.First,TMGA initializes the community affiliation and connectivity between nodes,uses the affiliation matrix and the adjacency matrix to encode,and designs new crossover and mutation methods based on matrix operations to iteratively generate new community structures.At the same time,TMGA constructs external and internal goals as fitness functions based on weighted modularity to measure the quality of the community.After the iteration ends,TMGA selects the solution of the first Pareto frontier as the community structure of the single layer network.(2)MTMGA and TLVA algorithms based on hierarchical fusion ideas.MTMGA and TLVA use multi-attribute decision making technology TOPSIS to fuse the similarity of nodes in different layers of multiplex networks,obtain a similarity score MT-Score,and aggregate the multiplex networks into a single layer weighted graph.In this paper,a genetic strategy based on matrix coding is used on the weighted graph to extend TMGA to multiplex networks to form the MTMGA algorithm.The simplified multiplex modularity and shared community redundancy connection rate are used as fitness functions,and the solution of the first Pareto frontier is selected as the community structure of the multiplex networks.At the same time,we implement the TLVA algorithm based on the weighted modularity on the weighted graph.First,we treat each node in the weighted graph as a separate set,and move the node into the neighbor set with the largest modularity increment and greater than 0.Then,each set is compressed into a supernode,and the total weight of the edges within the set is taken as the weight of the node’s self loop.Multiple edges between different sets are taken as one edge,and the total weight of the edges between neighboring sets is taken as the weight of the new edge.Repeat the above steps to obtain the community structure of multiplex networks.This paper conducts experiments on TMGA,MTMGA,and TLVA algorithms on multiple complex networks,and compare the results of community detection with other algorithms.Experiments show that TMGA,MTMGA,and TLVA algorithms have superior community detection capabilities compared to other algorithms.