An Algorithm for Identifying Useful Structure in Graphs Clustering
Dongming Chen, Xiaowei Xu · International Workshop on Education Technology and Computer Science · 2010
A new clustering method for graphs which is based on Breadth-First-Search is proposed. The clusters are of various structures such as cliques, stars, including hubs and outliers. Hubs and Outliers should be marked because they play very different roles in the network. Traditional algorithms may detect some useful structures, but they tend to fail to find hubs and outliers. We propose a clustering algorithm to solve the problem. Both synthetic networks and real datasets experiments demonstrate that apart from finding hubs and outliers, the algorithm also outperforms other algorithms in speed with a running time O(n) on a network with n nodes and m links, which is much faster than the fastest modularity-based algorithm O(mdlogn) (where d is the depth of the dendrogram describing the hierarchical cluster structure).
Cited by 2 works. doi:10.1109/etcs.2010.222
Authors
References
- Collective dynamics of ‘small-world’ networks
- Normalized cuts and image segmentation
- A density-based algorithm for discovering clusters in large spatial Databases with Noise
- Community structure in social and biological networks
- On power-law relationships of the Internet topology
- Finding and evaluating community structure in networks
- On power-law relationships of the Internet topology
- On random graphs. I.
- Finding community structure in very large networks
- An Information Flow Model for Conflict and Fission in Small Groups