Pretty much every domain covered by Mathematica is overwhelming and dense in many ways; heaps of functions, dozens of algorithms, thousands of parameters, endless ways to do things. The graph and networks package is no exception, it contains enough material to spend the rest of your life experimenting with it. This short introduction is a gentle overview and also contains a few things which are not so straightforward. Sometimes Mathematica (aka Wolfram Language knowadays) has its own obnoxious ways of doing things, often the amazing is simple and the simple requires a mind twist. An invaluable source of help and magic is the Mathematica StackExchange site which contains a universe of tricks and wizardry. This intro is a pragmatic approach and an concise invitation, there is plenty more to discover and to enjoy. Especially, the interactions within Mathematica between different types (social networks, sound, images, data…) and graphs give an amazing playground.

Spikey

Documentation pointers :

Note: if you read this document on the web you will not be able to exploit certain interactive elements contained in the exported Mathematica notebook.

Creating explicit graphs

The most basic way to create a graph is via the short form:

Networks_1.gif

Networks_2.gif

If you wish to see the labels you need to add the VertexLabels attribute:

Networks_3.gif

Networks_4.gif

This is a directed graph and you can turn it into an undirected by using the DirectedEdges attribute;

Networks_5.gif

Networks_6.gif

If you wish to extract the vertices out of this then you can use VertexList:

Networks_7.gif

Networks_8.gif

and similarly for the edges:

Networks_9.gif

Networks_10.gif

The fact that this list is with arrow indicates a directed graph. You can turn it back and forth with the DirectedGraph and UndirectedGraph directives:

Networks_11.gif

Networks_12.gif

The special undirected symbol  can be entered using “Esc ue Esc” while the symbol  can be entered using “Esc de Esc”.

To change the vertex shapes and size you can use the VertexShapeFunction and VertexSize;

Networks_13.gif

Networks_14.gif

Next to this you can also assign a custom shape like so

Networks_15.gif

Networks_16.gif

The vertices of a graph can be an arbitrary object though it’s not always represented accordingly:

Networks_17.gif

Networks_18.gif

Networks_19.gif

Networks_20.gif

The same with the edges, they can be adorned with objects. Click on the red edge to see the stock chart:

Networks_21.gif

Networks_22.gif

and putting a label

Networks_23.gif

Networks_24.gif

or as a tooltip

Networks_25.gif

Networks_26.gif

To color certain edges you can use the highlighting facility:

Networks_27.gif

Networks_28.gif

Matrices

You can associate with a graph various matrices which capture the structure of a graph. The adjacency matrix of the directed graph

Networks_29.gif

Networks_30.gif

Networks_31.gif

Networks_32.gif

represents how each of the nodes are connected. More precisely, all entries are zero unless entry ij corresponds to an edge between vertex i and vertex j.

Networks_33.gif

1 2 3
1 0 1 0
2 0 0 1
3 1 0 0

We’ll save the simple triangle graph as an example for later as TriangleGraph;

Networks_34.gif

The undirected matrix is always symmetric;

Networks_35.gif

Networks_36.gif

An interesting way to represent this matrix is by plotting the matrix or array

Networks_37.gif

Networks_38.gif

which gives a more direct visualization of where the entries are and whether the matrix is symmetric. Alternatively, you can use the ArrayPlot;

Networks_39.gif

Networks_40.gif

The adjacency matrix is genuine representation in the sense that it’s also possible to draw a graph from a given adjacency matrix;

Networks_41.gif

Networks_42.gif

Note that loops are created when you assign a weight to the diagonal elements.

An alternative way of representing a graph in a matrix is the incidence of edges and vertices;

Networks_43.gif

Networks_44.gif

The rows are indexed by the edges of the graph and the column by the vertices. The source of the edge gets a -1 and the target a +1 in the matrix. The representation is also faithful since you can get the graph back from the incidence matrix.

Networks_45.gif

Networks_46.gif

By convention, if the entries are non-negative the edges are undirected;

Networks_47.gif

Networks_48.gif

Let’s save the following definitions:

Networks_49.gif

as well as the degree matrix which consists of the diagonal matrix with the degree of the vertices:

Networks_50.gif

and if you take the difference between the degree matrix and the adjacency matrix you get the Laplacian matrix of the graph:

Networks_51.gif

For example;

Networks_52.gif

Networks_53.gif

In Mathematica this is called the Kirchoff matrix and the equality to our definition is valid both for directed and undirected graphs;

Networks_54.gif

In addition, if the graph is undirected then it’s also the related to the incidence matrix;

Networks_55.gif

Networks_56.gif

which is not true for the directed case. On the other hand, the formula for the Laplacian via the incidence matrix does have generalizations in higher dimensions which cannot be done via the formula we have given (using the degrees and the adjancency matrix). The incidence definition does not preserve the orientation of simplices. The way the Kirchoff matrix is defined by Mathematica does however preserve the orientation and is faithful since you can create a graph from a Kirchoff matrix;

Networks_57.gif

Networks_58.gif

Networks_59.gif

Networks_60.gif

Parametric graphs

Various types of well-known graphs can be created with their defining parameters. Below is an overview of these predefined graphs together with their adjacency plot.

Networks_61.gif

Networks_62.gif

Networks_63.gif

Networks_64.gif

Networks_65.gif

Networks_66.gif

Networks_67.gif

Networks_68.gif

Networks_69.gif

Networks_70.gif

Networks_71.gif

Networks_72.gif

Networks_73.gif

Networks_74.gif

Networks_75.gif

Networks_76.gif

Networks_77.gif

Networks_78.gif

Networks_79.gif

Networks_80.gif

Networks_81.gif

Networks_82.gif

Networks_83.gif

Networks_84.gif

Networks_85.gif

Networks_86.gif

Networks_87.gif

Networks_88.gif

Networks_89.gif

Networks_90.gif

Networks_91.gif

Networks_92.gif

Networks_93.gif

Networks_94.gif

Networks_95.gif

Networks_96.gif

Networks_97.gif

Networks_98.gif

Networks_99.gif

Random graphs

Random graphs are created by means of a distribution which tells whether a couple of vertices are connected or not.

The uniform distribution of n vertices and m edges samples uniformly over the space of simple graphs of n vertices and m edges;

Networks_100.gif

Networks_101.gif

which in fact corresponds to a uniform distribution in matrix space since it maps to a random matrix.

The Bernouilli distribution is based on a Bernoulli trial with probability p; two edges are connected based on a Bernoulli (coin tossing) probability p. If two vertices have equal probability to be connected or not then this would be;

Networks_102.gif

Networks_103.gif

A Barabasi-Albert graph distribution is constructed starting from triangle graph, and a vertex with k edges is added at each step. The k edges are attached to vertices at random, following a distribution proportional to the vertex degree. This means that if k=1 you end up with a random tree;

Networks_104.gif

Networks_105.gif

while for higher degrees the EdgeCount distribution is uniform as is clear from how the random graph is constructed.

Networks_106.gif

Networks_107.gif

Networks_108.gif

The Price graph distribution creates graphs which are almost trees:

Networks_109.gif

Networks_110.gif

It is constructed starting from a graph with a single vertex and at each step adding a vertex with k edges. The k edges are attached to vertices at random with weights Networks_111.gif, where Networks_112.gif is the in-degree of vertex i.

The degree distribution is simply a random graph with vertices having the degrees specified in the given list:

Networks_113.gif

Networks_114.gif

The Watts-Strograts graph is created by starting from a circular graph of n vertices and rewiring each edge with probability p. Each edge is rewired by changing one of the vertices, making sure that no loop or multiple edge is created.

Networks_115.gif

Networks_116.gif

Finally, the spatial distribution starts with vertices placed uniformly on a square of dimension one and connecting them if they are within the distance specified.

Networks_117.gif

Networks_118.gif

In addition to the previous random graph generated through a distribution you can define your own random graph. For example, through the generation of random adjacency matrices;

Networks_119.gif

Networks_120.gif

Centrality

Centrality is all about differentiating vertices on the basis of some criteria which define one vertex as more important than another one.
For example, the degree of a vertex could be an indication of the importance of the vertex. In a social network context this could mean that one person is highly connected. In the family graph below ‘Larry’ is the most important (influencial) person in the family considering his high degree in the graph.

Networks_121.gif

Networks_122.gif

Networks_123.gif

Networks_124.gif

The eigenvector centraility is defined by the eigenvectors of the adjacency matrix;

Networks_125.gif

Networks_126.gif

Networks_127.gif

The difference with degree centrality becomes more apparent in a k-ary (balanced) tree graph. The degree centrality is constant in this case but the eigenvector centrality does make a difference and emphasizes the children closer to the root as more important than the lower children.

Networks_128.gif

Networks_129.gif

Networks_130.gif

The Katz centrality is related to paths connecting a graph rather than just the immediate neighborhood, thus extending the notion of degree centrality.

Networks_131.gif

The best way to see the difference here is by looking at a grid graph. The degree centrality is in this case failry constant across the grid and the eigenvector centrality is cumulative on the inner vertices. The Katz centrality is however cumulative on the outer vertices, as can be seen below.

Networks_132.gif

Networks_133.gif

Networks_134.gif

Closeness centrality is in comparison to the other techniques useful when searching for centers which are strong starting points to reach all other vertices. While the eigenvector centrality will tell you what the most important vertices are, the closeness centrality will tell you which nodes a close to all the others. For this reason the closeness centrality is often used when dealing with urban design, virus spreading simulations and alike.

Networks_135.gif

Networks_136.gif

The betweenness centrality emphasizes vertices which sits in between other vertices. The best way to see this is by creating a graph which two wings;

Networks_137.gif

Networks_138.gif

Networks_139.gif

Graphics:Betweenness

Distance

The shortest path between two vertices defines the graph distance of these vertices. For a path graph this is obviously the same as the linear distance;

Networks_141.gif

Networks_142.gif

The vertex eccentricity is by definition the maximum length of a vertex to any other vertex. Coloring the graph on the basis of the distances results in a nice visualization :

Networks_143.gif

Networks_144.gif

The diameter of a graph is the maximum eccentricity of the vertices. In the case of a line graph this reduces to the standard distance while for a grid it’s the sum of the width and height.

Networks_145.gif

Networks_146.gif

The periphery of a graph are the outer vertices in the sense of maximum eccentricity. The center of a graph is the complementary notion; the set of vertices with minimum eccentricity.

Networks_147.gif

Graphics:Graph Periphery

Paths

Finding the shortest path is really easy:

Networks_149.gif

Networks_150.gif

Underneath this is actually the assumption that all edges have weight one. If we change the weights this  can be seen.

Networks_151.gif

Networks_152.gif

The underlying algorithm is chosen automatically in function of the edge weight. For positive weights only this is the Dijkstra algorithm, while the more general case is handled by Bellman-Ford. Trying to force Dijkstra for example will not give in an error but rather return an unexecuted result

Networks_153.gif

Networks_154.gif

Networks_155.gif

Networks_156.gif

So, in general you can safely forget about the Method and just assume that Mathematica will access the correct algorithm.

Properties

The Property keyword can be applied wherever you’d use a vertrex or edge in the definitions:

Networks_157.gif

Networks_158.gif

Alternatively, you can use the SetProperty to change an existing object. One important thing to remember is that this creates a new object and does not alter the object being modified.

Networks_159.gif

Networks_160.gif

Networks_161.gif

Scans (aka traversals)

The traversals are somewhat less accessible than the rest of the graph framework although there are plenty of ways to make use of it or to plug into it. Let’s take the simplest example, a tree graph and perform a depth-first traversal. We’ll print out the visited vertices.

Networks_162.gif

Networks_163.gif

Networks_164.gif

A breadth-first scan results in

Networks_165.gif

Networks_166.gif

Networks_167.gif

The following method will show the path of the traversal:

Networks_168.gif

Of course, when applied to the k-ary trees it fills the tree but not so in other graphs;

Networks_169.gif

Networks_170.gif

Networks_171.gif

Networks_172.gif

What about  disconnected graphs? Since the traversal starts at a certain vertex the traversal will not visit disconnected components.

Networks_173.gif

Networks_174.gif

You can however find a spanning forest by discovering the connected components:

Networks_175.gif

Networks_176.gif

Graphs from Graphs

There are some graph generating and modifying instructions.

A line graph is in a way the dual of a graph where edges are mapped to vertices and these vertices are connected if the original edges are adjacent.

Networks_177.gif

Networks_178.gif

The complement of a graph is with respect to the complete graph.

Networks_179.gif

Networks_180.gif

The neighborhood of a vertex gives a new subgraph, with optionally the distance defining the radius of the neighborhood.

Networks_181.gif

Networks_182.gif

Networks_183.gif

Networks_184.gif

The disjoint graph union allows you to assemble multiple graphs.

Networks_185.gif

Networks_186.gif

The non-disjoint union will overlap the given graphs and merge the edges for the corresponding vertices:

Networks_187.gif

Networks_188.gif

The graph intersection gives the overlapping edges in the union of the vertices. The edges are intersected but the vertices are joined! Due to the way that vertices are being numbered this can lead to unexpected results however. In the following example the intersection is visually a 2×2 graph but the result is not.

Networks_189.gif

Networks_190.gif

Boolean graphs are created by joining the vertices of graphs g1,g2 and applying a Boolean function f which creates an edge between vertices u and v if f[EdgeQ[g1,u-v], EdgeQ[g2,u-v]] is true.

Assigning objects

When using graphs it’s often useful to let the vertices carry a payload, i.e. some data bound to the node.
The easiest way to do this is by using either JSON or using the PropertyValue.

Using the PropertyValue you can assign an object as follows:

Networks_191.gif

Networks_192.gif

The object is actually a set of rules:

Networks_193.gif

Networks_194.gif

You can print the content of the object out as follows:

Networks_195.gif

FirstName: Isaac
LastName: Newton

Using JSON you can easily assign a more complex object like so:

Networks_196.gif

Book: The Road to Reality
FirstName: Roger
Knows: a whole lot
LastName: Penrose

Note that it’s important to specify the “JSON” type otherwise it will be imported as a string.