How to find connected components of a random graph?

What is the relation between edge weights of a graph and eigenvector of laplacian of that graph?

• I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from ( http://:http://www.cs.yale.edu/homes/spielman/561/2009/lect02-09.pdf ) says that : Let [math]G = (V, E, w)[/math] be a weighted connected graph, and let [math]L_G[/math] be its Laplacian matrix. Let [math] 0= \lambda_1 \leq \lambda_2 \leq .... \leq \lambda_n [/math] be the eigenvalues of [math]L_G[/math] and let [math]v_1, . . . ,v_n[/math] be the corresponding eigenvectors. For any [math]k\ge 2[/math], let [math]W_k = {i \in V : v_k(i) \ge 0}[/math]. Then, the graph induced by G on [math]W_k[/math] has at most k − 1 connected components. This question might sound very stupid. But, I was wondering if there is any extensions on this, or other theorems, which in particular shows the relationship between the edge weights ([math]L_G[i,j][/math]) and values of eigenvectors.

• Answer:

  What are 'values' of eigenvectors? That's really a vague entity to define, as eigenvectors are not unique for a particular graph. Now, if you are talking about the eigenvectors of a laplacian in general, then here are a few pointers that could help understand what they are: 1. An eigenvector in general represents a natural mode a system can take. In this case, the system is a graph. And eigenvectors represent these modes. 2. With that said, if you are familiar with traditional signal processing, the eigenvectors kind of represent the 'frequency' present in a particular weighted graph. They form the x axis if you plot a frequency spectrum. 3. The eigenvalues in turn, represent the 'amounts' of these eigenvectors present in a given graph signal. They form the y axis of the frequency spectrum. This is drawn mainly from a dsp perspective, that being my major. But if you are familiar with those concepts, I hope it helped answer the question a little.