Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, first on the disconnected subgraph case, and second on the effects of adding edges sparsely connecting different subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(‖E ‖ + ‖V‖log(‖V‖)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
Description
A spectral method to separate disconnected and nearly-disconnected web graph components
%0 Conference Paper
%1 Ding01graphComponents
%A Ding, Chris H. Q.
%A He, Xiaofeng
%A Zha, Hongyuan
%B KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining
%C New York, NY, USA
%D 2001
%I ACM
%K 01 Ding clustering graph toread
%P 275--280
%R http://doi.acm.org/10.1145/502512.502551
%T A spectral method to separate disconnected and nearly-disconnected web graph components
%U http://portal.acm.org/citation.cfm?id=502551&dl=GUIDE&coll=GUIDE&CFID=64167610&CFTOKEN=59359426
%X Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, first on the disconnected subgraph case, and second on the effects of adding edges sparsely connecting different subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(‖E ‖ + ‖V‖log(‖V‖)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
%@ 1-58113-391-X
@inproceedings{Ding01graphComponents,
abstract = {Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, first on the disconnected subgraph case, and second on the effects of adding edges sparsely connecting different subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(‖E ‖ + ‖V‖log(‖V‖)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.},
added-at = {2008-11-12T21:04:56.000+0100},
address = {New York, NY, USA},
author = {Ding, Chris H. Q. and He, Xiaofeng and Zha, Hongyuan},
biburl = {https://www.bibsonomy.org/bibtex/2b518b37e1b3c9a246c5f7bffe86840e3/lee_peck},
booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining},
description = {A spectral method to separate disconnected and nearly-disconnected web graph components},
doi = {http://doi.acm.org/10.1145/502512.502551},
interhash = {78af28f1d92760ad6fee9f0f3033db8b},
intrahash = {b518b37e1b3c9a246c5f7bffe86840e3},
isbn = {1-58113-391-X},
keywords = {01 Ding clustering graph toread},
location = {San Francisco, California},
pages = {275--280},
publisher = {ACM},
timestamp = {2009-02-02T16:44:45.000+0100},
title = {A spectral method to separate disconnected and nearly-disconnected web graph components},
url = {http://portal.acm.org/citation.cfm?id=502551&dl=GUIDE&coll=GUIDE&CFID=64167610&CFTOKEN=59359426},
year = 2001
}