A new blockmodeling based hierarchical clustering algorithm for web social networks

摘要

Cluster analysis for web social networks becomes an important and challenging problem because of the rapid development of the Internet community like YouTube, Facebook and TravelBlog. To accurately partition web social networks, we propose a hierarchical clustering algorithm called HCUBE based on blockmodeling which is particularly suitable for clustering networks with complex link relations. HCUBE uses structural equivalence to compute the similarity among web pages and reduces a large and incoherent network into a set of smaller comprehensible subnetworks. HCUBE is actually a bottom-up agglomerative hierarchical clustering algorithm which uses the inter-connectivity and the closeness of clusters to group structurally equivalent pages in an effective fashion. In addition, we address the preliminaries of the proposed blockmodeling and the theoretical foundations of HCUBE clustering algorithm. In order to improve the efficiency of HCUBE, we optimize it by reducing its time complexity from O(| V|~2) to O(|V|~2/p), where p is a constant representing the number of initial partitions. Finally, we conduct experiments on real data and the results show that HCUBE is effective at partitioning web social networks compared to the Chameleon and k-means algorithms.