A spectral method to separate disconnected and nearly-disconnected web graph components

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.

REFERENCES

• 1: B. Awerbuch , Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Transactions on Computers, v.36 n.10, p.1258-1263, Oct. 1987 [doi>10.1109/TC.1987.1676869]
• 2: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 3: N. Biggs. Algebraic Graph Theory. Cambridge Univ. Press, 1974.
• 4: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 5: S. Chakrabarti, B. E. Dom, and J. M. Kleinberg. Mining the link structure of the world wide web. Feb 1999.
• 6: C.-K. Cheng and Y.A. Wei. An inlproved two-way partitioning algorithm with stable performance. IEEE. Trans. on Computed Aided Desgin , 10:1502-1511, 1991.
• 7: F.R.K. Chung. Spectral Graph Theory. Amer. Math. Society., 1997.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: C. Ding, X. He, H. Zha, M. Gu, and H. Simon. Spectral min-max cut for graph partitioning and data clustering. Lawrence Berkeley Nat'l Lab Tech report 47848, May 2001.
• 10: W.E. Donath and A. J. Hoffman. Lower bounds for partitioning of graphs. IBM J. Res. Develop., 17:420-425, 1973.
• 11: M. Fiedler. Algebraic connectivity of graphs. Czech. Math. l., 23:298-305, 1973.
• 12: M. Fiedler. A property of eigenvectors of non-negative symmetric matrices and its application to graph theory. Czech. Math. J., 25:619-633, 1975.
• 13: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 14: Hillel Gazit, An optimal randomized parallel algorithm for finding connected components in a graph, SIAM Journal on Computing, v.20 n.6, p.1046-1067, Dec. 1991 [doi>10.1137/0220066]
• 15: John Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.16-25, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181021]
• 16: L. Hagen and A.B. Kalmg. New spectral methods for ratio cut partitioning and clustering. IEEE. Trans. on Computed Aided Desgin, 11:1074-1085, 1992.
• 17: X. He, H. Zha, C. Ding, and H.D. Simon. Web document clustering using hyperlink structures. Tech Report CSE-01-O06, April 2001.
• 18: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 19: R. R. Larson. Bibliometrics of the world wide web: an exploratory analysis of the intellectual structures of cyberspace. Proc. S1GIR'96, 1996.
• 20: Yanhong Li, Toward a Qualitative Search Engine, IEEE Internet Computing, v.2 n.4, p.24-29, July 1998 [doi>10.1109/4236.707687]
• 21: J. Mathews and R.L. Walker. Mathematical Methods of Physics. Addison-Wesley, 1971.
• 22: L. Page. Pagerank: bring order to the web. Stanford Digital Library working paper 199%0072, 1997.
• 23: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 24: Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
• 25: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 26: L.I. Schiff. Quantum Mechanics, 3rd ed. McGraw-Hill, 1968.
• 27: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 28: Y. Shiloach and U. Vishkin. An o(log n) parallel connectivity algorithm. J. Algorithm, pages 57-67, 1982.
• 29: R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Computing., J:146-160, 1972.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Performance, Theory