Research On Complex Network Community Detection Algorithm Based On Node Link Relationship

There are a large number of complex systems of various types in our real life,and the study of the structure of complex systems is a hot issue of concern.The network is the representation of complex system which consists of a number of nodes and edges.The nodes represent individuals of complex systems,and the edges represent relationships between individuals,such as social networks,transportation networks,and biological protein networks.A lot of research shows that there are obvious community structure characteristics on complex networks,that is,community members are connected closed,but the relationship between communities is sparse.The detection of community structure has important research significance and value in many fields such as personalized services,recommendation systems,link prediction and so on.This thesis focuses on the non-overlapping community detection and overlapping community detection,and aims to solve the problems that the current community detection algorithms ignore the link relationship between nodes,resulting in low quality,low accuracy and instability of community partitioning,and hopes to further improve the time efficiency of the algorithm.This thesis mainly includes the following two aspects:(1)Existing algorithms for obtaining non-overlapping community structures by using edge-deleting methods have disadvantages such as large time consumption and inaccurate partitioning results.To solve the problem,an improved non-overlapping community detection algorithm using edge-deleting with restrictions is proposed.The method obtains the link relationship between nodes by calculating the number of common neighbors,and distinguishes weak links and strong links in the network.Then it continuously deletes weak links in the network and preserves the community partitioning of optimal modularity.In addition,the restrictions are added in the deletion process to accelerate the iteration of the algorithm.Finally,the isolated nodes are detected and merged into initial communities for optimizing the community structure.Experiments on synthetic networks and real world networks prove that the proposed algorithm improves the time efficiency while ensuring the quality of community partitioning compared with other methods using edge-deleting.(2)Aiming at the problem that the current local expansion optimization algorithm ignores the strong and weak links between nodes in the network,resulting in unstable and inaccurate community partitioning,a new local expansion method by node-weighting to achieve overlapping community partitioning is proposed.The method also uses the link relationship between nodes to assign weight for each node,and selects the initial seed according to the order of node importance.Then it starts with the most important node as seed to expand local community until a locally optimal community is found by the improved the community fitness function.Iterate the seed selection and community expansion until each node is assigned to at least one community.Finally,in order to further improve the quality of community partitioning,the communities with high overlapping score are merged.Experimental results on synthetic networks and real world networks show that the proposed algorithm can further improve the quality and accuracy of community partitioning compared with other types of overlapping detection algorithms and traditional local expansion methods.