Spectral Graph Layout Method - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : DrawGraph Details : GraphTheory/Layouts/Spectral

Spectral Graph Layout Method

Options

 • largest=truefalse
 By default, the spectral method uses the eigenvectors corresponding to the smallest eigenvalues.  If this option is true then the eigenvectors corresponding to the largest eigenvalues are used.
 • logdegree=truefalse
 If this option is true then instead of using the Laplacian of the graph, a modified version of the Laplacian is used with the log of the degree of each vertex on the diagonal instead of the degree. This can help prevent clustering near the origin in graphs with a lot of variation in the degrees of vertices.
 • normalized=truefalse
 By default the normalized form of the LaplacianMatrix is used when logdegree=false and the unnormalized form otherwise. This option can force use of the other form.

Description

 • The spectral layout method is so named because it uses the eigenvectors of the normalized LaplacianMatrix of the Graph to choose the positions of the points.
 • For a given graph, this layout is unique, unless the LaplacianMatrix has a smallest (or largest if largest=true) eigenvalue of multiplicity greater than one. In that case, the eigenvector basis of the associated eigenspace may differ between sessions, leading to very different graph layouts. This is uncommon for random graphs, but extremely common for highly structured graphs.
 • This layout method works in two and three dimensions.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $G≔\mathrm{Graph}\left(\mathrm{undirected},\left\{\left\{1,2\right\},\left\{1,4\right\},\left\{2,3\right\},\left\{3,4\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 4 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G,\mathrm{layout}=\mathrm{spectral}\right)$
 > $\mathrm{DrawGraph}\left(G,\mathrm{layout}=\mathrm{spectral},\mathrm{layoutoptions}=\left[\mathrm{largest}=\mathrm{true}\right]\right)$
 > $\mathrm{DrawGraph}\left(G,\mathrm{layout}=\mathrm{spectral},\mathrm{layoutoptions}=\left[\mathrm{largest}=\mathrm{true},\mathrm{normalized}=\mathrm{false}\right]\right)$
 > $H≔\mathrm{HypercubeGraph}\left(3\right)$
 ${H}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 8 vertices and 12 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(H,\mathrm{layout}=\mathrm{spectral},\mathrm{dimension}=3\right)$
 > $K≔\mathrm{RandomGraph}\left(50,125\right)$
 ${K}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 50 vertices and 125 edge\left(s\right)}}$ (3)
 > $\mathrm{DrawGraph}\left(K,\mathrm{layout}=\mathrm{spectral},\mathrm{dimension}=3,\mathrm{layoutoptions}=\left[\mathrm{logdegree}=\mathrm{true}\right]\right)$