Local Community Detection Based On User’s Similarity

Community structure is one of the most important feature of complexnetworks. It represents the relationship between people in social networks,the websites link relationship in the Internet, the cooperation relationshipin citation networks and the food chain relationship in animal networks.All of these networks are representatives of complex networks. In recentyears, community structures detection get much more attention inacademic world. Traditional community detection algorithms focus on thecommunity structure of the entire network, which have high timecomplexity, and theses algorithms require information of the wholenetwork, which is too large and hard to know completely. With the size ofthe networks become larger and larger, traditional community structuredetection methods have hit the bottleneck because of the high timecomplexity. Besides, some networks such as the World Wide Web, arehuge and dynamic, which make the traditional community detectionmethods infeasible.For the above reasons, the research of the local community structuredetection is particularly important. The local community structuredetection method is proposed to detecting modules based on local structureinformation of networks and to overcome the limitations of global methods.For a given node, we detect the community to which the given nodebelongs using local community detection method. In the real world, wetend to detect some representative nodes’ community because the socialnetwork is too large to get the network’s entire information. Besides, undernormal circumstances, we are just concerned about the community ofsomeone which we are really interested in. For example, sometimes we only care about some famous websites’ local community structures in theWorld Wide Web.This paper proposes a local community detection algorithm, which isbased on user’s similarity and local center node. Through the complexityanalysis and experimental comparison, we make a conclusion that ouralgorithm can keep high accuracy with low time complexity. The mainresults and innovation points of this paper include the following aspects:First, we find local center nodes of the given node and start to detectthe local community from the local center nodes. Then we add nodes intocommunity based on user’s similarity. This method can reduce the timecomplexity. The time complexity is O (kd2).Second, the algorithm still keeps a high accuracy even though itreduces the time complexity.Thirdly, the algorithm is applied to the classical networks such askarate network, dolphin network, American football network, Americanpolitical books network and two computer generated networks which havethe characteristics of complex networks. Then we make a comparisonbetween our algorithm and the classic local community detectionalgorithm in these datasets. Our algorithm improve the precision and recallvalue. Experiment results indicate that, the algorithm reduces the timecomplexity and improves the accuracy.