Research On Community Detection Algorithms In Complex Networks

Community detection in complex network analysis remains up to this date a quite challenging problem spanning many applications in various disciplines such as biology,physics and social network.Informally,a community is a densely connected sub-network that is only sparsely linked to the remaining network.Such communities often exist in social networks,biological networks,traffic networks and wireless sensor networks.The community structure can reflect the dynamic characteristics and functions of complex networks.The detection of community structures can be exploited for a diverse range of applications such as terrorist organization identification,protein function prediction,personalized recommendation,information retrieval,and so forth.Recently a large number of methods have been developed for this problem,such as modularity based optimization algorithm and label propagation algorithm(LPA).However,few algorithms can achieve satisfactory results in both effectiveness and efficiency at present.We studied the problem in this thesis and the main motivations and contributions of our research are as follows:(1)Since the problem for community detection with modularity maximization is known to be NP-complete,it is always desirable to explore new efficient meta-heuristic for uncovering community structures within a reasonable amount of computation time.This thesis proposed a hybrid meta-heuristic called iterated carousel greedy(ICG)algorithm for solving community detection problem with modularity maximization.The proposed ICG algorithm generates a sequence of solutions by iterating over a greedy construction heuristic using destruction,carousel and reconstruction phases.A local search procedure with strong intensification is applied to search for a better solution in each iteration.Compared with the traditional iterated greedy(IG)meta-heuristic,the improved method employs the carousel greedy procedure to direct the search towards the better solution space.A simulated annealing-like acceptance criterion is utilized for avoiding the stagnation situations of search process.The experimental results on synthetic and real-world networks show the superior performance of the proposed method over the existing meta-heuristic methods in the literature.(2)Label propagation algorithm is an efficient approach to detect community structures in complex networks which is easy to implement However,some drawbacks,such as the random updating order and tie-breaking strategy in LPA make the algorithm unstable and poor of accuracy,sometimes even lead to the formation of a monster community.In this thesis,an improved LPA called LPA-INTIM is proposed for solving the community detection problem.Firstly,an intimacy matrix is constructed using local topology information for measuring the intimacy between connected nodes.And then,the node importance is calculated to ensure that nodes are updated in a specific order.Finally,the label influence is evaluated for updating node label during the label propagation process.In addition,we introduce a novel tightness function to improve the stability of the proposed algorithm.By the comparison with the representative label propagation based algorithm in the literatures,experimental results on real-world and synthetic networks show that the proposed LPA-INTIM has gained obvious performance improvements in terms of efficiency and effectiveness.