Loading...
Please wait, while we are loading the content...
Similar Documents
Geographically organized small communities and the hardness of clustering social networks.
| Content Provider | CiteSeerX |
|---|---|
| Author | Kurucz, Miklós Benczúr, András A. |
| Abstract | Abstract Spectral clustering, while perhaps the most efficient heuristics for graph partitioning, has recently gathered bad reputation for failure over large-scale power law graphs. In this chapter we identify the abundance of small-size communities connected by long tentacles as the major obstacle for spectral clustering. These sub-graphs hide the higher level structure and result in a highly degenerate adjacency matrix with several hundreds of eigenvalues very close to 1. Our results on clus-tering social networks, telephone call graphs, and Web graphs are twofold. (1) We show that graphs generated by existing social network models are not as difficult to cluster as they are in the real world. For this end we give a new combined model that yields degenerate adjacency matrices and hard-to-partition graphs. (2) We give heuristics for spectral clustering for large-scale real-world social networks that han-dle tentacles and small dense communities. Our algorithm outperforms all previous methods for power law graph partitioning both in speed and in cluster quality. In a combination of heuristics for the contraction of tentacles as well as the removal of community cores that involve the recent SCAN (Structural Clustering Algorithm |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Clustering Social Network Small Community Degenerate Adjacency Matrix Spectral Clustering Community Core Bad Reputation Level Structure Structural Clustering Algorithm Social Network Model Small Dense Community Hard-to-partition Graph Clus-tering Social Network Large-scale Power Law Graph Efficient Heuristic Major Obstacle Small-size Community Power Law Graph Real World Graph Partitioning Han-dle Tentacle Large-scale Real-world Social Network Sub-graphs Hide Previous Method Recent Scan Telephone Call Graph Long Tentacle Web Graph Abstract Spectral Clustering Cluster Quality Several Hundred |
| Content Type | Text |
| Resource Type | Article |
