Loading...
Please wait, while we are loading the content...
Similar Documents
A spectral clustering approach to finding communities in graphs.
| Content Provider | CiteSeerX |
|---|---|
| Author | White, Scott Smyth, Padhraic |
| Abstract | Clustering nodes in a graph is a useful general technique in data mining of large network data sets. In this context, Newman and Girvan [9] recently proposed an objective function for graph clustering called the Q function which allows automatic selection of the number of clusters. Empirically, higher values of the Q function have been shown to correlate well with good graph clusterings. In this paper we show how optimizing the Q function can be reformulated as a spectral relaxation problem and propose two new spectral clustering algorithms that seek to maximize Q. Experimental results indicate that the new algorithms are e#cient and effective at finding both good clusterings and the appropriate number of clusters across a variety of real-world graph data sets. In addition, the spectral algorithms are much faster for large sparse graphs, scaling roughly linearly with the number of nodes n in the graph, compared to O(n²) for previous clustering algorithms using the Q function. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Finding Community Spectral Clustering Approach Useful General Technique New Spectral Clustering Algorithm Large Sparse Graph Appropriate Number Spectral Relaxation Problem Automatic Selection Good Clustering Good Graph Clustering New Algorithm Experimental Result Spectral Algorithm Data Mining Real-world Graph Data Set Objective Function Graph Clustering Large Network Data Set |
| Content Type | Text |
| Resource Type | Article |
