Research On Community Detection Algorithms In Complex Networks

Community structure is one of the most important properties in complex networks.Detecting such communities plays an important role in a wide range of applications,including but not limited to cluster analysis,recommendation systems and understanding the behavior of complex systems.Researchers have derived many algorithms to discover the community structures of networks,including information theoretic approaches,dynamic label propagation,and modularity optimization techniques.However,discovering communities is a challenging task,and there is no single algorithm that produces the best results for all networks in terms of effectiveness and efficiency.Therefore,despite many elegant solutions,discovering communities remains an active area of research.We studied the problem in this thesis and the main motivations and contributions of our research are as follows:(1)Community detection can be transformed into modularity maximum problem which is an NP-complete problem.We propose a novel iterated greedy algorithm based on modularity contribution for maximizing modularity value of complex networks,which is based on an iterative process that combines a destruction phase and a reconstruction phase.During the destruction phase,the algorithm destructs community structures of a certain percent nodes having lower modularity contribution.In the reconstruction phase,their community structures are reconstructed by using the well-known Louvain construction heuristic.A local search procedure can be applied after the reconstruction phase to improve the performance of the algorithm.Experiments on the computer-generated networks and real-world networks show that our algorithm is very efficient and competitive compared with several state-of-the-art methods.(2)Label Propagation Algorithm(LPA)is a simple and fast community detection algorithm which is not accurate enough because of its randomness.Some advanced versions of LPA have been presented in recent years,but their accuracy still need to be improved.In this paper,we proposed an improved LPA with two stages.The first stage involved calculating best-close node of each node according to local structural information and obtaining primary community structure,which is used to assign the initial labels.In stage two,the initial labels of nodes resulted from stage one will be injected as seeds into an improved LPA,which increases accuracy based on node influence.Experiments on real-world and synthetic networks show that our proposed algorithm can mitigate the shortcomings of LPA and significantly improve the quality of detected results compared with recent competing algorithms in the literature.