Research Of Community Detection Algorithms Based On SOM And GSA

Complex network is a kind of abstract description of complex system,which contains a large amount of entities that can be abstracted as nodes,and the relationships among them can be abstracted as edges.Such as,a social network can be abstracted by the relationship among the users in the social system,and urban road network can be abstracted by the relationship among the road sections in the urban road system.The research has found that community structure is one of the main characteristics of complex networks.Communities are composed of nodes with close internal connections and sparse connections among communities that are often corresponding to the functional modules in the system.Therefore,extracting communities from the network can provide an effective way to understand the relationship between network functions and structures.However,the community structure in some networks is unknown,which needs to be detected by using appropriate algorithms,so that the relationship between the components of the system and the function of the system can be deeply understood.Researchers have proposed many community detection methods from various perspective.This dissertation also proposes two community detection methods which are based on SOM(Self-Organizing Map)and GSA(Gravitational Search Algorithm),respectively.(1)SOM based community detection method,SOMCD.This method first removes the nodes with only one neighbor;then constructs the attribute matrix by using the adjacency and similarity between nodes,and randomly selects several columns of the attribute matrix as the input vector to train the SOM.Next,the method uses competitive learning to obtain the winning neurons in the competition layer which are most similar to the input vector,and then adjusts the weight vectors of the winning neurons and other neurons by adopting different methods.After several iterations,the input vectors with the same winning neurons can be mapped to the same community.In addition,this paper embeds the community detection process into the above training process.After each training session,the modularity of the corresponding community structure is calculated,and the community structure corresponding to the maximum modularity is recorded.When the training process is complete,the community structure with the largest modularity is the optimal result.Finally,a post-processing process is used to add the removed nodes into the communities where their neighbors belong to,and merge some too small communities,so as to obtain a high-quality community structure.(2)GSA based community detection method,GSACD.This method first removes the nodes which have limited contribution to the community structure.Then,the multiple search solutions are obtained by running LPA(Label Propagation Algorithm)and the improved algorithm of LPA,and each search solution can be represented by a discrete vector by the discrete coding way.In the vectors,the value of each dimensionality represents the community number of each node,so that the initial population can be acquired.Specifically,each particle in the population represents a community structure.Considering that the similarity among communities and nodes has a certain effect on the structure of communities,this paper rewrites the formula for calculating gravity.With the change of the gravitational force between particles,this dissertation continuously updates the mass,acceleration,and speed of particles,and rewrites the position updating formula of the particles through the labels of their most neighbors in each dimension of the community structure,which means updating the membership of nodes.At the same time,the modularity is used as the fitness function to calculate the mass of the particles.After multiple iterations,the position of the particle with the highest mass is the optimal community structure.Finally,the method obtain the final community structure through adding the removed nodes of pre-processing process into the communities where their neighbors belong to in the post-processing process.The two methods proposed in this paper can automatically detect the number of communities in which the GSACD method does not need to set any parameters.Moreover,in order to verify the effectiveness of SOMCD and GSACD methods,this dissertation runs the two methods and some influential algorithms on the real-world and synthetic networks with different scales,and evaluates the quality of community structure by modularity and NMI.The comparison and analysis of the experimental results show that SOMCD and GSACD can detect the community structure with high quality stably.