Table of Contents

This is a Jupyter Notebook that contains Julia code I will run in the first lecture of Spectral Graph Theory. I find experiments to be incredibly useful when working on spectral graph theory. They help me figure out what is true, and they help me find counterexamples to my conjectures.

If you want to try using this, you will need to install Jupyter (via Python), Julia and IJulia. You also need my package, called Laplacians.jl. It may be added in Julia via

Using Pkg
Pkg.add("Laplacians")
In [1]:
using Laplacians
using LinearAlgebra
using Statistics
using Plots
using SparseArrays
using FileIO
using JLD2
using Random

Path Graphs

In [22]:
L = lap(path_graph(10))
E = eigen(Matrix(L))
;
In [23]:
Plots.plot(E.vectors[:,2],label="v2",marker = 5)
Plots.plot!(E.vectors[:,3],label="v3",marker = 5)
Plots.plot!(E.vectors[:,4],label="v4",marker = 5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[23]:
2 4 6 8 10 -0.4 -0.2 0.0 0.2 0.4 Vertex Number Value in Eigenvector v2 v3 v4
In [24]:
Plots.plot(E.vectors[:,10],label="v10",marker=5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[24]:
2 4 6 8 10 -0.4 -0.2 0.0 0.2 0.4 Vertex Number Value in Eigenvector v10

A randomly weighted path

In [34]:
Random.seed!(2)
M = spdiagm(1=>rand(10))
Out[34]:
11×11 SparseMatrixCSC{Float64,Int64} with 10 stored entries:
  [1 ,  2]  =  0.366796
  [2 ,  3]  =  0.523879
  [3 ,  4]  =  0.210256
  [4 ,  5]  =  0.819338
  [5 ,  6]  =  0.501371
  [6 ,  7]  =  0.559355
  [7 ,  8]  =  0.523559
  [8 ,  9]  =  0.41587
  [9 , 10]  =  0.540152
  [10, 11]  =  0.689567
In [35]:
M = M + M'
L = lap(M)
;
In [36]:
E = eigen(Matrix(L))
println(E.values)

[1.00929e-17, 0.0371842, 0.129075, 0.342382, 0.534419, 0.755576, 1.16124, 1.42235, 1.72423, 1.97659, 2.21725]
In [37]:
Plots.plot(E.vectors[:,2],label="v2",marker = 5)
Plots.plot!(E.vectors[:,3],label="v3",marker = 5)
Plots.plot!(E.vectors[:,4],label="v4",marker = 5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[37]:
2 4 6 8 10 -0.4 -0.2 0.0 0.2 0.4 Vertex Number Value in Eigenvector v2 v3 v4
In [38]:
Plots.plot(E.vectors[:,11],label="v10",marker=5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[38]:
2 4 6 8 10 -0.50 -0.25 0.00 0.25 0.50 Vertex Number Value in Eigenvector v10
In [39]:
Random.seed!(1)
M = spdiagm(1=>rand(10))
M = M + M'
L = lap(M)
E = eigen(Matrix(L))
Plots.plot(E.vectors[:,2],label="v2",marker = 5)
Plots.plot!(E.vectors[:,3],label="v3",marker = 5)
Plots.plot!(E.vectors[:,4],label="v4",marker = 5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[39]:
2 4 6 8 10 -0.50 -0.25 0.00 0.25 0.50 Vertex Number Value in Eigenvector v2 v3 v4

Spectral Graph Drawing -- The Yale Logo

In [40]:
using PyPlot: pygui
pygui(false)
Out[40]:
false
In [41]:
@load "YALE.jld2"
Out[41]:
4-element Array{Symbol,1}:
 :a 
 :xy
 :v2
 :v3
In [42]:
plot_graph(a, v2,v3, dots=false)
Out[42]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x126738290>

The Dodecahedron

In [43]:
M = readIJV("dodec.txt")
;
In [44]:
spectral_drawing(M)
Out[44]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x126a2e310>