Reseacrh On Community Detection Algorithms Based On Local Information In Complex Networks

In recent years, in many research fields of complex networks, communitystructure detection has become one of the most concerning areas. Moreover, it isclosely related to the research of clustering and classification in data mining.Community structure detection focuses on discovering the relationship betweenelement and element to acquire the key contents we need from these information.With the development of network technology and graph theory research, a lot ofthings of different fields can be represented by complex networks. Abundant datainformation and the complex network structures have made people unable to getglobal data information. Therefore, using the local information of network to detectcommunities has important significance.Now many community detection algorithms need us to know the state of thewhole network, or calculate many times throughout the network. Unlikely, expandingcommunity just according to some local information of network not only can greatlysimplify the complexity, but also know about the importance of nodes and evolutionof network structure. Several kinds of algorithms focus on the local information areeither bad in starting node selection which is not suitable for mass data or is not stableor local extension metric is not good enough to get effective results.In order to solve the above problems, the paper summarizes some classiccommunity detection algorithms based on the research of representative literatures ofrecent years, and make optimization and improvement of some existing algorithms.The basic idea of detecting community from locality is to extend the community fromthe initial node set according to the local extension metric. The paper improves theMONC algorithm which is based on the exact resolution, mainly makes optimizationon the time complexity. The optimization algorithm is called hierarchical clusteringalgorithm based on key node set, in short, KHC algorithm. And the paper alsopresents an overlapping community algorithm based on accepted maximal cliques,according to LFK algorithm, in short, AMC algorithm. The starting node set of KHC algorithm consist of specified single node and themost closely connected key node with it. For the specified node, we define the keynodes of community which are those large degree nodes. And we also define the keynode of a node based on similarity. Then calculate the resolution value after addingeach neighbor, and then expand community according to relevant rule. The nodewhich gets the maximum resolution will be joined to the community. In accordancewith the law of diminishing resolution values obtain each level community, until allnodes are placed in one community. Unlike the MONC algorithm, the algorithmconsiders the importance of nodes in network when selecting the initial node sets,decrease the randomness in some extent. More importantly, this kind of initial nodesets reduces the complexity of the algorithm. In addition, the implementation ofMONC is optimized. Finally, the algorithm uses the classical community divisionmetric, module degree Q function to select the optimal division.The initial node sets of AMC algorithm are composed of accepted maximalcliques, as the center of communities. AMC adopts cliques abandon strategy whichreduces the complexity under the premise of not affecting the results. For theextension function, AMC algorithm combines the community structure definition andcommunity density, which make us know the density of the community and excludethe abnormal nodes that community may exist. At the same time, set a parameter toadjust the proportion of the density, which can reach to adjust the size of thecommunity.These two algorithms both are local community detection based on localinformation, which have advantage in large-scale networks. The paper experimentsthe two algorithms on artificial datasets and real world datasets, and the results provedthat the algorithms’effectiveness and certain superiority.