Research On Algorithms Of Detecting Community Structure In Complex Networks

The community in complex networks is thought of as a set of nodes where nodes are densely interconnected and sparsely linked to other parts of the networks.The research of community structure in complex networks has positive theoretical and practical effects on understanding the functions of complex networks,analyzing topology structure of complex networks,detecting potential patterns of complex networks and forecasting behaviors of complex networks.The detection of community structure is widely applied into social networks,terroristic organization uncovered,biological network analysis,Web mining,clustering of Web document,search engine,etc.Community structure detection has become focus of interdisciplinary research area.In this work,the research of complex network community structure detection is based on three aspects: the fractal characteristics of complex networks,heuristic optimization,and multi-scale community.Firstly,the algorithm which is named FCUC(Fractal Cluster for Uncovering Community)is proposed.The network nodes are clustered by box-covering algorithm in FCUC.Complex networks is covered by some boxes.The nodes in same box is clustered,and the cluster is renormalize a node of new network.A new network is created by renormalization and box-covering algorithm.In the new network,the weight of edge between two nodes equals summary of weight of two clusters which is created by box-covering algorithm,and represents connecting strength of these two nodes.Renormalization and box-covering algorithm are repeated until there is only one node in networks,and the clustering process stops.The renormalizing progress creates a fractal tree,and community structure is uncovered by cutting the fractal tree.To enhance connection in the box,two-step box-covering algorithm is proposed.Secondly,A heuristic artificial bee colony algorithm which is named HABC(Heuristic Artificial Bee Colony)is proposed to uncover community.To address community problem,a heuristic function is applied into search progress of bee colony in HABC.The average agglomerate probability of two adjacent communities can be used as the heuristic function of searching processes.In searching process,a node is labeled with community ID of the neighbor community in which the value of heuristic function is most largest.A nectar source represents a solution of community structure.In initialization stage,complete sub-graphs are extracted from complex network,and nodes in same sub-graph is labeled with unique community ID.A nectar source is created with simply community structure which makes searching progress quickly.Experimental results demonstrate that HABC is both effective and efficient for discovering node communities.At last,a heuristic genetic algorithm with spectral analysis,HGASA,is proposed to uncover multi-scale community There are two stages in HGASA.In the first stage,multiple-scale property is uncovered by normalized Laplacian matrix.In the second stage,multi-scale property is associated with GA to uncover community structure.One-way incorporating crossing operation is proposed in HGASA.The community structure return new individual by one-way incorporating crossing operation.A heuristic function based network dynamics is applied in mutation operation,and the monotonic relationship between the heuristic function and the object function is proved.The study result of this thesis,especially of fractal cluster,heuristic optimization and multiple-scale community,are of both theoretical and practical benefit to further study on the complex networks.