Community Detection On Large Network By Distributed Evolutionary Algorithm

The rapid development of information industry has brought human society with the great convenience in the social,shopping,travel and many other areas.There are many examples that illustrate this fact,like online shopping,ticketing,chatting with friends and so on.As the Internet companies provide services to the whole society,with using those services,we will produce massive amounts of data,such as the shopping records of consumers on Taobao,the messages shared by users on Microblog,and thumbs-up in“Moments”of We Chat.In order to provide better services,these Internet companies process the massive data to find consumer preferences and recommend that things the consumer like.In the context of processing massive data of consumers,network data mining has become a hot research area.Community detection is an important tool of network data mining that analyzing the network structure and dividing whole network into the communities.As a class of the community detection algorithms,Multi-objective Evolution Algorithm(MOEA)has many advantages in community detection,such as heuristic searching and getting multi-level hierarchical results at the same time.However,the traditional evolutionary algorithm is limited by computation resources of PC,while it is used to solve community detection on large-scale network.In this thesis,to overcome the challenges of traditional MOEAs in detecting communities on large-scale networks,we implement the MOEA on Spark-a distributed computing framework,and use it to resolve the community detection on large network.We list our main work and innovations at here:1)We designed a distributed evolutionary algorithm for the commuity dectection on large scale network.To deal with community detection on large-scale network,we design the methods of population storage,initialization and the strategy of crossover and mutation for evolution.By analyzing the main current of objective function and the main purpose of community detection,we take the features of social network and the traits of distributed computing framework and design a couple of objective functions for distributed computing.2)We designed another distributed evolutionary algorithm based on Resilient Distributed Dataset.The population is broken up into serval small populations with the partitions of Resilient Distributed Dataset.These small populations employ with different crossover and mutation probabilities.3)This article is experimented on the artificial networks called Benchmark and the real world networks made up by small networks and large networks.The results of those experiments show that the proposed algorithm is effective in dealing with community detection on large-scale networks and still has good performance when dealing with small network.