Visualizations in Graph Theory 
and the Wolfram Language

Michael Sollami Ph.D.
Chief Scientist at Ditto Labs

Join the Conversation #WolframTechConf

Setup Code

$HistoryLength = 0;
ClearSystemCache[];

(*Configure Notebook for Editing*)
SetOptions[EvaluationNotebook[],{WindowElements->{"HorizontalScrollBar","MagnificationPopUp","VerticalScrollBar","MenuBar"},ShowCellBracket->True,ShowCellTags->True,ShowCellLabel->True,ShowGroupOpener->True}];

(*Configure Notebook for Presenting*)
SetOptions[EvaluationNotebook[],{WindowElements->{"VerticalScrollBar","MenuBar"},ShowCellBracket->False,ShowCellTags->False,ShowCellLabel->False,ShowGroupOpener->False}]

(*Load MaTeX*)
$texMag = 2;
SetDirectory["~/Research/wtc16/talk/packages/MaTeX-1.6.1/MaTeX"];
<<MaTeX`;
texStyle={(*FontFamily->"Latin Modern Roman",*)FontSize->26};
SetOptions[MaTeX,"Preamble"->{"\\usepackage{amsmath,amssymb}
\\usepackage[inline]{enumitem}","\\usepackage{color,txfonts}
\\DeclareUnicodeCharacter{F3D4}{\\dash}
\\DeclareRobustCommand\\dash{%
  \\unskip\\nobreak\\thinspace\\textemdash\\allowbreak\\thinspace\\ignorespaces}
"},LineSpacing->{0,14.4}];
MaTeX["\\color{red}\\sqrt{x}"]

(*Load Isomorphs*)
SetDirectory["~/Research/wtc16/talk/packages/Isomorphs"];
<<Isomorphs`

(*Load video*)
NotebookOpen@"/Users/mike/Research/wtc16/talk/packages/mma_video/mma_video.wl";
NotebookEvaluate@%;

Welcome to my talk

Cambridge based computer vision startup Ditto Labs

Giving out API Keys to developers!

DynamicGeoGraphics[{Polygon[(Entity["Cambridge", Entity["City",{"Cambridge","Massachusetts","UnitedStates"}], "Entity[\"City\", {\"Cambridge\", \"Massachusetts\", \"UnitedStates\"}]", "city"])],GeoMarker[Interpreter["StreetAddress"]["1 Broadway, Cambridge MA"],Import@"~/Research/wtc16/talk/images/ditto-logo1.png","Alignment"->Center,"Scale"->.006]}]

Q: What is the future of scientific communication?

A: Interactive Sequential Art

Import["~/Research/wtc16/talk/images/bret.png"]

Example #1: New York Times

Visualizing conversations in social media

play@"/Users/mike/Research/wtc16/talk/videos/cascade3.mp4"

Example #2: OpenDNS

Visualizing carding site activity

play@"/Users/mike/Research/wtc16/talk/videos/target_attack.mp4"

Example #3: Healthcare

Visualizing movement of patient metadata

play["/Users/mike/Research/wtc16/talk/videos/athena1.mp4"]

Example #4: Cosmic Web

Network Behind the Cosmic Web

play@"/Users/mike/Research/wtc16/talk/videos/cosmic3.mp4"

My Favorite Piece of MMA Code

Flyby by Vitaliy and me

gr=GraphData["Foster364A"];
gr3D=GraphPlot3D[AdjacencyMatrix[gr],Boxed->False,ViewAngle->.3,EdgeRenderingFunction->(Cylinder[#1,.02]&),VertexRenderingFunction->({ColorData["Atoms"][RandomInteger[{1,117}]],Sphere[#1,.05]}&),PlotStyle->Directive[Specularity[White,20]]];
ver=gr3D[[1,2,2]];
edg=EdgeList[gr=GraphData["Foster364A"]];
f[x_]:=Block[{$V},$V=RandomChoice[Select[edg,(#[[2]]==x[[2]]||#[[1]]==x[[2]])&]];
If[$V[[1]]==x[[2]],$V,Reverse[$V]]]
ran=ver[[#]]&/@NestList[f,1\[UndirectedEdge]4,1][[All,1]];
bsc=BSplineFunction[Flatten[Transpose[{ran,ran}],1]];
Manipulate[Show[gr3D,ViewAngle->Dynamic@va,ViewVector->Dynamic@{bsc[t]+.07,bsc[t+.01]+.03},ImageSize->800],{t,0,.99,Animator,AnimationRate->.12},{{va,1.2},.3,2,Slider},FrameMargins->0]

Problem motivation: László Babai and his algorithm

imgs=Import@*StringTemplate["~/Research/wtc16/talk/images/laszlo`1`.jpg"]/@Range[3];
imgs=Image[#,ImageSize->Full]&/@imgs;
SlideView[imgs,ImageSize->Full]

Graph Isomorphism

MaTeX["
\\begin{aligned}
&\\text{{\\bf Input description:} Two graphs, $G$ and $H$.}
\\end{aligned}", Magnification -> $texMag]

MaTeX["
\\begin{aligned}
&\\text{{\\bf Problem description:} Find a mapping $f$ from the vertices of $G$} \\\\
&\\text{to the vertices of $H$ such that $G$ and $H$ are identical;} \\\\
&\\text{i.e. $(x, y)$ is an edge of $G$ iff $(f(x),f(y))$ is an edge of $H$.}
\\end{aligned}
", Magnification -> $texMag]

GraphicsGrid[
 Partition[GraphData["PetersenGraph", "AllImages"], 4] /. 
  Gray -> Hue[0.6, 0.2, 0.8], ImageSize -> 700, Spacings ->-10]

Quasipolynomial Time

MaTeX["
\\begin{aligned}
&\\text{Functions like $n^{\\log n}$ that are superpolynomial but subexponential}\\\\
&\\text{are called {\\bf quasi-polynomial}.}
\\end{aligned}", Magnification -> $texMag]

Best Known Methods

Algorithms

MaTeX["
\\begin{aligned}
&\\text{{$\\diamond$} Trivial bound $O\\left(n!\\right)$ }\\\\ 
&\\text{{$\\diamond$}  Eugene Luks 1983 bound of $\\exp\\left(O\\left(\\sqrt{n \\log n}\\right)\\right)$}\\\\
&\\text{\\color{blue} $\\diamond$ $\\exp\\left((\\log n)^{O(1)}\\right)$ from Babai in 2015}
\\end{aligned}",Magnification->$texMag]

Implementations

MaTeX["
\\begin{aligned}
&\\text{$\\bullet$ Nauty (Brendan McKay)} \\\\
&\\text{$\\bullet$ VFLib graph-matching library} \\\\
&\\text{$\\bullet$ Valiente graph-matching library} \\\\
&\\text{$\\bullet$ Kreher and Stinson}
\\end{aligned}", Magnification -> $texMag]

Summary & Implications

• Babai’s proposed algorithm doesn’t bring graph isomorphism all the way into P, but it comes close.

Isomorphic Animations

Pappus Graph

p=GraphData["PappusGraph"];
vcs=GraphData["PappusGraph","AlternateVertexCoordinates"];
allGraphs=Graph[VertexList[p],EdgeList[p],VertexCoordinates->Thread[VertexList[p]->#]]&/@vcs;
Row@allGraphs

Generate frames

{frames,delays}=GraphSequence["PappusGraph",1.5,.5,"ImageSize"->{200,200},"Manip"->True];

GraphAnimate@@{frames,delays}

Export["~/Downloads/example.gif",frames,"Interlaced"->False,"DisplayDurations"->delays,"AnimationRepetitions"->∞]

Avoid ListAnimate

ListAnimate[frames,DisplayAllSteps->True]

ListAnimate[
 Import@"~/Downloads/example.gif"]

Export["~/Downloads/example.gif",frames,
"Interlaced"->False,
"DisplayDurations"->delays,
"AnimationRepetitions"->∞
]

Enhancing the Animations

p=GraphData["PetersenGraph"];
vcs=GraphData["PetersenGraph","AlternateVertexCoordinates"];
allGraphs=Graph[VertexList[p],EdgeList[p],VertexCoordinates->Thread[VertexList[p]->#]]&/@vcs;
Multicolumn[allGraphs,4]

iGraphAnimate["PetersenGraph",1,1,"Manip"->False,"ImageSize"->300]

Limitation 1: Many Graphs

fav={"TruncatedOctahedralGraph","LeviGraph","TesseractGraph","Balaban10Cage","DodecahedralGraph","HeawoodGraph","ChvatalGraph","Foster040A","DoyleGraph","IcosidodecahedralGraph","PetersenLineGraph","GraphCartesianProductOfK33AndK3"};

iGraphAnimate[#,1,1,"Manip"->False,"ImageSize"->200]&/@fav[[2;;3]]

iGraphAnimate[#,1,1,"Manip"->False,"ImageSize"->100]&/@fav

Limitation 2: Large Graphs

Great Rhombicosidodecahedral Graph

GraphData["GreatRhombicosidodecahedralGraph"]

iGraphAnimate["GreatRhombicosidodecahedralGraph",1,1,"Manip"->True,"ImageSize"->100]

Deployment options

Dynamics in the Wolfram Cloud  - Issues with stability and Frame-rates

imgs=Import@*StringTemplate["~/Research/wtc16/talk/images/bug`1`.png"]/@Range[4];
imgs=Image[#,ImageSize->Full]&/@imgs;
SlideView[imgs,ImageSize->Full]

How to deploy interactivity, really?

Javascript, HTML5, Electron, etc...

logos=Import/@{"/Users/mike/Research/wtc16/talk/images/sig.jpg","/Users/mike/Research/wtc16/talk/images/d3.jpg","/Users/mike/Research/wtc16/talk/images/three.png","/Users/mike/Research/wtc16/talk/images/react-native.png"};
Magnify[TextGrid[Transpose@Thread@{{"Graph[]","Graphics[]","Graphics3D[]" , "CloudDeploy[]"},logos}],1.4]

Demo #1: Sigma.js

->

Demo #2: D3

Demo #3: Javascript Limitations

Demo #4: Visualizing NetGraph

Summary

• Motivating examples of killer graph visuals

• Check out László Babai’s paper on the arxiv

• Real-world deployable presentations are hard!

• MMA needs javascript integration and/or enhanced exportability

• Feature request: Please make exporting code easy :)

Thanks for listening

Connect with me!

Magnify[TextGrid[{{"email", "michaelsollami@gmail.com"},
   {"www", "www.mikesollami.com"}, {"API Key:", "mike@dittolabs.io"},{"twitter","@DittoLabs"},{"demo","www.startditto.com"}}, 
  Frame -> All, FrameStyle -> LightGray, 
  BaseStyle -> {FontFamily -> "Apple Symbols"}], 2]

Ditto

• We do photo listening

• At twitter scale

• Studying social networks though computer vision