Parallel Discrete Particle Swarm Optimization For Community Detection

Most of systems can be represented as complex network and the community detection can be applied to various fields.Community detection has great application in many areas.Usually,community detection is formulated as an optimization problem.By optimizing the community division index to discover communities.However with the rapid development of the Internet,social networks,online shopping and Internet of Things are popular.These areas generate vast amounts of data to analysis.These large-scale networks are great challenges for the traditional community detection algorithm,regardless of the results of the community partition or run time of algorithm as well as the memory capacity of the computing platform.Hence,study of large-scale networks for community detection is of great significance.An effective algorithm is needed to deal with such a problem.Based on the development of big data,in this thesis,we will put forward a train of thought to solve the problem of large-scale complex networks.The detail is described as follows:(1)A parallel particle swarm optimization algorithm based on Apache Spark for community detection is put forward.Relying on the existing distributed computing technology,we combine the particle swarm optimization with Apache Spark.As these particles in PSO have few interaction between each other.It is suitable for PSO to do parallel computing.Direct coding of population is adopted and Resilient Distributed Datasets are used.This makes it possible to parallel updating the information of particles.Using the broadcast variable of the distributed platform,the adjacency matrix of the network is shared among multiple servers.Compared with the single task processing,parallelization of optimizing objective function by cluster can greatly speed up the efficiency of the algorithm.(2)Based on the graph calculation framework of distributed computing platform,we propose a parallel particle swarm optimization algorithm based on message aggregation for network community detection.The large-scale network structures are stored in the system as distributed graphics.It solves the memory bottlenecks of stand-alone environment.Then,community detection of complex network is modeled as a optimization problem.The modularity density is the objective function.We use distribution of the message aggregation instead of adjacency matrix to calculate modularity density.For one thing,through the horizontal expansion of the cluster in the network we can increase the processing capacity,for another the speed of algorithm execution is accelerated by distributed graphs.In order to prove the validity of the algorithm,our algorithm is applied to benchmark and small-scale real-world network and make comparison with other mainstream community detection algorithms.The results show the effectiveness of our algorithms.At the same time,we also test the algorithm on real-world large-scale networks.The experiments show that our proposed algorithm is effective and suitable for solving large-scale network community detection problem.