most recent 30 from http://mathoverflow.net 2013-05-22T04:48:01Z http://mathoverflow.net/feeds/user/19684 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120522/how-to-identify-bridge-nodes-between-nearly-connected-graph-components-in-partiti Vass 2013-02-01T14:15:58Z 2013-02-01T20:13:51Z

<p>I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. I have clustered them so that they form a band matrix. </p> <p>What ways exist to identity these nodes linking groups? These nodes that act as bridges between these nearly connected components.</p> <p>It appears that each method I have seen has some element of it being a heuristic in some way.</p>

http://mathoverflow.net/questions/120336/can-the-first-non-zero-eigenvalue-of-a-laplacian-matrix-with-more-than-1-zero-val Vass 2013-01-30T16:36:49Z 2013-02-01T07:19:40Z

<p>I have a graph with multiple connected components, and its adjacency matrix. I form the <code>Laplacian matrix</code> (<a href="http://en.wikipedia.org/wiki/Laplacian_matrix" rel="nofollow">wiki Laplacian matrix</a>), and from the 1K nodes there around 100 eigenvalues of value zero. (I use <code>eig</code> in <code>matlab</code> and the first 5 have negative values which I assume is a problem with the accuracy of matlab). I take that there are 100 connected components in the graph. </p> <p>If only the first eigenvalue was 0, I would take the eigenvector corresponding to the second smallest eigenvalue (<code>Fiedler vector</code>) to sort the adjacency matrix into a band matrix. This is done by finding the indexes to sort the Fiedler vector and use that to sort the adjacency matrix. Can this be done accordingly using the first non-zero eigenvalue's vector?</p> <p>Can I perform clustering with these eigenvectors in the same way as I would with <code>PCA</code> (principal component analysis).</p>

http://mathoverflow.net/questions/120336/can-the-first-non-zero-eigenvalue-of-a-laplacian-matrix-with-more-than-1-zero-val/120344#120344 Vass 2013-01-31T09:29:14Z 2013-01-31T09:29:14Z

@xawlaxaw , do you think that I could add small random padding values to the zeros in the adjacency matrix to force the <code>Fiedler</code> vector's eigenvalue to be non-zero?