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 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.
Documentation pointers :
- Graph Programming: an overview of the graph domain within Mathemtica.
- Older graph utilities package overview: the documentation of graph within Combinatorica.
- Graph layout: the documentation on graph layout.
- Older GraphPlot and graph drawing: contains some valuable but also somewhat outdated GraphPlot info.
- Graph operations and modifications: algebraic operations using graphs.
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.
The most basic way to create a graph is via the short form:
If you wish to see the labels you need to add the VertexLabels attribute:
This is a directed graph and you can turn it into an undirected by using the DirectedEdges attribute;
If you wish to extract the vertices out of this then you can use VertexList:
and similarly for the edges:
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:
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;
Next to this you can also assign a custom shape like so
The vertices of a graph can be an arbitrary object though it’s not always represented accordingly:
The same with the edges, they can be adorned with objects. Click on the red edge to see the stock chart:
and putting a label
or as a tooltip
To color certain edges you can use the highlighting facility:
You can associate with a graph various matrices which capture the structure of a graph. The adjacency matrix of the directed graph
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.
We’ll save the simple triangle graph as an example for later as TriangleGraph;
The undirected matrix is always symmetric;
An interesting way to represent this matrix is by plotting the matrix or array
which gives a more direct visualization of where the entries are and whether the matrix is symmetric. Alternatively, you can use the ArrayPlot;
The adjacency matrix is genuine representation in the sense that it’s also possible to draw a graph from a given adjacency matrix;
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;
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.
By convention, if the entries are non-negative the edges are undirected;
Let’s save the following definitions:
as well as the degree matrix which consists of the diagonal matrix with the degree of the vertices:
and if you take the difference between the degree matrix and the adjacency matrix you get the Laplacian matrix of the graph:
In Mathematica this is called the Kirchoff matrix and the equality to our definition is valid both for directed and undirected graphs;
In addition, if the graph is undirected then it’s also the related to the incidence matrix;
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;
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.
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;
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;
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;
while for higher degrees the EdgeCount distribution is uniform as is clear from how the random graph is constructed.
The Price graph distribution creates graphs which are almost trees:
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 , where 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:
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.
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.
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;
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.
The eigenvector centraility is defined by the eigenvectors of the adjacency matrix;
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.
The Katz centrality is related to paths connecting a graph rather than just the immediate neighborhood, thus extending the notion of degree centrality.
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.
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.
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;
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;
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 :
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.
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.
Finding the shortest path is really easy:
Underneath this is actually the assumption that all edges have weight one. If we change the weights this can be seen.
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
So, in general you can safely forget about the Method and just assume that Mathematica will access the correct algorithm.
The Property keyword can be applied wherever you’d use a vertrex or edge in the definitions:
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.
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.
A breadth-first scan results in
The following method will show the path of the traversal:
Of course, when applied to the k-ary trees it fills the tree but not so in other graphs;
What about disconnected graphs? Since the traversal starts at a certain vertex the traversal will not visit disconnected components.
You can however find a spanning forest by discovering the connected components:
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.
The complement of a graph is with respect to the complete graph.
The neighborhood of a vertex gives a new subgraph, with optionally the distance defining the radius of the neighborhood.
The disjoint graph union allows you to assemble multiple graphs.
The non-disjoint union will overlap the given graphs and merge the edges for the corresponding vertices:
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.
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.
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:
The object is actually a set of rules:
You can print the content of the object out as follows:
Using JSON you can easily assign a more complex object like so:
|Book: The Road to Reality|
|Knows: a whole lot|
Note that it’s important to specify the “JSON” type otherwise it will be imported as a string.