Research On Node Similarity Based Community Detection Algorithm

In recent years, the rising social networks application has gained rapiddevelopment, including online social networking websites like Facebook, Twitter,Renren and Weibo. And, the research on social networks attracts extensive attention ofresearchers in various academic fields worldwide. Community is a kind of hiddenpatterns in social networks, conforming to the characters of that nodes inside a samecommunity are densely connected while in different communities are sparselyconnected. Based on the similarities between the community nodes, the research oncommunity structure can give us the information about user communication patternand demand pattern. What’s more, it’s comparatively significant for understandingnetwork structure and making the most of network values. Detecting the communitiesis to detect potential patterns in networks with the known information of graphtopology, node attributes and linking relations.Most of the existing community detection algorithms are based on network graphtopology to calculate and classify. Such algorithm commonly has the problem of hightime complexity, low accuracy and comparatively simple clustering factor. To solvethe problems in the existing algorithms, the thesis proposed a community detectionalgorithm based on node similarities. The algorithm is put forward based on the studyof the related algorithms, comprehensively considering the graph topology and thenode attributes. Different from the thoughts of existing graph clustering algorithmswhich using graph topology only to dividing the graph, the algorithm proposed in thethesis firstly gets node similarities with the rules of practical significance whichequals to distance between nodes in data mining, and then clusters nodes withtraditional spatial point clustering algorithm. The algorithm firstly constructs attributeaugmented graph to combining the graph topology and node attributes, and thencalculates nodes similarities based on the thought of similar structure situation. In theattribute augmented model, the relationship between nodes with same attribute willconnect closer because of the addition of attribute node. At last, based on the nodessimilarity, it uses the improved algorithm of traditional k-means algorithm to clusterto get better community structure which can precisely describe the real relationship ofsocial network members.The structure of thesis organizing and planning is as follows. Firstly, the thesisintroduces the conception of social networks and network community, and furtherpresents the related research status at home and at aboard in this field. Secondly, it expounds the idea of several classic community detection algorithms, analyzes theirperformances and points out the existing limitations. Thirdly, as the core of the wholethesis, it proposes a community detection algorithm based on node similarities whichis called NSCDA, which is described in detail in the following text. At last, in order toverify the algorithm validity, several experiments on multiple datasets are carried outto analyze the performance of the algorithm. The experiment results show that thecommunity structure detected with the algorithm has high accuracy and linear timecomplexity, the testing on some datasets all present the effectiveness of the algorithm.