Community Detection Of Complex Networks Based On The Algebraic Connectivity Function

Community detection is an important issue in complex networks. How to findcommunities correctly has gained more and more attention. we pitched three differentmodels base on algebraic connectivity function of complex network.The first one is community detection of complex networks based on the spectrumoptimization algorithm. In this area, GN model made by Newman and Girvan attractswidespread attention. However the disadvantage of the GN model is high timecomplexity. We give a reasonable solution base on algebraic connectivity function. Anedge cutting model is proposed for selecting edges to be removed from candidates byminimizing algebraic connectivity function. In this model a greedy heuristic method isused to get the lower bound of optimal value, which makes it applicable to mid-sizednetworks.The second one is one of the fastest community detection of complex networkbased on the algebraic connectivity function. Following with the developing of socialnetwork on line, How to run on large-scale network attract more attention. Newmaninvented the concept of edge betweenness with random walking, shortest path andresistor. We give a novel edge betweenness base on algebraic connectivity functionwhich decreases the time complexity to linear. The advantage of the method is speedand higher degree of accuracy when runs on a low mixed community network thanthe other methods. As the mixed communities being higher and higher, the accuracyof result decreases quickly.The last one is automatic labeling community detection of social network base onalgebraic connectivity function. This model consists of divisive step and automaticlabeling step. In order to decreasing the mixed degree of network, the central nodeswere removed depend on the degree of node. Because of the large scale inner-nodes,the communities continue to stay close together. After the divisive step,unlabeled-nodes were labeled according to the label-value of adjacent nodes andfalse-labeled nodes were re-labeled again until every node was labeled correctly.The models are tested in LRF benchmark graphs and real graphs. The resultreflects that the spectrum optimization algorithm decreases the number of iterationscomparing with GN method, so the time complexity was declined effectively.Meanwhile, the model keeps the well result as same as GN algorithm. The fast community detection model gets perfect result in low mixed networks. Three differentmodels run in real graphs respectively and have a good performance.