Graphs and Networks: Concepts and Applications

Charles Pooh
Wolfram Research
training@wolfram.com

A Brief History of Graphs & Networks

({{({{"1736", "Euler", "Bridges of Königsberg"}, {"1845", "Kirchhoff", "Circuit laws"}, {"1927", "Kermack, McKendrick", "First epidemic model"}, {"1960", "Baran", "Reliable communication"}, {"1960", "Erdos, Renyi", "Random graphs"}, {"1967", "Milgram", "Small-world experiment"}, {"1972", "Bollobas", "Complex graphs"}, {"1998", "Watts, Strogatz, al.", "Small-world network"}, {"1999", "Barabasi, Albert", "Scale-free network model"}, {"2001", "Yung", "Applications: SNA, business, ..."}, {"2005", "National Research Council", "Network science"}}), }})

Graph Modeling and Analysis

Graphs and Networks in Mathematica

Mathematica provides a modern extensible platform for graph and network modeling and analysis.

The only development platform fully integrating computation into complete workflows, moving you seamlessly from initial ideas all the way to deployed individual or enterprise solutions.

What Is a Graph?

In its simplest form, a graph is a collection of points joined together in pairs by lines.

The points are referred to as vertices and the lines are referred to as edges.

A graph with 10 vertices and 15 edges:

PetersenGraph[5,2,VertexSize-> 0.18,EdgeStyle-> Thick]

What is a Network?

A network is a graph that represents something real with a structure and a behavior.

Vertices are called nodes and the edges are called links.

Different nomenclature in each field:

({{"Computer sciences", "network as a system of nodes and links"}, {"Sociology", "network as social interactions or ties among actors"}, {"Physics", "network as model of phase transition, magnetism,…"}, {"Biology", "network as model of epidemics, metabolic systems within cells, …"}})

The World Wide Web (WWW) is a network of web pages linked via hyperlinks:

Show[Graph[webcrawler["http://www.wolfram.com",2],webstyle]]

Graphs in Mathematica

Graph[{(Subscript[e, 1]),(Subscript[e, 2]),…}] yields a graph with edges (Subscript[e, i]).

An edge between vertices u and v is denoted by u <-> v  (u EscueEsc v).

Build a graph from an edge list.

Graph[{1\[UndirectedEdge]3,1\[UndirectedEdge]4,1\[UndirectedEdge]5,2\[UndirectedEdge]3,2\[UndirectedEdge]4,2\[UndirectedEdge]5}]

Directed Graphs in Mathematica

Graph[{(Subscript[e, 1]),(Subscript[e, 2]),…}] yields a graph with edges (Subscript[e, i]).

A directed edge from vertex u to vertex v is denoted u -> v  (u EscdeEsc v).

A directed graph:

Graph[{1\[DirectedEdge]3,1\[DirectedEdge]4,1\[DirectedEdge]5,2\[DirectedEdge]3,2\[DirectedEdge]4,2\[DirectedEdge]5}]

The Internals of Mathematica

Efficient representations are used to store graphs. A graph object is treated as a raw object by functions like AtomQ and for purposes of pattern matching.

Use predicate function such as GraphQ, UndirectedGraphQ, and DirectedGraphQ for pattern matching:

myfunc[g_Graph]:=

myfunc[g_?GraphQ]:=

Use interface functions such as VertexList, EdgeList, Options to extract information:

# []& /@ {VertexList,EdgeList, Options}

Standard and Customizable Properties

Full support of standard properties (shape, labels, weights, style, ...) as well as customized user-defined properties.

Standard properties:

Graph[{1\[DirectedEdge]3,1\[DirectedEdge]4,1\[DirectedEdge]5,2\[DirectedEdge]3,2\[DirectedEdge]4,2\[DirectedEdge]5}, VertexStyle-> Red,VertexLabels->"Name",VertexLabelStyle-> Directive[Large,Gray],ImagePadding-> 30]

Custom properties:

Graph[{Property[1\[DirectedEdge]3,"strength"-> 10],1\[DirectedEdge]4,1\[DirectedEdge]5,2\[DirectedEdge]3,2\[DirectedEdge]4,2\[DirectedEdge]5}];

PropertyValue[{%,1\[DirectedEdge]3},"strength"]

Matrix Representations

An adjacency matrix ((Subscript[a, i,j])) can be used to represent a (undirected) simple graph.

(Subscript[a, i,j])=({{{, ({{1, if (Subscript[u, i]) is adjacent to (Subscript[u, j])}, {0, otherwise}})}})

Build a graph from an adjacency matrix.

AdjacencyGraph[(({{0, 1, 1, 1, 0}, {1, 0, 0, 0, 1}, {1, 0, 0, 0, 1}, {1, 0, 0, 0, 1}, {0, 1, 1, 1, 0}}))]

The adjacency matrix of a graph.

AdjacencyMatrix[] //MatrixForm

Network Models

({{"Computer sciences", "database design, data mining, web mining, …"}, {"Sociology", "social networks, …"}, {"Physics", "models of phase transition, magnetism, …"}, {"Ecology", "food webs, …"}, {"Economy", "models of markets, sponsored search markets, …"}, {"Business informatics", "organization diagrams, event driven process chains, …"}, {"Bioinformatics", "models of epidemics, metabolic networks, …"}})

Building Graphs and Networks from Data

File Formats: Graphlet · DOT · GraphML · GXL · DIMACS · LEDA · Pajek, …

Built-in Functions: AdjacencyGraph, IncidenceGraph, MorphologicalGraph, …

Transportation networks — a city block:

graph=MorphologicalGraph[Binarize[ColorNegate[image]],EdgeStyle->Gray];

Column[{image,HighlightGraph[graph,NeighborhoodGraph[graph,1800,10],ImageSize->{550,278},VertexSize->{1800->10}]}]

Theoretical and Empirical Graphs & Networks

Theoretical graphs — the Petersen graph:

GraphData["PetersenGraph"]

Empirical graphs and networks — a network of books about US politics:

ExampleData[{"NetworkGraph","BooksAboutUSPolitics"}]

Random Graphs

Random graphs following a variety of graph distributions allow one to build simulated internets or citation graphs.

UniformGraphDistribution · BernoulliGraphDistribution · BarabasiAlbertGraphDistribution · PriceGraphDistribution · WattsStrogatzGraphDistribution · DegreeGraphDistribution

Erdos-Renyi model:

RandomGraph[UniformGraphDistribution[10,20]]

Gilbert models:

RandomGraph[BernoulliGraphDistribution[10,0.4]]

Epidemiology studies of sexually transmitted diseases:

RandomGraph[DegreeGraphDistribution[{3,3,1,1,2,2,2,2,5,7,3,3}]]

Random Graphs

Random graphs following a variety of graph distributions allow one to build simulated internets or citation graphs.

UniformGraphDistribution . BernoulliGraphDistribution . BarabasiAlbertGraphDistribution . PriceGraphDistribution . WattsStrogatzGraphDistribution . DegreeGraphDistribution

The small-world model:

RandomGraph[WattsStrogatzGraphDistribution[10,0.096]]

Barabasi-Albert model:

RandomGraph[BarabasiAlbertGraphDistribution[10,3]]

Preferential attachment models:

RandomGraph[PriceGraphDistribution[10,3,1.5]]

Information Visualization

With Mathematica’s unique graphics and dynamic interface tools, interactive effects can be attached to vertices and edges. This provides information drill-down for greater information visualization.

UML state diagram:

umlFrame[name_]:=(Inset[Panel[Style[name,14]],#]&);
umlFrame[name_,do_]:=(Inset[Panel[Style[Column[{Style[name,Bold,14],do},Center],12]],#]&);
eLabel[label_,pos_]:=Placed[Style[label,13],pos];
verts={"start","sr","sp","lr","end"};
edges={"start"->"sr","sr"->"end","sr"->"sp","sp"->"sr","sp"->"lr","lr"->"sr","lr"->"end"};
vcoords={{0,7.5},{0,6},{0,4},{0,2},{0,.5}};
vshape={"start"->Graphics[{Red,Disk[]}], "end"->Graphics[{Red,Circle[],Point[{0,0}]}]};
vshapef={"sr"->umlFrame["Simulator running"],"sp"->umlFrame["Simulator paused", "do/wait"],
"lr"->umlFrame["Log retrivial","do/output log"]};
eshapef={"start"\[DirectedEdge]"sr"->(Arrow[{{0,7.4},{0,6.3}}]&),
"sr"\[DirectedEdge]"end"->(Arrow[{{1.1,6},{3.2,6},{3.2,0.5},{0.1,.5}}]&),
"lr"\[DirectedEdge]"sr"->(Arrow[{{-1,2},{-2.2,2},{-2.2,6},{-1.1,6}}]&),
"sr"\[DirectedEdge]"sp"->(Arrow[{{-.3,5.7},{-.3,4.4}}]&),
"sp"\[DirectedEdge]"sr"->(Arrow[{{.3,4.4},{.3,5.7}}]&),
"sp"\[DirectedEdge]"lr"->(Arrow[{{0,3.6},{0,2.4}}]&),
"lr"\[DirectedEdge]"end"->(Arrow[{{0,1.7},{0,.6}}]&)};
elabels={"start"\[DirectedEdge]"sr"->eLabel["[Start]",{.9,{-0.2,0}}],
"sr"\[DirectedEdge]"end"->eLabel["[Stop]",{1/6,{1,1.5}}],
"lr"\[DirectedEdge]"sr"->eLabel["[Continue]",{1/5.5,{0,2}}],
"sr"\[DirectedEdge]"sp"->eLabel["[Pause]",{1/2,{1.1,0}}],
"sp"\[DirectedEdge]"sr"->eLabel["[Unpause]",{1/2,{-0.1,0}}],
"sp"\[DirectedEdge]"lr"->eLabel["[Data requested]",{1/2,{-0.1,0}}]};
Graph[{"start","sr","sp","lr","end"},edges,
 VertexShapeFunction->vshapef,
VertexShape->vshape,
EdgeShapeFunction->eshapef,
VertexCoordinates->vcoords,
EdgeLabels->elabels,
EdgeStyle->Red,
ImageSize->450]

Information Visualization

With Mathematica’s unique graphics and dynamic interface tools, interactive effects can be attached to vertices and edges. This provides information drill-down for greater information visualization.

Interactive food webs:

web={"Aphid"\[DirectedEdge]"Ladybug","Caterpillar"\[DirectedEdge]"Beetle","Caterpillar"\[DirectedEdge]"Towhee","Grasshopper"\[DirectedEdge]"Towhee","Ladybug"\[DirectedEdge]"Towhee","Mosquito"\[DirectedEdge]"Dragonfly","Mosquito"\[DirectedEdge]"Towhee","Sunflower"\[DirectedEdge]"Aphid","Sunflower"\[DirectedEdge]"Caterpillar","Sunflower"\[DirectedEdge]"Grasshopper","Sunflower"\[DirectedEdge]"Louse","Towhee"\[DirectedEdge]"Owl"}; 
names = PopupWindow[#,Dynamic[WolframAlpha[#]],WindowSize-> Medium]& /@ Union[Sequence @@@ web];
shapes={"Sunflower"->,"Aphid"->,"Ladybug"->,"Towhee"->,"Owl"->,"Grasshopper"->,"Louse"->,"Caterpillar"->,"Beetle"->,"Mosquito"->,"Dragonfly"->};
action[name_-> img_]:=With[{i=ImageResize[img,65]},name-> Tooltip[Mouseover[i,ImagePad[i,5,Red]],name]];
shapes=action /@ shapes ;
Graph[names,web,VertexShape-> shapes,VertexSize-> 0.9,ImageSize-> 900]

Structural Properties

Many algorithms and procedures require graphs with certain properties.

Basic properties:

VertexCount, EdgeCount — the number of vertices and edges in a graph

VertexEdge, EdgeList — the number of vertices and edges in a graph

Local structural properties:

DirectedGraphQ, UndirectedGraphQ — test whether a graph is directed or undirected

SimpleGraphQ, LoopFreeGraphQ, …

Global structural properties:

IsomorphicGraphQ — test whether two graphs are isomorphic

AcyclicGraphQ, BipartiteGraphQ, ConnectedGraphQ, …

Paths and Cycles

FindShortestPath — find the shortest path from the source to a target

GraphDiameter, GraphCenter, …

FindEulerianCycle, FindHamiltonianCycle, …

Solving mazes:

maze = ;

FindShortestPath[maze,"in","out"]

highlightMazePath[maze,%]

Centrality Measures

ClosenessCentrality — closeness centrality for each vertex

BetweennessCentrality — betweenness centrality for each vertex

EigenvectorCentrality, PageRankCentrality, HITSCentrality, KatzCentrality …

The 10 most traversed stations — along the shortest paths — of the London Underground:

london=;

HighlightSubway[london,First/@SortBy[Thread[VertexList[london]->BetweennessCentrality[london]],Last][[-10;;]]]

Components and Connectivity

ConnectedComponents — give groups of vertices that are strongly connected

KCoreComponents — give groups of vertices that are connected to at least k others

ConnectedGraphQ, VertexComponent …

ENRON email communication network

data = Import["http://snap.stanford.edu/data/email-Enron.txt.gz",{"Text","Lines"}];

enron = Graph[DirectedEdge @@@StringSplit[Drop[data,1;;4],"\t"]];

DisplayCell@
DisplayTable[{
{Style["Dataset statistics",Bold],SpanFromLeft},
{"Number of actors",VertexCount[enron]},
{"Number of emails", EdgeCount[enron]},
{"Number of actors in largest connected components",Length[First[ConnectedComponents[enron]]]},
{"Number of emails in largest connected components",EdgeCount[Subgraph[enron,First[ConnectedComponents[enron]]]]}},
Spacings->{2,1},
Frame->True,FrameStyle->{Thin,GrayLevel[.65]},Dividers->{{True,True,True},All},Alignment->Left]

({{"Dataset statistics", }, {"Number of actors", 36692}, {"Number of emails", 367662}, {"Number of actors in largest connected components", 33696}, {"Number of emails in largest connected components", 361622}})

Graph Programming

BreadthFirstScan — scan a graph in a breadth-first order

DepthFirstScan — scan a graph in a depth-first order

Property, PropertyValue …

Depth-first scan tree:

graph=;

Reap[DepthFirstScan[graph,2,{"FrontierEdge"->Sow}]][[2,1]]

HighlightGraph[graph,%]

Conclusion

Mathematica provides state-of-the-art functionality for modeling, analyzing, and synthesizing graphs and networks.

Modern extensible platform for graph and network modeling and analysis.

Graphs in visual form can be used directly as input and included in programs.

Information visualization and automation of graph layout using algorithmic aesthetics methods.

Hundreds of built-in Mathematica functions and standard graph algorithms.

Support for directed, undirected, and weighted graphs.

Full integration of graphs and networks into Mathematica.

Initialization

Clear[m8red];
m8red[a_]:=RGBColor[0.811765,0.117647,0.145098,a];

DisplayCell[expr_]:=CellPrint[TextCell[expr,"DisplayFormula",ShowStringCharacters->False]]

DisplayTable[list_List,opts:OptionsPattern[Grid]]:=TraditionalForm@Grid[list,opts,Dividers->All,Spacings->{1,2},Alignment->{Center,Center},BaseStyle->{FontFamily->"Verdana"},Background->{None,{{Hue[.6,.15,.9],GrayLevel[.9]}}},FrameStyle->Directive[Thick,White]]

PicturePrint[expr_,opts:OptionsPattern[Cell]]:=CellPrint[TextCell[expr,"Picture",opts,ShowStringCharacters->False]]

OverviewMouseover[header_,subs_]:=CellPrint@Cell[BoxData[ToBoxes@Mouseover[Framed[Style[header,"OverviewSection"],FrameMargins->{{15,15},{5,5}},BoxFrame->2,FrameStyle->None,RoundingRadius->5],

Evaluate@If[subs=="",Framed[Style[header,"OverviewSection",White],FrameMargins->{{15,15},{5,5}},BoxFrame->2,FrameStyle->None,RoundingRadius->5,Background->m8red[1]],Row[{Framed[Style[header,"OverviewSection",White],FrameMargins->{{15,15},{5,5}},FrameStyle->None,RoundingRadius->5,Background->m8red[1]]," » ",Framed[Style[subs,"OverviewSection"],FrameMargins->{{15,15},{5,5}},FrameStyle->m8red[1],BoxFrame->2,RoundingRadius->5,Background->White]}]]]],"OverviewSection"]

(*MapThread[OverviewMouseover,Transpose[{{"Chapter One","Chapter One topics, …"},{"Chapter Two","Chapter Two topics, …"},{"Chapter Three","Chapter Three topics, …"},{"Chapter Four","Chapter Four topics, …"}}]]*)

LargeOverviewMouseover[header_,subs_]:=CellPrint@Cell[BoxData[ToBoxes@Mouseover[Framed[Style[header,"LargeOverviewSection"],FrameMargins->{{15,15},{5,5}},BoxFrame->2,FrameStyle->None,RoundingRadius->5],

Evaluate@If[subs=="",Framed[Style[header,"LargeOverviewSection",White],FrameMargins->{{15,15},{5,5}},BoxFrame->2,FrameStyle->None,RoundingRadius->5,Background->m8red[1]],Row[{Framed[Style[header,"LargeOverviewSection",White],FrameMargins->{{15,15},{5,5}},FrameStyle->None,RoundingRadius->5,Background->m8red[1]]," » ",Framed[Style[subs,"LargeOverviewSection"],FrameMargins->{{15,15},{5,5}},FrameStyle->m8red[1],BoxFrame->2,RoundingRadius->5,Background->White]}]]]],"LargeOverviewSection"]

webcrawler[rooturl_,depth_]:=Flatten[Rest[NestList[Union[Flatten[Thread[#->Import[#,"Hyperlinks"]]&/@Last/@#]]&,{""->rooturl},depth]]];

colors=RandomChoice[Flatten[{Table[White,{10}],ColorData[3,"ColorList"]}],20];

webstyle={VertexStyle->Dynamic[Refresh[colors[[RandomInteger[{1,10}]]],UpdateInterval-> 0.5]],VertexShapeFunction->"Point",EdgeStyle->Directive[Opacity[.5],Hue[.15,.5,.8]],Background->Black,EdgeShapeFunction->(Line[#1]&),ImageSize->500};

image =;
(*WolframAlpha["Champaign IL",{{"Map:CityData",1},"Image"}];*)

highlightMazePath[maze_,path_]:=Show[{Graphics[{GrayLevel[0.2],Rectangle[{-1.,-1.},{30.,20.}]}],maze,Graph[path,EdgeList[PathGraph[path]],VertexCoordinates->AbsoluteOptions[maze,VertexCoordinates][[2,VertexIndex[maze,#]&/@path]],VertexSize->0,EdgeStyle->Directive[Thickness[0.01],Red,Opacity[1],CapForm["Round"]]]},ImageSize->500]

london = ;

highlightedStation[vsf_][coords_,v_,whDummy_]:=With[{orig=vsf[coords,v,whDummy],δ=2 π/10},With[{r=3.5 First@Cases[orig,Style[Disk[_,r_],_]:>r]},Join[orig,{AbsoluteThickness[3],Red,CapForm["Butt"],Circle[coords,0.75 r]},Table[Circle[coords,r,{ϕ δ,(ϕ+1) δ}],{ϕ,0,Round[2 π/δ]-1,2}]]]]

HighlightSubway[g0_,vertices_List]:=Module[{g=g0},Do[PropertyValue[{g,v},VertexShapeFunction]=highlightedStation[PropertyValue[{g,v},VertexShapeFunction]],{v,vertices}];
g]

$Line=0;