Dual Hierarchical Clustering Algorithm Through Three-degree Information

Community structure is one of the most fundamental and important topological properties of complex network. Detecting communities may expose relationships among the nodes. However, there are some limitations in current community detection algorithms. On the one hand, definitions of distance between pairwise nodes only make use of only one-degree information. In this case, some more important information is ignored in sparse networks. So we decide to apply the three-degree information in our algorithm in order to better define the similarity between pairwise nodes. On the other hand, most algorithms are disturbed by noise nodes in networks which may lead to the phenomenon that two communities are classified into a single larger community. To solve these two problems, we consider hierarchical structure within communities and propose a new algorithm based on three degree information..This paper is divided into three parts. The first part is about the background of community detection algorithms and some brief introductions of common clustering algorithms. The second part mainly targets at the proposition of the new algorithm which contains three tasks. First, is to make improvements on the traditional hierarchical clustering algorithm mainly from two aspects:distance between pairwise nodes and preprocessing of networks. Second, we introduce two testing models in details:the stochastic?"block model and the LFR benchmark. Third, is to test the accuracy and effectiveness of the new algorithm in our synthetic networks through comparison among algorithms. In addition, we receive further application and validation in two real networks. The third part is about the conclusions and some further expectation.