Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

When I specify that a graph should be realized using the "SpectralEmbedding" procedure, what paper / algorithm for spectral embedding is this based on? I was unable to find any documentation for this.

Also, are we guaranteed that the contours of a $N \times M$ rectangular lattice will be straight lines after this embedding procedure?

share|improve this question
3  
For this type of question I suggest you contact support directly. But when they reply, it'd be good if you could post the answer here for everyone's benefit. –  Szabolcs Feb 8 '13 at 17:55
    
@Szabolcs No response yet, but I'll post here what I learn. –  Roger Harris Feb 10 '13 at 13:21
add comment

1 Answer

up vote 7 down vote accepted

I e-mailed support at Wolfram Research and recieved the following response:

"Spectral graph drawing methods construct the layout using eigenvectors of certain matrices associated with the graph (Laplacian matrix). Reference: Hall, K.M. "An r-dimensional Quadratic Placement Algorithm.", Management Science 17, pp. 219-229 (1970)."


Here's a link to the journal article: http://mansci.journal.informs.org/content/17/3/219.short

Abstract: In this paper the solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form X′X = 1, for each of the r unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum or r positive semi-definite quadratic forms which, under the quadratic constraints, reduces to the problem of finding r eigenvectors of a special “disconnection” matrix. It is shown, by example, how this can serve as a basis for cluster identification.

From (Section 2.3) of Daniel A. Spielman lecture notes on applications of the Laplacian in spectral graph theory: http://www.cs.yale.edu/homes/spielman/561/lect02-12.pdf

"This approach to using eigenvectors to draw graphs was suggested by Hall [Hal70] in 1970. Hall first considered the problem of assigning a real number $x(u)$ to each vertex $u$ so that $(x(u)-x(v))^2$ is small for most edges (u; v). This led him to consider the problem of minimizing (2.1). So as to avoid the degenerate solutions in which every vertex is mapped to one value, he introduced the restriction that $x$ be orthogonal to $1$. As the utility of the embedding does not really depend upon its scale, he suggested the normalization $||x|| = 1$. As we saw last class, the solution to the resulting optimization problem is precisely an eigenvector of the second-smallest eigenvalue of the Laplacian."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.