Algorithms For Social Networks’ Partition

In recent years, social networks, such as Renren and SinaWeibo athome, as well as Facebook and Twitter abroad, have played a more andmore important role in people’s life. With the fast development of socialnetworks, various researches on the social network have been carried on.This paper will focus on the detection of community structure of thesocial network， which can help social network users to locate theirfriend circle, so that they can keep contact with old friends, as well astake advantage of the social network platform to make new friends.Moreover, the detection of the community structure of social network canbring endless business opportunities. For example, the media can savemuch effort to discover their potential target. In a word, the communitystructure detection of social networks can offer us much convenience inlife and in work. It’s worth all the hard work on it.The detection of community structure can be divided into two classesaccording to the function. One is for detecting disjoint communities, andanother is for the overlap community structure detection. This paperproposes three algorithms in total, two improved algorithm for disjointcommunity structure detection, and one brand new algorithm for overlapcommunity structure detection. The first algorithm is an improved NJWalgorithm based on prior knowledge. It belongs to graph-partitioningalgorithms. The efficiency is raised by dimension reduction, and itintroduces an isolating index in order to improve the NJW algorithm forits failure to discover isolated communities. The second algorithm is thethree-phase hierarchical algorithm. It keeps the agglomeration phase offast GN algorithm, and additionally increase two other phase, namelydivision phase and adjustment phase, aiming to upgrade the efficiency byan initial partition and improve the quality by trivial vertex moving. Thethird algorithm makes use of the modularity, used in hierarchicalalgorithm for disjoint community structure detection. And further expand the meaning modularity so as to be adopted in the overlap communitystructure detection.In the experiment part, the paper compares the newly-put-forwardalgorithms with the existing algorithms in view of the modularity and theNMI, which shows a satisfied result. As for overlap community detection,the high value of index NMI shows the feasibility to transplantmodularity notation to the detection of overlap community structure...