Effective clustering of dense and concentrated online communities

Most clustering algorithms tend to separate large scale online communities into several meaningful subcommunities by extracting cut points and cut edges. However, these algorithms are not effective on dense and concentrated graphs which do not have any meaningful cut points. Common problems with the previous algorithms are as follows. First, the size of the first cluster is too large as it may contain many incompatible users. Second, the quality and the purity of the clusters are very low. Third, only the dominant first cluster is found to be meaningful. To address these problems, we first propose a graph transformation to separate large scale online communities into two different types of meaningful subgraphs. The first subgraph is the intimacy graph and the second is the reputation graph. Then, we present the effective algorithms for discovering good sub-communities and for excluding incompatible users in these subgraphs. The experimental results show that our algorithms allow for extracting more suitable and meaningful sub-communities than the previous work in dense online networks.