A new clustering method and its application in social networks

In a graph theory model, clustering is the process of division of vertices into groups, with a higher density of edges within groups than between them. In this paper, we introduce a new clustering method for detecting such groups and use it to analyse some classic social networks. The new method has two distinguished features: non-binary hierarchical tree and the feature of overlapping clustering. A non-binary hierarchical tree is much smaller than the binary-trees constructed by most traditional methods and, therefore, it clearly highlights meaningful clusters which significantly reduces further manual efforts for cluster selections. The present method is tested by several bench mark data sets for which the community structure was known beforehand and the results indicate that it is a sensitive and accurate method for extracting community structure from social networks.

► We introduce a new clustering method for detecting community structures. ► Individuals and their relationships are denoted by weighted graphs. ► The graph density we defined gives a better quantity depict of whole correlation among individuals in a community. ► This new method has two important features: much smaller hierarchical trees that clearly highlight meaningful clusters and overlapping clusters. ► This new method is sensitive and accurate for extracting community structure in social networks.