0b3ckfb6d74ao IGraph/M

the igraph interface for Mathematica
0.3.116 (March 30, 2020)

This notebook can be opened using the command IGDocumentation[] or through the Documentation Centre. It cannot be saved, so feel free to edit and evaluate input cells, and experiment!

The documentation is currently incomplete. Contributions are very welcome!

Introduction

IGraph/M provides a Mathematica interface to the popular igraph network analysis package, as well as many other functions for working with graphs in Mathematica. The purpose of IGraph/M is not to replace Mathematica’s built-in graph theory functionality, but to complement it. Thus the IGraph/M interface is designed to interoperate seamlessly with built-in functions and datatypes, while also being familiar to users of other igraph interfaces (R, Python or C).

The full igraph functionality is not yet exposed. Priority is given to functionality that is not currently built into Mathematica. While many of the functions that IGraph/M provides overlap with built-in ones, like IGBetweenness and BetweeneessCentrality, there are usually some relevant differences. For example, IGBetweenness uses edge weights, while the built-in function BetweennessCentrality does not.

Basic usage

The package can be loaded using

Needs["IGraphM`"]

03r8h0gpf8w9v

The list of included functions can be queried with the command below. Notice that their names always have the IG prefix. Click on the name of a function to see its usage message.

?IGraphM`*

154d5m7xuztcr

Or just type a question mark followed by the symbol’s name:

?IGVersion

0vrrj8llllefq

IGVersion[]
"IGraph/M 0.3.116 (March 30, 2020)
igraph 0.9.0-pre+4b6e4215 (Mar 30 2020)
Mac OS X x86 (64-bit)"

IGraph/M functions work directly with Mathematica’s built-in Graph datatype. No new special graph datatype is introduced.

Let’s take a look at a few examples. Let us first generate a graph using the built-in functions of Mathematica.

SeedRandom[42];
g = RandomGraph[BarabasiAlbertGraphDistribution[100, 2]]

1ehv9vlcgrdei

We can compute the betweenness centrality of each vertex either using IGraph/M, …

IGBetweenness[g]
{1118.26, 1058.15, 540.601, 127.365, 1175.53, 678.175, 206.929, \
128.576, 204.019, 535.316, 487.858, 391.669, 0., 135.039, 0., \
52.5324, 104.28, 12.2286, 75.8798, 110.155, 68.8282, 13.9095, \
46.4209, 99.3299, 0., 168.196, 213.871, 358.855, 0., 64.9572, \
5.12619, 102.369, 17.978, 15.569, 95.7266, 8.45843, 25.4984, 13.0274, \
0., 71.2012, 47.2895, 32.4444, 8.20833, 0., 27.0286, 10.9357, \
4.60238, 0., 14.7095, 24.7944, 79.125, 7.38301, 22.0817, 43.9635, \
11.7135, 10.9952, 40.8782, 11.2429, 0., 60.0431, 9.36667, 32.4529, \
85.4487, 100.431, 15.205, 93.2876, 60.0548, 9.2, 0., 0., 10.512, \
9.37438, 8.42222, 45.7937, 3.61667, 9.23333, 53.3897, 11.4012, \
22.0959, 5.24091, 10.2647, 8.66017, 9.97438, 11.0429, 15.8765, \
12.7798, 0., 30.1744, 0., 0., 4.0373, 9.7, 1., 10.4883, 0., 0., \
13.7861, 13.8594, 1.7, 2.80952}

… or using Mathematica’s built-ins, and obtain the same result.

BetweennessCentrality[g]
{1118.26, 1058.15, 540.601, 127.365, 1175.53, 678.175, 206.929, \
128.576, 204.019, 535.316, 487.858, 391.669, 0., 135.039, 0., \
52.5324, 104.28, 12.2286, 75.8798, 110.155, 68.8282, 13.9095, \
46.4209, 99.3299, 0., 168.196, 213.871, 358.855, 0., 64.9572, \
5.12619, 102.369, 17.978, 15.569, 95.7266, 8.45843, 25.4984, 13.0274, \
0., 71.2012, 47.2895, 32.4444, 8.20833, 0., 27.0286, 10.9357, \
4.60238, 0., 14.7095, 24.7944, 79.125, 7.38301, 22.0817, 43.9635, \
11.7135, 10.9952, 40.8782, 11.2429, 0., 60.0431, 9.36667, 32.4529, \
85.4487, 100.431, 15.205, 93.2876, 60.0548, 9.2, 0., 0., 10.512, \
9.37438, 8.42222, 45.7937, 3.61667, 9.23333, 53.3897, 11.4012, \
22.0959, 5.24091, 10.2647, 8.66017, 9.97438, 11.0429, 15.8765, \
12.7798, 0., 30.1744, 0., 0., 4.0373, 9.7, 1., 10.4883, 0., 0., \
13.7861, 13.8594, 1.7, 2.80952}

Let us now assign weights to the edges. Many IGraph/M functions, including IGBetweenness, support edge weights.

wg = SetProperty[g, EdgeWeight -> RandomReal[1, EdgeCount[g]]];
IGBetweenness[wg]
{1569., 1509., 697., 506., 1510., 948., 173., 0., 106., 827., 663., \
379., 0., 318., 0., 360., 0., 0., 83., 129., 1., 0., 227., 582., 0., \
91., 236., 213., 0., 60., 0., 334., 1., 53., 549., 0., 0., 0., 0., \
10., 0., 0., 0., 0., 68., 68., 17., 357., 27., 16., 80., 0., 0., 0., \
437., 0., 0., 0., 52., 22., 0., 0., 62., 139., 93., 187., 1., 7., 0., \
0., 0., 16., 0., 69., 10., 98., 0., 1., 4., 21., 0., 0., 0., 0., 0., \
0., 0., 43., 0., 0., 98., 0., 0., 0., 0., 0., 0., 63., 25., 4.}

Notice that Mathematica 12.0 does not include functionality to compute weighted vertex betweenness. The built-in function BetweennessCentrality[] ignores the weights.

BetweennessCentrality[wg]
{1118.26, 1058.15, 540.601, 127.365, 1175.53, 678.175, 206.929, \
128.576, 204.019, 535.316, 487.858, 391.669, 0., 135.039, 0., \
52.5324, 104.28, 12.2286, 75.8798, 110.155, 68.8282, 13.9095, \
46.4209, 99.3299, 0., 168.196, 213.871, 358.855, 0., 64.9572, \
5.12619, 102.369, 17.978, 15.569, 95.7266, 8.45843, 25.4984, 13.0274, \
0., 71.2012, 47.2895, 32.4444, 8.20833, 0., 27.0286, 10.9357, \
4.60238, 0., 14.7095, 24.7944, 79.125, 7.38301, 22.0817, 43.9635, \
11.7135, 10.9952, 40.8782, 11.2429, 0., 60.0431, 9.36667, 32.4529, \
85.4487, 100.431, 15.205, 93.2876, 60.0548, 9.2, 0., 0., 10.512, \
9.37438, 8.42222, 45.7937, 3.61667, 9.23333, 53.3897, 11.4012, \
22.0959, 5.24091, 10.2647, 8.66017, 9.97438, 11.0429, 15.8765, \
12.7798, 0., 30.1744, 0., 0., 4.0373, 9.7, 1., 10.4883, 0., 0., \
13.7861, 13.8594, 1.7, 2.80952}

Let us delete the minimum feedback edge set to obtain an acyclic graph:

acg = EdgeDelete[g, IGFeedbackArcSet[g]]

1uee4mk125a5z

And try out a few of igraph’s layout algorithms.

{IGLayoutGraphOpt[acg], IGLayoutKamadaKawai[acg], 
 IGLayoutFruchtermanReingold[acg]}

0hc8phhd0f643

Layout functions typically have many options to tune:

Options[IGLayoutGraphOpt]
{"MaxIterations" -> 500, "NodeCharge" -> 0.001, "NodeMass" -> 30, 
"SpringLength" -> 0, "SpringConstant" -> 1, "MaxStepMovement" -> 5, 
"Continue" -> False, "Align" -> True}

Increasing the number of iterations will usually improve the result.

IGLayoutGraphOpt[acg, "MaxIterations" -> 5000]

0bvfknw1ptup9

A final note

Please refer to the usage messages for information on how to use each function. For more information on the meaning of various function options, the algorithms used by the functions, references, etc. please refer to the C/igraph documentation. The igraph documentation provides article references for most nontrivial algorithms.

The following sections provide general information on each functionality area, and show common usage patterns.

Graph creation

All the graph creation functions in IGraph/M take any standard Mathematica Graph option such as VertexLabels, EdgeLabels, VertexStyle, GraphStyle, PlotTheme, etc.

IGLCF[{5, -5}, 7, GraphStyle -> "SmallNetwork"]

12gu7wxpdux24

Many included graph creation functions implement random graph models. These use igraph’s (not Mathematica’s) random number generator, which can be re-seeded using IGSeedRandom[].

Deterministic graph generators

IGShorthand

IGShorthand provides an easy way to create small graphs from a simple and quick-to-type notation.

?IGShorthand

0dw3l58h9fj41

The available options are:

Construct a cycle graph.

IGShorthand["1-2-3-4-1"]

0ogsa8djwa790

Vertex labels are shown by default. They can be turned off using VertexLabels -> None.

IGShorthand["1-2-3-1", VertexLabels -> None]

05u3brvudo3q2

The interpretation of - as directed or undirected is controlled by the DirectedEdges option.

IGShorthand["1-2-3-1", DirectedEdges -> True]

0t9f0gmvwxf4t

Directed edges can be input using ->, <- or <->.

IGShorthand["Jim -> Suzy <- Joe"]

0xwilbycb38jh

<-> is interpreted as a pair of directed edges.

IGShorthand["1<->2->3"]

0fylxqhnp0mtm

Mixed graphs, containing both directed and undirected edges, are supported. Note that mixed graphs are not allowed as input to most IGraph/M functions.

IGShorthand["1-2<-3"]

0hp936ww4qjoc

Disconnected components are separated by commas.

IGShorthand["1, 2-3, 4-5-6"]

1cy39zcje357t

Groups of vertices can be given using the colon separator. Edges will be connected to each vertex in the group. This makes it easy to specify a complete graph …

IGShorthand["A:B:C:D:E -- A:B:C:D:E"]

1o92p3h7pr9pa

… or a complete bipartite graph.

IGLayoutBipartite@IGShorthand["a:b:c - 1:2:3:4"]

0teey3qrmquht

Vertex names are taken as strings, except when they can be interpreted as an integer.

IGShorthand["xyz - 137"] // VertexList // InputForm
{"xyz", 137}

Spaces are allowed in vertex names, and edges can be specified using any number of - characters.

IGShorthand["Sophus Lie --- Camille Jordan"]

0iuteubh5tksk

Self-loops and parallel edges are removed by default because these are often created as an undesired by-product of vertex groups. They can be re-enabled using the SelfLoops or MultiEdges options when desired.

IGShorthand["1:2:3 - 1:2:3", SelfLoops -> True]

1dvo8xn0b924g

IGShorthand["1:2:3 - 1:2:3", SelfLoops -> True, MultiEdges -> True]

02dtuod7bxbh3

IGShorthand["1-2-1-3", MultiEdges -> True]

0wh2qpvzkli8d

The vertex order will follow the order of appearance of vertices in the input string. To control the order, simply list vertices at the beginning of the shorthand specification.

IGShorthand["4-3-1-2-4"] // VertexList
{4, 3, 1, 2}
IGShorthand["1,2,3,4, 4-3-1-2-4"] // VertexList
{1, 2, 3, 4}

IGEmptyGraph

?IGEmptyGraph

0yxyyt1z3rx6p

IGEmptyGraph is a convenience function for creating graphs with no edges.

Create a null graph.

IGEmptyGraph[] // VertexCount
0

Create an empty graph on 15 vertices.

IGEmptyGraph[15]

1wm9nh0m2jc0g

The built-in EmptyGraphQ returns True for these graphs.

EmptyGraphQ[%]
True

IGLCF

?IGLCF

17rinsyri8rli

0zrqwr4usuwcr creates a graph based on the LCF notation1oomllwl735wo.

The Möbius–Kantor graph is [5, -5]^8.

IGLCF[{5, -5}, 8, GraphStyle -> "DiagramGreen"]

0ykgvrlwpr7wc

The Pappus graph is [5, 7, -7, 7, -7, -5]^3.

IGLCF[{5, 7, -7, 7, -7, -5}, 3, GraphStyle -> "ThickEdge"]

0nrc4phbxjh5i

The cuboctahedral graph is [4, 2]^6.

IGLayoutKamadaKawai3D@IGLCF[{4, 2}, 6]

0sftw9ilxdwkl

IGChordalRing

?IGChordalRing

0z59pyf502vft

IGChordalRing[n, w] constructs an extended chordal ring based on the offset specification vector or matrix \(w\) as follows:

  1. It creates a cycle graph (i.e. ring) on \(n\) vertices.

  2. For each vertex \(i\) on the ring, it adds a chord to a vertex \(w[[(i \bmod p)]]\) steps ahead counter-clockwise on the ring.

  3. If \(w\) is a matrix, the procedure is carried out for each row.

The number of vertices \(n\) must be an integer multiple of the number of columns in the matrix \(w\).

The available options are:

Create an extended chordal graph.

IGChordalRing[15, {3, 4, 8}, GraphStyle -> "Business"]

17x1dy0iczx8o

Negative offsets are allowed.

IGChordalRing[15, {{3, 4, 8}, {-3, -4, -8}}]

00h1ofpl30b06

IGChordalGraph may create self-loops or multi-edges. This can be prevented by setting the SelfLoops or MultiEdges options to False.

IGChordalRing[15, {{3, 4, 8}, {-3, -4, -8}}, MultiEdges -> False]

1j9ld9fc0aq68

Create a chordal graph with directed edges.

IGChordalRing[8, {2, 3}, DirectedEdges -> True, 
 GraphStyle -> "DiagramGold"]

1u5r45299mwyi

Colour the chords of the ring based on which entry of the \(w\) vector they correspond to.

w = {2, 3, 4};
IGChordalRing[12, w, GraphStyle -> "ThickEdge", 
  EdgeStyle -> Opacity[1/2]] // IGEdgeMap[
  ColorData[97],
  EdgeStyle -> Function[g,
    Table[
     If[i <= VertexCount[g], 0, Mod[i, Length[w], 1]], {i, 
      EdgeCount[g]}]
    ]
  ]

12zlpfg0himlu

IGSquareLattice

?IGSquareLattice

1dh2608xel54m

0cakqac0dk8it creates a square lattice graph of the given dimensions. The available options are:

In previous versions, IGSquareLattice was called IGMakeLattice. This name can still be used as a synonym for the sake of backwards compatibility, however, it will be removed in a future version.

To create other types of lattices, see IGTriangleLattice and IGLatticeMesh.

IGSquareLattice[{3, 4}, GraphStyle -> "VintageDiagram"]

0xv4xylq8x1nq

IGSquareLattice[{10, 10}, "Periodic" -> True]

0d1ghmdjvtxkw

Graph3D@IGSquareLattice[{5, 4, 3}, GraphStyle -> "Prototype"]

05k26gc2k85w8

Graph3D@IGSquareLattice[{2, 5}, DirectedEdges -> True, 
  "Periodic" -> True, PlotTheme -> "NeonColor"]

1huhtmopmo3r9

IGTriangularLattice

?IGTriangularLattice

19ecqq9md6i2x

IGTriangularLattice can create a triangular grid graph in the shape of a triangle or a rectangle. To generate other types of lattices, see IGSquareLattice and IGLatticeMesh.

The available options are:

Generate a triangular lattice on an equilateral triangle with 6 vertices along each of its edges.

IGTriangularLattice[6, GraphStyle -> "SmallNetwork"]

0wmtmmdmxpj43

Create a directed triangle lattice on a rectangle. Notice the vertex labelling and that the arrows are oriented from smaller index vertices to larger index ones, making this an acyclic graph.

IGTriangularLattice[{4, 4}, DirectedEdges -> True,
 VertexShapeFunction -> "Name", PerformanceGoal -> "Quality"]

15tr7plw7yyga

Create a triangle lattice and colour its vertices.

IGTriangularLattice[{8, 6}, VertexSize -> Large, EdgeStyle -> Gray] //
  IGVertexMap[ColorData[98], VertexStyle -> IGMinimumVertexColoring]

1mi1wlv8x6r0l

Take a hexagonal subgraph of a triangle lattice.

g = IGTriangularLattice[13];
center = First@GraphCenter[g];
VertexDelete[g,
 Complement[VertexList[g], AdjacencyList[g, center, 4], {center}]
 ]

0mgfnc28m99tp

Create a periodic (i.e. toroidal topology) triangle lattice.

Graph3D@IGTriangularLattice[{24, 8}, "Periodic" -> True]

1rfkl11nxwnzl

IGKaryTree

?IGKaryTree

1mx6wn0axrtxa

The available options are:

IGKaryTree[15]

10ioc9eb3z47b

IGKaryTree[10, 3, DirectedEdges -> True]

06g5gg3qpksdg

IGSymmetricTree

?IGSymmetricTree

19ehg4hgp1tme

IGSymmetricTree creates a tree where successive layers (i.e. vertices at the same distance from the root) have the specified number of children.

Create a tree where the root has 4 children, its children have 3 children, and so on.

IGSymmetricTree[{4, 3, 2, 1}]

1x6alfl28pnjl

Create a directed tree.

IGSymmetricTree[{4, 2}, DirectedEdges -> True]

1i79bx1qzwqg1

IGSymmetricTree is guaranteed to label vertices in breadth-first order. Deeper layers have higher integer labels.

IGSymmetricTree[{3, 3}, GraphStyle -> "DiagramBlue"]

00cdlmqkbttp5

IGBetheLattice

?IGBetheLattice

0gapb0z0ex1sf

A Bethe lattice is an infinite tree in which all vertices have the same degree. IGBetheLattice[n, k] computes the first n layers of such a tree. Each non-leaf vertex will have degree k. The default degree is 3.

IGBetheLattice differs from CompleteKaryTree in that the degree of the root will be the same as the degree of other non-lead nodes.

IGBetheLattice[5, GraphStyle -> "Prototype", VertexSize -> Large]

0l8u9nlhdomul

Generate a tree where non-leaf nodes have degree 5, and use directed edges.

IGBetheLattice[5, 4, DirectedEdges -> True]

1980l5adn1a2w

Colour vertices based on their distance from the root (i.e. the “layer” they are part of).

IGVertexMap[
 ColorData[68],
 VertexStyle -> (First@IGDistanceMatrix[#, {1}] &),
 IGBetheLattice[5, GraphStyle -> "BasicBlack", VertexSize -> 0.4]
 ]

1anrr14ypmu4p

IGFromPrufer

?IGFromPrufer

1q7ctqyzz8agz

A Prüfer sequence is a unique representation of an \(n\)-vertex labelled tree as \(n-2\) integers between \(1\) and \(n\).

IGFromPrufer[{1, 1, 2, 2}, VertexLabels -> "Name"]

0mfn163i47ukp

Use IGToPrufer to convert a tree back to its Prüfer sequence.

IGToPrufer[%]
{1, 1, 2, 2}

Generate all labelled trees on 4 nodes:

IGFromPrufer[#, VertexLabels -> "Name"] & /@ Tuples[Range[4], {2}]

0j36kf1g6a4rq

Of these, only two are non-isomorphic.

DeleteDuplicates[CanonicalGraph /@ %]

1c89yisn8zhrn

IGExpressionTree

?IGExpressionTree

0f33u6p86ztqn

IGExpressionTree constructs the tree graph corresponding to an arbitrary Mathematica expression. The vertices of the tree will be the positions of the corresponding subexpressions.

IGExpressionTree takes all standard Graph options. The VertexLabels option takes the following special values:

IGExpressionTree constructs a graph corresponding to the structure of a Mathematica expression.

tree = IGExpressionTree[expr = 1 + x^2]

0rgkidds014x6

The expression tree is similar to what TreeForm displays, but unlike TreeForm’s output, it is a Graph object that works with all graph functions.

TreeForm[expr]

1f8qyq6l4kzy7

The vertex names are the position specifications of the corresponding subexpressions.

VertexList[tree]
{{1}, {2, 1}, {2, 2}, {2}, {}}
Extract[expr, %]
{1, x, 2, x^2, 1 + x^2}

Place the vertex labels in the centre and construct an undirected graph.

IGExpressionTree[x^2 + y^2,
 GraphStyle -> "DiagramGold",
 VertexLabels -> Placed["Head", Center], VertexSize -> Large
 ]

1cke2fqzqh9jt

Create an undirected graph, labelled with subexpressions.

IGExpressionTree[Normal[Sin[x] + O[x]^5], DirectedEdges -> False,
 VertexLabels -> "Subexpression"]

1wsoths7b1evs

Certain trees are easier to construct through their corresponding nested expression.

IGExpressionTree[#, VertexLabels -> "Index"] & /@ Groupings[5, 3]

18bvvnt5mu02d

An equivalent of IGSymmetricTree can be easily implemented using IGExpressionTree.

IGExpressionTree[ConstantArray[1, {3, 4, 5}], VertexLabels -> None, 
 GraphLayout -> "RadialEmbedding"]

0pzmxmi4labbm

Define a tree through a substitution system.

IGExpressionTree[
 Nest[ReplaceAll[{0 -> {0, 1}, 1 -> {0}}], {0, 1}, 3],
 VertexLabels -> None, GraphStyle -> "VibrantColor"
 ]

04ji26abf9lso

To format each node so that it fits a label, it is necessary to set an explicit VertexShapeFunction.

IGExpressionTree[First@Roots[x^2 + a x + 1 == 0, x],
   VertexLabels -> "Subexpression",
   PerformanceGoal -> "Quality",
   ImageSize -> 280
   ] //
  IGVertexMap[
   Function[e, Inset[Panel[e], #1] &],
   VertexShapeFunction -> IGVertexProp[VertexLabels]
   ] // RemoveProperty[#, VertexLabels] &

0ffmt6j98fjbs

IGCompleteGraph

?IGCompleteGraph

0cgwnr6cl06h3

The available options are:

Create an undirected complete graph with loops.

IGCompleteGraph[5, SelfLoops -> True]

14y0lpn7wzcl5

Create a directed complete graph with loops.

IGCompleteGraph[6, SelfLoops -> True, DirectedEdges -> True]

15dojw681xpd0

Create a list of complete graphs starting with the null graph.

IGCompleteGraph /@ Range[0, 3]

15h0qi7y4qlbg

Create a complete graph on the given vertices.

IGCompleteGraph[{"a", "b", "c", "d"}, GraphStyle -> "DiagramBlue"]

01uqmrbpjjn5n

IGCompleteAcyclicGraph

?IGCompleteAcyclicGraph

0q83z9fq046w8

Create a complete acyclic directed graph on 5 vertices.

IGCompleteAcyclicGraph[5]

0omatnq4oqxrf

Create a complete acyclic graph on the given vertices. The directed edges always run from vertices that appear earlier in the list to those that appear later.

IGCompleteAcyclicGraph[CharacterRange["a", "f"], 
 GraphStyle -> "DiagramGold"]

0d3cifmygr6oh

IGKautzGraph

?IGKautzGraph

1ac1bs7ex2vd4

The vertices of the Kautz graph \(K_m^n\) are strings of length \(n+1\), composed of \(m+1\) distinct symbols, with the restriction that two adjacent symbols in the string may not be the same. A vertex \(s_1s_2\text{$\ldots $s}_ns_{n+1}\) connects to all other vertices of the form \(s_2\text{$\ldots $s}_{n+1}x\), where \(x\) can be any symbol distinct from \(s_{n+1}\).

The Kautz graph \(K_m^n\) has \((m+1) m^n\) vertices, with each vertex having in-degree and out-degree \(m\). Therefore, it has \((m+1) m^{n+1}\) edges.

VertexCount@IGKautzGraph[3, 2] == (3 + 1)*3^2
True
VertexOutDegree@IGKautzGraph[3, 2]
{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, \
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

The line graph of Kautz graph \(K_m^n\) is \(K_m^{n+1}\).

IGIsomorphicQ[
 LineGraph@IGKautzGraph[2, 2],
 IGKautzGraph[2, 3]
 ]
True

Visualize the Kautz graph \(K_2^3\) on 3 characters with string length 4 in three dimensions.

Graph3D@IGKautzGraph[2, 3]

1lhhqxmp3brs7

Label the vertices of the Kautz graph on 3 characters with string length 2.

labels = StringJoin /@ 
   DeleteCases[Tuples[{"A", "B", "C"}, {2}], {c_, c_}];
IGKautzGraph[2, 1,
 VertexLabels -> Thread[Range[6] -> (Placed[#, Center] &) /@ labels],
 VertexSize -> Large, VertexShapeFunction -> "Capsule", 
 PerformanceGoal -> "Quality",
 PlotTheme -> "CoolColor", VertexLabelStyle -> White
 ]

12fg4xdbbkci2

IGDeBruijnGraph

?IGDeBruijnGraph

1lbxq2d9kcr79

IGDeBruijnGraph[3, 2, GraphStyle -> "BackgroundBlue", 
 EdgeStyle -> Thick]

0lq8cgri91knt

IGRealizeDegreeSequence

?IGRealizeDegreeSequence

0kjd6o4fc21hl

This function uses the Havel–Hakimi algorithm (undirected case) or Kleitman–Wang algorithm (directed case) to construct a graph with the given degree sequence. These algorithms work by selecting a vertex, and connecting up all its free (out-)degrees to other vertices with the largest degrees. In the directed case, the “largest” degrees are determined by lexicographic ordering of (in, out)-degree pairs. The order in which vertices are selected is controlled by the Method option.

To randomly sample multiple realizations of a degree sequence, use IGDegreeSequenceGame.

Available Method option values:

degseq = VertexDegree@IGGiantComponent@RandomGraph[{50, 50}]
{3, 4, 4, 4, 2, 1, 2, 3, 3, 1, 2, 3, 2, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, \
3, 1, 3, 2, 1, 2, 2, 3, 1, 3, 1, 1, 1, 1, 1}
IGRealizeDegreeSequence[degseq]

12d3rc3pbenvy

N@GraphAssortativity[%]
-0.524347
IGRealizeDegreeSequence[degseq, Method -> "LargestFirst"]

08bzzaloxh0q4

N@GraphAssortativity[%]
0.904728

Create a directed graph.

g = IGBarabasiAlbertGame[50, 1]

0em76fnm12bta

indegseq = VertexInDegree[g];
outdegseq = VertexOutDegree[g];
IGRealizeDegreeSequence[outdegseq, indegseq]

1faudy4pui4j1

{VertexOutDegree[%] == outdegseq, VertexInDegree[%] == indegseq}
{True, True}

IGGraphAtlas

?IGGraphAtlas

0bf8ible9c0tb

This function is provided for convenience for those who have the book An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, and for those who wish to replicate results obtained with other packages that include this database. For all other purposes, use Mathematica’s built-in GraphData function.

Retrieve graph number 789:

IGGraphAtlas[789]

1n95gfxjbqwh2

IGFromNauty

?IGFromNauty

1ghcboz81bazj

IGFromNauty converts a Graph6, Digraph6 or Sparse6 string to a graph. These formats originate with the nauty suite of programs and are supported by many other graph theory software.

Interpret a Graph6 string.

IGFromNauty["Gr`HOk"]

1d6oln947d0nf

Interpret a Sparse6 string. These start with a : character.

IGFromNauty[":I`ESgTlVF"]

1upsvbxdrkwm4

Interpret a Digraph6 string. These start with a & character.

IGFromNauty["&FKB?oMB_W?"]

0w8dp603bjwys

IGFromNauty does not support headers or whitespace in the string. To handle these, or to interpret a multiline string, use IGImportString[…, "Nauty"].

IGFromNauty[">>graph6<<DYw"]

02x8vjvv9d03l

$Failed
IGImportString[
 ">>graph6<<DYw
 Dhs
 Dxo
 DVW
 ", "Nauty"]

0dhroxfbkrg6k

Random graph generators

These graph creation functions use igraph’s random graph generator, which can be seeded using IGSeedRandom.

?IG*Game*

1uyoky6anvn25

Basic random graphs

?IGErdosRenyiGameGNM

1q6b8v4qb6tzs

?IGErdosRenyiGameGNP

16rggv3crdky6

IGErdosRenyiGameGNM uniformly samples graphs with \(n\) vertices and \(m\) edges. This random graph model is known as the Erdős–Rényi \(G(n,m)\) model.

In IGErdosRenyiGameGNP, each edge is present with the same and independent probability. This model is known as the Erdős–Rényi \(G(n,p)\) model or Gilbert model.

The available options are:

Create a random graph with 10 vertices and 20 edges.

IGErdosRenyiGameGNM[10, 20, GraphStyle -> "VintageDiagram"]

1ohc6f45j99uj

Create a directed graph and allow self-loops.

IGErdosRenyiGameGNM[10, 35, DirectedEdges -> True, SelfLoops -> True]

1lytons0ptdm0

Insert each edge with a probability of 20%.

IGErdosRenyiGameGNP[20, 0.2, GraphStyle -> "RoyalColor"]

0p3g9n34i7bu8

The \(G(n,p)\) model produces connected graphs with high probability for \(p>\ln (n)/n\).

n = 300;
ListPlot[
 Table[
  {p, Mean@
    Boole@Table[ConnectedGraphQ@IGErdosRenyiGameGNP[n, p], {50}]},
  {p, 0, 0.05, 0.0005}
  ],
 GridLines -> {{Log[n]/n}, None}
 ]

1twnb0cfyzeip

Random bipartite graphs

?IGBipartiteGameGNM

04oueq1ckjyh1

?IGBipartiteGameGNP

0idem3yb162et

IGBipartiteGameGNM and IGBipartiteGameGNP are equivalent to IGErdosRenyiGNM and IGErdosRenyiGNP, but they generate bipartite graphs.

The available options are:

IGBipartiteGameGNP[5, 5, 0.5, VertexLabels -> "Name"]

1nbo393ez2o08

Create a bipartite directed graph with edges running either uni-directionally or bidirectionally between the two partitions.

IGLayoutBipartite@
   IGBipartiteGameGNM[10, 10, 30, DirectedEdges -> True, 
    "Bidirectional" -> #] & /@ {False, True}

0t1ic4dks08or

IGTreeGame

?IGTreeGame

0trzep7fyxb1p

IGTreeGame samples uniformly from the set of labelled trees.

Available options:

Available Method options:

IGTreeGame[250, GraphLayout -> "LayeredEmbedding", 
 PlotTheme -> "PastelColor"]

0qlvgxqq2ifm5

There are several distinct labellings of isomorphic trees. All of these are generated with equal probability.

Table[
  IGTreeGame[3, VertexLabels -> Automatic],
  {100}
  ] // DeleteDuplicatesBy[AdjacencyMatrix]

1bk0wcdlo2vf8

Generate directed trees.

Table[IGTreeGame[6, DirectedEdges -> True, 
  GraphLayout -> "LayeredDigraphEmbedding"], {5}]

0qmlm3an13ox7

Generate a random sparse connected graph by first creating a tree, then adding cycle edges. Note that this method does not sample connected graphs uniformly.

randomConnected[nodeCount_, edgeCount_] :=
 Module[{tree},
  tree = IGTreeGame[nodeCount];
  EdgeAdd[tree, 
   RandomSample[EdgeList@GraphComplement[tree], 
    edgeCount - nodeCount + 1]]
  ]
randomConnected[100, 120]

1h2bep6igpke0

Colour the nodes of a random tree by their inverse average distance to other nodes.

IGVertexMap[
 ColorData["SolarColors"],
 VertexStyle -> Rescale@*IGCloseness,
 IGTreeGame[1000, Background -> Black, ImageSize -> Large, 
  EdgeStyle -> LightGray]
 ]

0hkvwairdvxwg

IGDegreeSequenceGame

?IGDegreeSequenceGame

1nnrkjaselxir

IGDegreeSequenceGame implements various random sampling methods for graphs with a given degree sequence. To quickly construct a single realization of a degree sequence, use IGRealizeDegreeSequence.

IGDegreeSequenceGame takes the following values for its Method option:

The default method is "FastSimple". Note that it does not sample uniformly.

degseq = VertexDegree@RandomGraph[{50, 100}];
IGDegreeSequenceGame[degseq, Method -> "ConfigurationModel"]

1iwh6yxmmghd5

SimpleGraphQ[%]
False
IGDegreeSequenceGame[degseq, Method -> "ConfigurationModelSimple"]

0iesynuynt2eh

SimpleGraphQ[%]
True

The configuration model algorithm is too slow to construct even small dense graphs.

ds = VertexDegree@RandomGraph[{10, Binomial[10, 2] - 5}]
{8, 8, 8, 8, 7, 9, 9, 6, 9, 8}
TimeConstrained[
 IGDegreeSequenceGame[ds, Method -> "ConfigurationModelSimple"], 1]
$Aborted

Graphs that are almost complete can be sampled by generating the complement first.

GraphComplement@
 IGDegreeSequenceGame[9 - ds, Method -> "ConfigurationModelSimple"]

0ngcxm4y9tojq

ds == VertexDegree[%]
True

IGKRegularGame

?IGKRegularGame

052btu3he8zvf

In a \(k\)-regular graph all vertices have degree \(k\). The current implementation is able to generate any \(k\)-regular graph, but it does not sample them with precisely the same probability.

The available options are:

IGKRegularGame[10, 3]

0ewhqbahlxqo2

Not all parameters are valid:

IGKRegularGame[5, 3]

13449qxa9s5sq

1e6l0x8j0cadc

$Failed

There are no graphs with 5 vertices each having degree 3.

IGGraphicalQ[{3, 3, 3, 3, 3}]
False

IGGrowingGame

?IGGrowingGame

0ie0imfbj3erj

IGGrowingGame[n, k] creates a random graph by successively adding vertices to the graph until the vertex count n is reached. At each step, k new edges are added as well.

The available options are:

IGGrowingGame[50, 2]

1sx7w64y19xhv

With "Citation" -> True, the newly added edges are connected to the newly added vertices.

IGGrowingGame[50, 1, "Citation" -> True]

1eexkz4bt6de1

Note that while this model can be used to generate random trees, it will not sample them uniformly. If uniform sampling is desired, use IGTreeGame instead.

Create a directed citation graph.

IGGrowingGame[20, 2, DirectedEdges -> True, "Citation" -> True, 
 GraphStyle -> "Web"]

1kl1a6n9h49se

IGBarabasiAlbertGame

?IGBarabasiAlbertGame

0quwiwymhfroh

IGBarabasiAlbertGame implements a preferential attachment model. It generates a graph by sequentially adding new vertices with the specified number of edges (\(k\)). The edges will connect to existing vertices with probability \(d^{\beta }+A\), where \(d\) is the in-degree of the existing vertex. The default parameters are \(\beta =1\) and \(A=1\).

The available options are:

Available Method option values:

The built-in BarabasiAlbertGraphDistribution is equivalent to using \(A=0\) and DirectedEdges -> False in IGBarabasiAlbertGame.

IGBarabasiAlbertGame[100, 1]

1gxbymcvnqzaa

Use attachment probability proportional to degree^1.5 + 1.

IGBarabasiAlbertGame[100, 2, {1.5, 1}]

00hzzanqud3qn

The "Bag" method may generate parallel edges:

IGBarabasiAlbertGame[100, 2, Method -> "Bag"]

1qbjtjtj9cpoa

MultigraphQ[%]
True

Create a graph with the given out-degree sequence. The \(k^{\text{th}}\) entry in the degree sequence list must be no greater than \(k\).

IGBarabasiAlbertGame[12, {1, 2, 3, 2, 1, 3, 4, 5, 1, 5, 2}, 
 PlotTheme -> "Minimal"]

0ablzytxu1bqa

VertexOutDegree[%]
{0, 1, 2, 3, 2, 1, 3, 4, 5, 1, 5, 2}

Create a preferential attachment graph using a 4-node complete graph as the starting point.

IGBarabasiAlbertGame[10, 1, "StartingGraph" -> CompleteGraph[4]]

17arhwd1ycw8p

IGWattsStrogatzGame

?IGWattsStrogatzGame

0a75li60hbi13

The two-argument form produces results equivalent to that of the built-in WattsStrogatzGraphDistribution.

IGWattsStrogatzGame[30, 0.05, PlotTheme -> "Web"]

1en76s6hc0kbh

The extended form allows for multi-dimensional lattices. Create a graph by randomly rewiring a two-dimensional toroidal lattice of \(10\times 10\) nodes:

Graph3D@IGWattsStrogatzGame[10, 0.01, {2, 1}]

0rwsaf8mt3nte

IGStaticFitnessGame

?IGStaticFitnessGame

0b3dmuhgkicmn

IGStaticFitnessGame generates a random graph by connecting vertices based on their fitness score. The algorithm starts with \(n\) vertices and no edges. Two vertices are selected with probabilities proportional to their fitness scores (for directed graphs, a starting vertex is selected based on its out-fitness and an end vertex based on its in-fitness). If they are not yet connected, an edge is inserted between them. The procedure is repeated until the number of edges reaches \(m\).

The expected degree of each vertex is proportional to its fitness score. This is exactly true when self-loops and multi-edges are allowed, and approximately true otherwise.

IGStaticFitnessGame approximates the Chung–Lu model in which each edge i \[UndirectedEdge] j is present independently, with probability

\[p_{ij}= \begin{array}{ll} \{ & \begin{array}{ll} \frac{f_if_j}{2m} & \text{if} i\neq j \\ \frac{f_if_j}{4m} & \text{if} i=j \\ \end{array} \\ \end{array} ,\]

where \(m=\frac{1}{2}\sum _kf_k\).

Unlike the Chung–Lu algorithm, which would require \(O\left(m^2\right)\) computation steps, IGStaticFitnessGame runs in \(O(m)\) time.

The available options are:

Create an undirected graph with four high-degree nodes and 40 low-degree ones.

weights = Join[{10, 10, 10, 10}, ConstantArray[1, 40]];
IGStaticFitnessGame[Total[weights]/2, weights]

09cjqmzjv5w3g

VertexDegree[%]
{5, 5, 12, 8, 2, 2, 1, 2, 2, 1, 1, 2, 2, 0, 2, 1, 2, 0, 0, 3, 1, 1, \
0, 0, 1, 2, 0, 3, 0, 2, 1, 2, 1, 1, 1, 2, 0, 1, 2, 0, 0, 3, 2, 1}

Create a directed graph.

IGStaticFitnessGame[30, Range[10], Range[10, 1, -1]]

0r5hxnt5vz0ht

When self-loops and multi-edges are allowed, the expected degree of each vertex is proportional to its fitness score.

degrees = {3, 3, 2, 2, 2, 1, 1};
Table[
   VertexDegree@IGStaticFitnessGame[
     Total[degrees]/2, degrees,
     SelfLoops -> True, MultiEdges -> True
     ],
   {1000}
   ] // N // Mean
{3.03, 2.97, 2.023, 1.957, 2.056, 0.977, 0.987}

When generating simple graphs, this holds only approximately.

degrees = {3, 3, 2, 2, 2, 1, 1};
Table[
   VertexDegree@IGStaticFitnessGame[
     Total[degrees]/2, degrees
     ],
   {1000}
   ] // N // Mean
{2.703, 2.625, 2.04, 2.071, 2.086, 1.23, 1.245}

IGStaticPowerLawGame

?IGStaticPowerLawGame

0hgfhoyypiph9

IGStaticPowerLawGame generates a directed or undirected random graph where the degrees of vertices follow power-law distributions with prescribed exponents. For directed graphs, the exponents of the in- and out-degree distributions may be specified separately.

This function is equivalent to IGStaticFitnessGame with a fitness vector \(f\) where \(f_i=i^{-\alpha }\) and \(\alpha =\frac{1}{\text{exponent}-1}\).

Note that significant finite size effects may be observed for exponents smaller than 3 in the original formulation of the game. This function removes the finite size effects by default by assuming that the fitness of vertex \(i\) is \(\left(i+i_0\right){}^{-\alpha }\), where \(i_0\) is a constant chosen appropriately to ensure that the maximum degree is less than the square root of the number of edges times the average degree; see the paper of Chung and Lu, and Cho et al. for more details.

The available options are:

Create a graph with a power-law degree distribution of exponent 2.5.

g = IGStaticPowerLawGame[100000, 200000, 2.5];
Histogram[VertexDegree[g], "Log", {"Log", "PDF"}]

0hhfiftobj7qz

Create a directed graph with power-law in- and out-degree distributions.

IGStaticPowerLawGame[50, 150, 3, 3]

184q8emxh0hu2

References

IGStochasticBlockModelGame

?IGStochasticBlockModelGame

1vh84346ibl0s

The ratesMatrix argument gives the connection probability between and within blocks (groups of vertices). The blockSizes argument gives the size of each block (vertex group).

The available options are:

1iwgvu4hi7qrt

1xvg3v8omdfqa

IGAdjacencyMatrixPlot[%]

0qibspdcordwr

IGForestFireGame

?IGForestFireGame

0yw4vyna0jpsn

The forest fire model is a growing graph model. In every time step, a new vertex is added to the graph. The new vertex chooses the specified number of ambassadors (default: 1) and starts a simulated forest fire at their locations. The fire spreads through the directed edges. The spreading probability along an edge is given by pForward. The fire may also spread backwards on an edge with probability pForward * rBackward. When the fire has ended, the newly added vertex connects to all the vertices that were burned in the fire.

The forest fire model intends to reproduce the following network characteristics, observed in real networks:

The available options are:

Generate a graph with only forward burning.

IGForestFireGame[30, 0.2, 0,
 GraphLayout -> "SpringEmbedding"]

1ueu1r907azrs

Generate a graph from the forest fire model, and visualize its community structure.

IGForestFireGame[100, 0.2, 1, 2, DirectedEdges -> False, 
 GraphLayout -> {"EdgeLayout" -> "HierarchicalEdgeBundling"}]

1tjaobhcj5f88

Plot the cumulative in-degree distribution for different backward to forward burning probability ratios.

Table[
 Histogram[
  VertexInDegree@
   IGForestFireGame[2000, 0.4, r, 2, DirectedEdges -> True],
  "Log", {"Log", "SurvivalCount"},
  PlotLabel -> Row[{"r=", r}]
  ],
 {r, 0, 0.8, 0.2}
 ]

0064c1hi2ano0

References

IGCallawayTraitsGame

?IGCallawayTraitsGame

0730hru2ecu3t

This function simulates a growing random graph according to the following algorithm:

At each time step, a new vertex is added. Its type is randomly selected according to the type weights. Then k existing pairs of vertices are selected randomly, and each pair attempts to connect. The probability of success for given types of vertices is given by the preference matrix.

This algorithm may create self-loops and multi-edges.

The available options are:

1o49n8n4cr4ch

0y1yyuyexc9xg

IGEstablishmentGame

?IGEstablishmentGame

0p72g79hnlaa7

This function simulates a growing random graph according to the following algorithm:

At each time step, a new vertex is added. Its type is randomly selected according to the type weights. It attempts to connect to k distinct existing vertices. The probability of success for given types of vertices is given by the preference matrix.

The available options are:

0ezn0jc1mcutr

05eneb8w08qrv

IGGeometricGame

?IGGeometricGame

1vvkwp3q4hmqj

Available options:

IGGeometricGame[50, 0.2]

0inemg6hur6p0

Use a toroidal topology and draw “wraparound” edges with dashed lines.

IGGeometricGame[50, 0.2, "Periodic" -> True] //
 IGEdgeMap[
  If[EuclideanDistance @@ # > 0.2, Dashed, None] &, 
  EdgeStyle -> IGEdgeVertexProp[VertexCoordinates]
  ]

0eblrfkxxjzr8

Graph modification

IGRewire

?IGRewire

1xo440en78z03

IGRewire will try to rewire the edges of the graph the given number of times by switching random pairs of edges as below, thus preserving the graph’s degree sequence.

0dd5decstywmx1i6qe95zvod5y or 0dd5decstywmx0pwhvxl25yj8n

The switches succeed only if they would not create multi-edges. The parameter \(n\) specifies the number of switch attempts, not the number of successful switches.

For directed graphs, the switches are such that they preserve both the in- and out-degree sequence.

The vertex ordering of the graph is retained.

Warning: Most graph properties, such as edge weights, will be lost.

The available options are:

Generate a random network with scale-free degree distribution:

IGRewire[IGBarabasiAlbertGame[200, 2, DirectedEdges -> False], 10000]

0x4jdgycsn433

Use SelfLoops -> True to allow creating loops.

Table[IGRewire[PathGraph@Range[4], 100, SelfLoops -> True], {5}]

1xnmsqjxrjuz3

IGRewrire never creates any multi-edges. Multigraphs are allowed as input, but a warning is given.

10j833svoqiw2

0kl2jkk9lxs1z

0p1px0b6ibk9j

Uniformly sample simple labelled graphs with a given degree sequence by first creating a single realization, then rewiring it a sufficient amount of times.

degseq = {3, 3, 2, 2, 1, 1};
Table[
    IGRewire[IGRealizeDegreeSequence[degseq], 100],
    {1000}
    ] // CountsBy[AdjacencyMatrix] // KeySort // 
 KeyMap[AdjacencyGraph[#, VertexShapeFunction -> "Name"] &]

1tybyg6ycbsjx

IGRewireEdges

?IGRewireEdges

0mqm27vfw99q6

IGRewireEdges randomly rewires each edge of the graph with the given probability. The vertex ordering is retained.

For directed graphs, it can optionally rewire only the starting point or endpoint of directed edges, thus preserving the out- or in-degree sequence. In this case, the MultiEdges option is ignored and multi-edges may be created.

Warning: Most graph properties, such as edge weights, will be lost.

The available options are:

Create a random graph with 10 vertices and 20 edges, while allowing for multi-edges:

IGRewireEdges[RandomGraph[{10, 20}], 1, MultiEdges -> True]

126tp487m7oes

EdgeCount[%]
20

Rewire the endpoint of each edge, preserving the out-degree sequence.

g = RandomGraph[{10, 30}, DirectedEdges -> True];
{VertexInDegree[g], VertexOutDegree[g]}
{{4, 3, 5, 1, 3, 3, 2, 1, 5, 3}, {2, 2, 4, 4, 3, 3, 4, 3, 3, 2}}
rg = IGRewireEdges[g, 1, "Out"];
{VertexInDegree[rg], VertexOutDegree[rg]}
{{3, 7, 4, 1, 1, 2, 3, 3, 2, 4}, {2, 2, 4, 4, 3, 3, 4, 3, 3, 2}}

Note that multi-edges were created.

MultigraphQ[rg]
True

IGVertexContract

?IGVertexContract

1l4789mh49eb8

IGVertexContract[g, {set1, set2, …}] will simultaneously contract multiple vertex sets into single vertices.

The name of a contracted vertex will be the same as the first element of the corresponding set. Vertex ordering is not retained. Edge ordering is retained only when using both SelfLoops -> True and MultiEdges -> True.

Warning: Most graph properties, such as edge weights, will be lost.

The available options are:

1fxc46bm1d9j0

IGVertexContract[g, {{1, 2, 3}, {4, 5}}, VertexLabels -> "Name"]

0jzqtjectk9d3

IGVertexContract[g, {{1, 2, 3}, {4, 5}}, SelfLoops -> True]

11xgan7u6f8i9

IGVertexContract[g, {{1, 2, 3}, {4, 5}}, SelfLoops -> True, 
 MultiEdges -> True]

1kqg3fz0dpugh

IGVertexContract[g, {{1, 2, 3}, {4, 5}}, MultiEdges -> True]

1k079wu6mfabm

When using both SelfLoops -> True and MultiEdges -> True, the edge ordering is maintained relative to the input graph. This allows easily transferring edge weights, and combining them if necessary.

g = IGShorthand["a-b-c-d-a,a-c",
  EdgeWeight -> {1, 2, 3, 4, 5}, EdgeLabels -> "EdgeWeight"]

187kl5ylpjay2

IGWeightedSimpleGraph[
 IGVertexContract[g, {{"a", "b"}},
  SelfLoops -> True, MultiEdges -> True,
  EdgeWeight -> IGEdgeProp[EdgeWeight][g]
  ],
 EdgeLabels -> "EdgeWeight", VertexLabels -> "Name"
 ]

1uo4lytycmn0s

IGConnectNeighborhood

?IGConnectNeighborhood

03vmozexymn6q

IGConnectNeighborhood[g, k] connects each vertex in g to its order k neighbourhood. This operation is also known as the \(k^{\text{th}}\) power of the graph.

IGConnectNeighborhood differs from the built-in GraphPower in that it preserves parallel edges and self-loops.

Warning: Most graph properties, such as edge weights, will be lost.

Connect each vertex to its second order neighbourhood:

IGConnectNeighborhood[CycleGraph[15]]

0zzmn91s5vw1t

Connect each vertex to its third order neighbourhood:

IGConnectNeighborhood[GridGraph[{10, 10}], 3]

101r70pjfil8i

IGMycielskian

?IGMycielskian

147miq4vn83n5

IGMycielskian applies the Mycielski construction to an undirected graph on \(n\geq 2\) vertices to obtain a larger graph (the Mycielskian) on \(2 n+1\) vertices. If the graph has less than 2 vertices, then instead of applying the standard Mycielski construction, IGMycielskian simply adds one vertex and one edge.

If the original graph has chromatic number \(k\), its Mycielskian has chromatic number \(k+1\). The Mycielski construction preserves the triangle-free property of the graph.

g = CycleGraph[4]

13d5ug4uhl4dy

{IGChromaticNumber[g], IGTriangleFreeQ[g]}
{2, True}
mg = IGMycielskian[g]

1pavi4liqg0gj

{IGChromaticNumber[mg], IGTriangleFreeQ[mg]}
{3, True}

Construct triangle-free graphs with successively larger chromatic numbers.

NestList[IGMycielskian, IGEmptyGraph[], 5]

1u5k54io844p1

IGChromaticNumber /@ %
{0, 1, 2, 3, 4, 5}

IGSmoothen

?IGSmoothen

00ziamp831i3r

IGSmoothen suppresses all degree-2 vertices, thus obtaining the smallest topologically equivalent (i.e. homeomorphic) graph. See also IGHomeomorphicQ.

0btrz5s9fdvlo1pnu7b4kz67oc1igsqmge2n9mt

The vertex names are preserved, and the weights of merged edges are summed up. All other graph properties are discarded. In directed graphs, only those vertices are smoothened which have one incoming and one outgoing edge.

Available options:

The smallest topological equivalent of a path graph consists of two connected vertices.

0uuia7w715678

1ia38yn3hqqht

The result may contain self-loops. The smallest topological equivalent of a cycle graph is a single vertex with a self-loop.

IGSmoothen[CycleGraph[10]]

0x1vgt6rezeoi

The result may also contain multi-edges.

0oyonvv9ji1r4

1732udizjjs8y

If the input is directed, only those vertices are smoothed which have one incoming and one outgoing edge.

0hdhq7rhrys0t

1h5my0j05oz3b

Use DirectedEdges -> False to treat the input graph as undirected.

1jd8qv4oilyrb

19ewuym0lm0wm

The result is always a weighted graph. When contracting edges, their weights are added up. If the input graph was not weighted, all of its edge weights are considered to be 1. Thus, the graph distance of any two vertices in the result is always the same as it was in the input graph.

g = IGGiantComponent@RandomGraph[{100, 100}]

1dr3g9qs251em

tm = IGSmoothen[g]

0nm6c50z656zk

IGEdgeWeightedQ[tm]
True
IGDistanceMatrix[g, VertexList[tm], VertexList[tm]] == 
 IGDistanceMatrix[tm]
True

The result does not contain any degree-2 vertices, except possibly isolated vertices with self-loops.

Union@VertexDegree[tm]
{1, 3, 4, 5, 6}

The vertex coordinates, as well as any other graph properties are discarded.

g = IGMeshGraph@IGLatticeMesh["Hexagonal", {3, 3}]

1kpxlg54x69ne

IGSmoothen[g]

1wqb9xnhvgnm8

Vertex coordinates can be transferred to the new graph as follows:

IGSmoothen[g,
 VertexCoordinates -> {v_ :> 
    PropertyValue[{g, v}, VertexCoordinates]}]

162gns76bfbye

An alternative and faster method uses IGVertexMap and IGVertexAssociate:

IGSmoothen[g] // 
 IGVertexMap[IGVertexAssociate[GraphEmbedding][g], 
  VertexCoordinates -> VertexList]

162gns76bfbye

Create a tree in which every non-leaf node has a degree of at least 3.

IGSmoothen[IGTreeGame[100], GraphLayout -> "RadialEmbedding"]

117ak4sahkbyg

Let us compute the effective resistance of a resistor network by repeated smoothing (merger of resistors in series) and simplification (merger of resistors in parallel). Resistances are stored as edge weights. A zero-resistance input and output terminal is added to prevent the premature smoothing of these points.

0yutnipish2j9

Merge resistors in series …

reducedGrid = IGSmoothen[resistorGrid]

1jyrh5km69i92

… then merge resistors in parallel and check the resulting edge weights.

reducedGrid = 
 IGWeightedSimpleGraph[reducedGrid, 1/Total[1/{##}] &, 
  EdgeLabels -> "EdgeWeight"]

1lfuwxjyvebr7

Repeat until a single resistor remains.

reducedGrid = IGSmoothen[reducedGrid]

1eiutver1gky2

reducedGrid = 
 IGWeightedSimpleGraph[reducedGrid, 1/Total[1/{##}] &, 
  EdgeLabels -> "EdgeWeight"]

1bjqv0gjk3ymr

reducedGrid = IGSmoothen[reducedGrid, EdgeLabels -> "EdgeWeight"]

0rooz5r0sbiod

IGEdgeProp[EdgeWeight][reducedGrid]
{3.}

Structural properties

Centrality measures

Betweenness

?IGBetweenness

1n0zr6z4jfioa

?IGBetweennessEstimate

18eyw7irp8hbr

?IGEdgeBetweenness

0ozk2b33x1brr

?IGEdgeBetweennessEstimate

06tkjd4ic9not

Weighted graphs are supported by all betweenness functions in IGraph/M.

The betweenness of a vertex or edge is, roughly speaking, the number of shortest paths passing through it. More formally, the betweenness of vertex \(i\) is \(b_i=\sum _{i\neq s\neq t} \frac{g_{st}^{(i)}}{g_{st}}\), where \(g_{st}\) is the total number of shortest paths (geodesics) between vertices \(s\) and \(t\), and \(g_{st}^{(i)}\) is the number of shortest paths between vertices \(s\) and \(t\) that pass through \(i\).

Available options:

Available Method options for vertex betweenness calculations:

Compare the "Fast" and "Precise" methods:

g = GridGraph[{30, 30}];
Timing[Max@IGBetweenness[g, Method -> "Precise"]]
{0.220522, 18980.5}
Timing[Max@IGBetweenness[g, Method -> "Fast"]]
{0.031536, 18980.5}

For this large grid graph, the "Fast" method no longer gives accurate results:

g = GridGraph[{40, 40}];
Timing[Max@IGBetweenness[g, Method -> "Precise"]]
{0.803159, 45701.7}
Timing[Max@IGBetweenness[g, Method -> "Fast"]]
{0.090276, 78169.7}

Visualize the vertex and edge betweenness of a weighted geometrical graph, where weights represent Euclidean distances.

pts = RandomPoint[Disk[], 100];
IGMeshGraph[
  DelaunayMesh[pts],
  EdgeStyle -> Thick, VertexStyle -> EdgeForm[None]
  ] //
 IGVertexMap[
   ColorData["SolarColors"],
   VertexStyle -> Rescale@*IGBetweenness
   ] /*
  IGEdgeMap[
   ColorData["SolarColors"],
   EdgeStyle -> Rescale@*IGEdgeBetweenness
   ]

1bwr7ps7ruoj1

Compute the betweenness of a subset of vertices.

g = ExampleData[{"NetworkGraph", "DolphinSocialNetwork"}];
Take[VertexList[g], 5]
{"Beak", "Beescratch", "Bumper", "CCL", "Cross"}
IGBetweenness[g, %]
{34.9212, 390.384, 16.6032, 4.34405, 0.}

Visualize the betweenness of a periodic grid with slightly randomized edge weights.

n = 40;
IGSquareLattice[{n, n},
  "Periodic" -> True,
  VertexCoordinates -> Tuples[Range[n], {2}],
  EdgeWeight -> {_ :> RandomReal[{.99, 1.01}]},
  GraphStyle -> "BasicBlack",
  EdgeShapeFunction -> None,
  VertexSize -> 1
  ] // IGVertexMap[
  ColorData["BlueGreenYellow"],
  VertexStyle -> Rescale@*IGBetweenness
  ]

0073xg5g7rrhj

Possible issues:

Weighted betweenness calculations may be affected by numerical precision when non-integer weights are used. Betweenness computations count shortest paths, which means that the total weight of different paths must be compared for equality. Equality testing with floating point numbers is unreliable. This can be demonstrated on an example which is purposefully constructed to be problematic.

An unweighted grid graph has many shortest paths between the same pair of vertices.

g = GridGraph[{6, 6}];

Let us construct non-integer weights which can add up to (equal) integers in many different ways.

weights = 1/RandomInteger[{1, 5}, EdgeCount[g]];

Let us now associate weights with edges and order the edges in two different random ways. Betweenness should not depend on edge ordering, so graphs constructed from both should have the same betweenness values.

asc1 = Association@RandomSample@Thread[EdgeList[g] -> weights];
asc2 = Association@RandomSample@Thread[EdgeList[g] -> weights];
g1 = Graph[Keys[asc1], EdgeWeight -> Values[asc1]];
g2 = Graph[Keys[asc2], EdgeWeight -> Values[asc2]];
KeySort@AssociationThread[VertexList[g1], IGBetweenness[g1]] -
 KeySort@AssociationThread[VertexList[g2], IGBetweenness[g2]]
<|1 -> 0., 2 -> 0., 3 -> 0., 4 -> 0., 5 -> 0., 6 -> 0., 7 -> 0., 
8 -> 0., 9 -> 0., 10 -> -7.10543*10^-15, 11 -> 0., 12 -> 0., 
13 -> 0., 14 -> 0., 15 -> -2.84217*10^-14, 16 -> -1.42109*10^-14, 
17 -> 0., 18 -> 0., 19 -> 0., 20 -> 0., 21 -> -2.84217*10^-14, 
22 -> 0., 23 -> 0., 24 -> 0., 25 -> 0., 26 -> 0., 27 -> 0., 28 -> 0.,
 29 -> 0., 30 -> 0., 31 -> 0., 32 -> 0., 33 -> 0., 34 -> 0., 
35 -> 0., 36 -> 0.|>
Max@Abs[%]
2.84217*10^-14

Yet the results differ. This is because IGraph/M works with floating point numbers. Even when different sums of exact weights happen to be equal, floating point calculations will give slightly different results.

To obtain a reliable result, we must use integer weights. The weights in these example were inverses of {1, 2, 3, 4, 5}. Multiplying these by their least common multiple will always yield an integer.

LCM @@ {1, 2, 3, 4, 5}
60
asc1 = Association@RandomSample@Thread[EdgeList[g] -> 60 weights];
asc2 = Association@RandomSample@Thread[EdgeList[g] -> 60 weights];
g1 = Graph[Keys[asc1], EdgeWeight -> Values[asc1]];
g2 = Graph[Keys[asc2], EdgeWeight -> Values[asc2]];
KeySort@AssociationThread[VertexList[g1], IGBetweenness[g1]] -
 KeySort@AssociationThread[VertexList[g2], IGBetweenness[g2]]
<|1 -> 0., 2 -> 0., 3 -> 0., 4 -> 7.10543*10^-15, 5 -> 0., 6 -> 0., 
7 -> 0., 8 -> 0., 9 -> 7.10543*10^-15, 10 -> 7.10543*10^-15, 
11 -> 0., 12 -> 0., 13 -> 0., 14 -> 0., 15 -> 2.84217*10^-14, 
16 -> 4.26326*10^-14, 17 -> 0., 18 -> 0., 19 -> 0., 20 -> 0., 
21 -> 2.84217*10^-14, 22 -> 7.10543*10^-15, 23 -> 0., 24 -> 0., 
25 -> 0., 26 -> 0., 27 -> 0., 28 -> 0., 29 -> 0., 30 -> 0., 31 -> 0.,
 32 -> 0., 33 -> 0., 34 -> 0., 35 -> 0., 36 -> 0.|>
Chop@Max@Abs[%]
0

Now IGBetweenness gives the same result regardless of edge ordering.

Closeness

?IGCloseness

0bxrmz6a87uqh

?IGClosenessEstimate

1bcqfqh0gkw9n

The normalized closeness centrality of a vertex is the inverse average shortest path length to other vertices.

Weighted graphs are supported.

Available options:

igraph’s closeness calculation differs from Mathematica’s in that when there is no path connecting two vertices, the total number of vertices is used as their distance (a number larger than any other distance in an unweighted graph). Mathematica computes closeness separately within each connected component.

Visualize the closeness of nodes in a weighted geometrical graph where weights correspond to Euclidean distances.

pts = RandomPoint[Polygon@CirclePoints[3], 75];
IGVertexMap[
 ColorData["Rainbow"],
 VertexStyle -> Rescale@*IGCloseness,
 IGMeshGraph[DelaunayMesh[pts], GraphStyle -> "BasicBlack"]
 ]

1rvkleev0r7ce

Indeterminate is returned for a single-vertex graph.

IGCloseness@IGEmptyGraph[1]
{Indeterminate}

PageRank

?IGPageRank

11qrdqsizqg4a

?IGPersonalizedPageRank

0up7u861rz43t

Weighted graphs and multigraphs are supported.

The default damping factor is 0.85.

The following Method options are available:

Eigenvector centrality

?IGEigenvectorCentrality

0f0eozmelv0bo

Weighted graphs are supported.

The available options are:

Kleinberg’s hub and authority scores

?IGHubScore

08ik1ohc2ugtt

?IGAuthorityScore

1hc28h1i9qi3s

Weighted graphs are supported.

The available options are:

Burt’s constraint score

?IGConstraintScore

1q9zbn6q78jcx

Weighted graphs are supported.

Centralization

?IG*Centralization

1c3dwkzxci3yw

Centralization is computed from centrality values in a way equivalent to Total[Max[centralities] - centralities]. With the (default) option Normalized -> True, the result is normalized by dividing by the highest possible centralization score of any graph of the same directedness on the same number of vertices.

g = IGBarabasiAlbertGame[100, 2, DirectedEdges -> False];
IGBetweennessCentralization[g]
0.315526
IGClosenessCentralization[g]
0.366524
IGDegreeCentralization[g, SelfLoops -> False]
0.206761
IGEigenvectorCentralization[g]
0.868027

For most centrality types, the highest centralization is achieved by the StarGraph.

IGBetweennessCentralization@StarGraph[5]
1.

In the case of the degree centralization, the highest possible centralization score depends on whether self-loops are allowed. This is controlled by the SelfLoops option of IGDegreeCentralization. The default is SelfLoops -> True.

1lsypuheojjeo

{0.666667, 1., 1.}

Topological sorting and acyclic graphs

IGDirectedAcyclicGraphQ

?IGDirectedAcyclicGraphQ

1dggip0mrhew1

IGDirectedAcyclicGraphQ tests if a graph is directed and has no directed cycles.

IGDirectedAcyclicGraphQ /@ {IGShorthand["1->2->3->1"], 
  IGShorthand["1->2->3<-1"]}
{False, True}

IGDirectedAcyclicGraphQ returns True for graphs with no edges.

IGDirectedAcyclicGraphQ[IGEmptyGraph[3]]
True

IGTopologicalOrdering

?IGTopologicalOrdering

11cf9cd77zlw2

IGTopologicalOrdering is to the built-in TopologicalSort as Ordering is to Sort: it returns the permutation which sorts vertices in topological order. When vertices are ordered topologically, all directed edges point from earlier vertices to later ones.

Graphs must be acyclic for topological sorting to be possible.

1idfvlc3trn6f

IGDirectedAcyclicGraphQ[g]
True
p = IGTopologicalOrdering[g]
{5, 8, 9, 4, 6, 1, 2, 3, 10, 7}
VertexList[g][[p]]
{"E", "H", "I", "D", "F", "A", "B", "C", "J", "G"}

If the vertices are laid out from left to right in topological order, all edges will point from left to right.

Graph[g,
  EdgeShapeFunction -> 
   GraphElementData[{"CurvedEdge", "Curvature" -> 1.5}]
  ] // IGVertexMap[{#, 0} &, 
  VertexCoordinates -> IGTopologicalOrdering /* Ordering]

1uptuirdozzua

When the graph contains cycles, and a complete topological sort cannot be performed, only a partial result is returned.

IGTopologicalOrdering[IGShorthand["1->2->3->4->5, 5->3, 5->6"]]

0hidrrmmkporw

{1, 2}

IGFeedbackArcSet

?IGFeedbackArcSet

10itr1fh1h6vd

IGFeedbackArcSet[] returns a set of directed edges (also called arcs) the removal of which makes the graph acyclic.

With Method -> "IntegerProgramming", it finds an exact minimal feedback arc set through integer programming using the triangle inequality formulation. With Method -> "EadesLinSmyth", it finds a feedback arc set (not necessarily minimal) using the fast “GR” heuristic of Eades, Lin and Smyth (1993).

The following directed graph is not acyclic.

g = RandomGraph[{10, 20}, DirectedEdges -> True, 
  VertexLabels -> "Name"]

1dqvij0m42rzx

{AcyclicGraphQ[%], IGDirectedAcyclicGraphQ[%]}
{False, False}

Find a set of edges whose removal breaks all cycles.

IGFeedbackArcSet[g]
{2 \[DirectedEdge] 4, 2 \[DirectedEdge] 7, 8 \[DirectedEdge] 5, 
8 \[DirectedEdge] 6}
ag = EdgeDelete[g, %]

1duj4wu56amur

IGDirectedAcyclicGraphQ[ag]
True

Vertices of a directed acyclic graph can be sorted topologically. IGTopologicalOrdering returns a permutation that sorts them this way, and thus makes the graph’s adjacency matrix upper triangular.

perm = IGTopologicalOrdering[ag]
{5, 7, 3, 6, 10, 9, 4, 2, 1, 8}
With[{am = AdjacencyMatrix[ag]},
 ArrayPlot /@ {am, am[[perm, perm]]}
 ]

0ybcoduza6mnk

References

Chordal graphs

IGChordalQ

?IGChordalQ

1tnfvzcuxdyjt

A graph is chordal if each of its cycles of four or more nodes has a chord, i.e. an edge joining two non-adjacent vertices in the cycle. Equivalently, all chordless cycles in a chordal graph have at most 3 vertices.

Chordal graphs are also called rigid circuit graphs or triangulated graphs.

Grid graphs are not chordal because they have chordless 4 cycles.

g = GridGraph[{2, 3}, VertexLabels -> "Name"]

0il0tcwfr6ix1

IGChordalQ[g]
False

Adding chords to the 4 cycles makes them chordal.

EdgeAdd[g, {1 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5}]

02fvvra75iyqc

IGChordalQ[%]
True

IGChordalCompletion

?IGChordalCompletion

0diupk0id9t02

IGChordalCompletion computes a set of edges that, when added to a graph, make it chordal. The edge set returned is not usually minimal, i.e. some of the edges may not be necessary to create a chordal graph.

g = CycleGraph[5]

1m3ym4n1esovz

completion = IGChordalCompletion[g];
HighlightGraph[EdgeAdd[g, completion], completion]

16h0txf6s8c7k

IGMaximumCardinalitySearch

?IGMaximumCardinalitySearch

0n642rxyxnkzz

The maximum cardinality search algorithm visits the vertices of the graph in such an order so that every time the vertex with the most already visited neighbours is visited next. The visiting order is animated below:

1qno4d0jc2m4w

seq = InversePermutation@IGMaximumCardinalitySearch[g]
{7, 6, 2, 9, 8, 4, 5, 3, 10, 1}
Table[
  HighlightGraph[
   Graph[g, VertexLabels -> "Name"],
   Take[seq, -i]
   ],
  {i, 1, 10}
  ] // ListAnimate

1ner6pir6ykw0

Clustering coefficient

?IG*ClusteringCoefficient

0hy4ulbgax6bk

Clustering coefficients are measures of the degree to which vertices in a graph tend to cluster together. They are also referred to as transitivity, as they measure how often two vertices that are connected through a third one are also directly connected.

All clustering coefficient calculations in IGraph/M ignore edge directions.

IGGlobalClusteringCoefficient

?IGGlobalClusteringCoefficient

1tw615noghe0o

The clustering coefficient of an undirected graph is defined as

\[C=\frac{\text{number of closed ordered triplets}}{\text{number of connected ordered triplets}}\]

The available options are:

The following graph has 10 connected ordered triplets, namely {3, 1, 2}, {2, 1, 3}, {1, 2, 3}, {3, 2, 1}, {2, 3, 1}, {2, 3, 4}, {1, 3, 4}, {1, 3, 2}, {4, 3, 2}, {4, 3, 1}. Out of these, only 6 are closed: {1, 3, 2}, {1, 2, 3}, {2, 1, 3}, {2, 3, 1}, {3, 2, 1}, {3, 1, 2}. Thus the clustering coefficient is 6/10 = 0.6.

0rzgxkntda9v3

0.6

IGLocalClusteringCoefficient

?IGLocalClusteringCoefficient

1q7dim5lo3o3y

The local clustering coefficient of a vertex is defined as

\[C=\frac{\text{number of connected pairs of neighbours}}{\text{total number of pairs of neighbours}}\]

The available options are:

In the following graph, vertex 4 has only one neighbour. Thus its local clustering coefficient will be computed as either 0 or indeterminate depending on the setting for "ExcludeIsolates".

1scko1jvz9vx2

{1., 1., 0.333333, 0.}

1gd5nnhuxbpan

{1., 1., 0.333333, Indeterminate}

IGAverageLocalClusteringCoefficient

?IGAverageLocalClusteringCoefficient

0jt0yvxt21mzb

The available options are:

With "ExcludeIsolates" -> True, the local clustering coefficient of vertex 4 will be excluded from the calculation of the average.

0t198ki1hzyrx

{0.583333, 0.777778}

IGWeightedClusteringCoefficient

?IGWeightedClusteringCoefficient

0bulddv2x0zv5

IGWeightedClusteringCoefficient computes the weighted local clustering coefficient. This function expects a weighted graph as input.

The available options are:

References

Neighbour degrees

IGAverageNeighborDegree

?IGAverageNeighborDegree

0jl6o8kmv1w1d

IGAverageNeighborDegree computes the average of the degrees of each vertex’s neighbours. In weighted graphs, a weighted average is used:

\[k_{\text{nn},u}=\frac{1}{s_u}\sum _v w_{uv}k_v\]

\(k_{\text{nn},u}\) denotes the average neighbour degree of vertex \(u\), \(k_v\) is the degree of vertex \(v\), \(w_{uv}\) is the weighted adjacency matrix, and \(s_u=\sum _vw_{uv}\) is the strength of vertex \(u\).

IGAverageNeighborDegree is similar to MeanNeighborDegree, with a few differences: it can compute the measure for only a subset of vertices, the interpretation of degrees and neighbours can be controlled independently in directed graphs, and for vertices which have no neighbours it returns Indeterminate instead of 0.

Average neighbour degree in a star graph:

IGAverageNeighborDegree[StarGraph[4]]
{1., 3., 3., 3.}

Compute the result only for vertices 1 and 3:

IGAverageNeighborDegree[StarGraph[4], {1, 3}]
{1., 3.}

All computes the result for all vertices (the default):

IGAverageNeighborDegree[StarGraph[4], All]
{1., 3., 3., 3.}

When a vertex has no neighbours, Indeterminate is returned:

IGAverageNeighborDegree[IGShorthand["1,2-3"]]
{Indeterminate, 1., 1.}

In directed graphs, the out-degrees of out-neighbours are considered by default.

143017y4tuq5a

IGAverageNeighborDegree[g]
{1., 1., 1.}

Use in-degrees of in-neighbours instead:

IGAverageNeighborDegree[g, All, "In"]
{Indeterminate, 1., 1.}

Use the in-degrees of all neighbours:

IGAverageNeighborDegree[g, All, "In", "All"]
{2., 1.33333, 1.33333}

Compute a weighted neighbour degree average. The weights used in averaging are taken from the edge weights:

1qflxi9rahwby

{2.2, 1.85714, 3., 3., 3., 3.}

References

IGAverageDegreeConnectivity

?IGAverageDegreeConnectivity

14yjk700uzztr

IGAverageDegreeConnectivity computes the average neighbour degree as a function of the vertex degree. The \(i\)th element of the result is the average of the IGAverageNeighborDegree result for all vertices of degree \(i\).

g = RandomGraph[{30, 50}];
IGAverageDegreeConnectivity[g]
{3.75, 4., 4.5, 4.42857, 4.12, Indeterminate, 4.42857, 4.25}

An equivalent implementation of IGAverageDegreeConnectivity is:

Transpose[{VertexDegree[g], IGAverageNeighborDegree[g]}] //
  
  GroupBy[#, First -> Last, Mean] & //
 
 Lookup[#, Range@Max@VertexDegree[g], Indeterminate] &
{3.75, 4., 4.5, 4.42857, 4.12, Indeterminate, 4.42857, 4.25}

Compute the average degree connectivity curve for a scale free network:

ListPlot[
 IGAverageDegreeConnectivity@IGStaticPowerLawGame[1000, 2000, 2],
 FrameLabel -> {"degree", "average neighbour degree"},
 PlotTheme -> "Detailed"
 ]

1p6hrv7egfwtd

References

Shortest paths

The length of a path between two vertices is the number of edges the path consists of. Functions that use edge weights consider the path length to be the sum of edge weights along the path.

IGDistanceMatrix

?IGDistanceMatrix

14zw34dhe8z13

IGDistanceMatrix takes the following Method options:

The igraph C core may override explicit method settings when appropriate. For example, if the graph is not weighted, it always uses "Unweighted".

IGDistanceCounts

?IGDistanceCounts

0hxvk91s5e925

IGDistanceCounts[graph] counts all-pair unweighted shortest path lengths in the graph. 1t37cjspf4f3v counts unweighted shortest path lengths for paths starting at the given vertices.

For weighted path lengths, or to restrict the computation to both certain start and end vertex sets, use IGDistanceHistogram[].

Compute how the shortest path length distribution changes as we rewire a grid graph k times.

Table[
 ListPlot[
  Normalize[IGDistanceCounts@IGRewire[GridGraph[{50, 50}], k], 
   Total],
  Joined -> True, Filling -> Bottom, 
  PlotLabel -> StringTemplate["rewiring steps: ``"][k]
  ],
 {k, {0, 5, 10, 20, 50, 100}}
 ]

0eky7ez64an43

IGNeighborhoodSize

?IGNeighborhoodSize

0fn1o49lhj6lm

IGNeighborhoodSize returns the number of vertices reachable within a certain distance range from a given vertex, or from multiple given vertices.

Scale vertices proportionally to the number of their second order neighbours:

g = IGBarabasiAlbertGame[50, 2, DirectedEdges -> False];
IGVertexMap[# &, 
 VertexSize -> (Rescale@IGNeighborhoodSize[#, All, {2}] &), g]

0x60s3agtwj0j

IGDistanceHistogram

?IGDistanceHistogram

1d2dr7c7y10dy

IGDistanceHistogram[] computes the weighted shortest path length histogram between the specified start and end vertex sets. The start and end vertex sets do not need to be the same. Note that if the graph is undirected, path lengths between s and t will be double counted (from s -> t and t -> s) if s and t appear both in the starting and ending vertex sets.

IGDistanceHistogram[] is useful when the result of IGDistanceMatrix[] (or GraphDistanceMatrix[]) does not fit in memory.

IGAveragePathLength

?IGAveragePathLength

0c0jps79z3d7w

If the graph is unconnected, vertex pairs between which there is no path are excluded from the calculation. This is different from the behaviour of MeanGraphDistance[], which returns in this case.

IGGirth

?IGGirth

0nep3j142g1rp

IGGirth computes the girth of a graph, i.e. the length of its shortest cycle. IGGirth ignores multi-edges and self-loops. Edge directions and edge weights are also ignored.

1oorl4gspgnu5

3

If the graph has no cycles, 0 is returned.

IGGirth@IGShorthand["1-2"]
0

IGDiameter and IGFindDiameter

?IGDiameter

0yawigaqt7fb2

The diameter of a graph is the length of the longest shortest path between any two vertices.

The available options are:

0y1ificoqk0gm

2
?IGFindDiameter

1c5dv0sfr863w

0fdp6oph6z75s

{1, 2, 4}

1ms879tm1zi0g

HighlightGraph[g, PathGraph@IGFindDiameter[g],
 GraphHighlightStyle -> "DehighlightFade", PlotTheme -> "RoyalColor"
 ]

1rv0wvxy16i50

IGEccentricity

?IGEccentricity

0huyjuyakrwl6

The eccentricity of a vertex is the longest shortest path to any other vertex. IGEccentricity computes the unweighted eccentricity of each vertex within the connected component where it is contained.

IGEccentricity@CycleGraph[8]
{4, 4, 4, 4, 4, 4, 4, 4}

Connected components are considered separately.

IGEccentricity[IGDisjointUnion[{CycleGraph[3], CycleGraph[8]}]]
{1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4}

IGRadius

?IGRadius

12ppyy7ky4rn7

The radius of a graph is the smallest eccentricity of any of its vertices, i.e. the eccentricity of the graph center.

IGVoronoiCells

?IGVoronoiCells

1slscgwcvqzci

IGVoronoiCells[graph, centers] partitions a graph’s vertices into groups based on which given centre vertex they are the closest to. Edge weights are considered for the distance calculations.

Available options:

g = PathGraph[Range[5], VertexLabels -> "Name", VertexSize -> Medium]

0djykkfnqrahr

IGVoronoiCells[g, {2, 4}]
<|2 -> {1, 2, 3}, 4 -> {4, 5}|>
HighlightGraph[g, Values[%]]

0qeyfuult30hw

In the event of a tie, a vertex is added to the first qualifying cell. The tiebreaker function can be changed as below.

IGVoronoiCells[g, {2, 4}, "Tiebreaker" -> Last]
<|2 -> {1, 2}, 4 -> {3, 4, 5}|>
Table[IGVoronoiCells[g, {2, 4}, "Tiebreaker" -> RandomChoice], {5}]
{<|2 -> {1, 2}, 4 -> {3, 4, 5}|>, <|2 -> {1, 2, 3}, 
 4 -> {4, 5}|>, <|2 -> {1, 2}, 4 -> {3, 4, 5}|>, <|2 -> {1, 2, 3}, 
 4 -> {4, 5}|>, <|2 -> {1, 2}, 4 -> {3, 4, 5}|>}

Find Voronoi cells on a grid.

g = GridGraph[{10, 10}, VertexSize -> Medium, 
   GraphStyle -> "BasicBlack"];
centers = RandomSample[VertexList[g], 3];
HighlightGraph[g,
 Append[
  Subgraph[g, #] & /@ Values@IGVoronoiCells[g, centers],
  Style[centers, Black]
  ],
 GraphHighlightStyle -> "DehighlightHide"
 ]

1ivo18us04hci

Edge weights are interpreted as distances.

g = IGMeshGraph@DelaunayMesh@RandomPoint[Disk[], 200];
centers = RandomSample[VertexList[g], 3];
HighlightGraph[g,
 Append[
  Subgraph[g, #] & /@ Values@IGVoronoiCells[g, centers],
  Style[centers, Black]
  ],
 GraphHighlightStyle -> "DehighlightGray"
 ]

18c47trkd42js

Efficiency measures

IGGlobalEfficiency

?IGGlobalEfficiency

11gifmx34qrsy

IGGlobalEfficiency[graph] computes the global efficiency of a graph. The global efficiency is defined as the average inverse shortest path length between all pairs of vertices,

\[E_{\text{global}}=\frac{1}{V(V-1)}\sum _{u,v} \frac{1}{d_{uv}},\]

where \(d_{uv}\) is the graph distance from vertex \(u\) to vertex \(v\) and \(V\) is the number of vertices. When \(v\) is not reachable from \(u\), \(1\left/d_{uv}\right.\) is taken to be 0.

Available options:

Compute the global efficiency of a network …

g = ExampleData[{"NetworkGraph", "ProteinInteraction"}];
IGGlobalEfficiency[g]
0.0997348

… and that of its spanning tree.

IGGlobalEfficiency@IGSpanningTree[g]
0.00106384

References

IGLocalEfficiency

?IGLocalEfficiency

1m4nzgken3uwb

IGLocalEfficiency[graph] computes the local efficiency around each vertex of a graph. The local efficiency around a vertex \(u\) is defined as the average pairwise inverse shortest path length between the neighbours of \(u\) after excluding \(u\) itself from the graph,

\[E_{\text{local}}(u)=\frac{1}{k_u\left(k_u-1\right)}\sum _{v,w\in N(u)} \frac{1}{d_{vw}},\]

where \(k_u\) is the degree of vertex \(u\), \(N(u)\) denotes its neighbourhood and \(d_{vw}\) is the graph distance from vertex \(v\) to vertex \(w\). If \(u\) has less than two neighbours, \(E_{\text{local}}(u)\) is taken to be 0.

Available options:

Size the vertices of a graph according to the corresponding local efficiency

g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
IGVertexMap[1.5 # &, VertexSize -> IGLocalEfficiency, g]

0l6zhl7chaco3

Plot the local efficiency versus the local clustering coefficient.

ListPlot[
 Transpose[{IGLocalClusteringCoefficient[g], IGLocalEfficiency[g]}],
 PlotTheme -> "Detailed"
 ]

01acovuzvwvgr

Compute the local efficiency of a subset of vertices only.

g = RandomGraph[{10, 20}, DirectedEdges -> True];
IGLocalEfficiency[g, {1, 2, 3}]
{0.547222, 0.366667, 0.429167}

By default, both in- and out-neighbours are considered when determining the neighbourhoods of vertices. We can also consider only in-neighbours or only out-neighbours.

{IGLocalEfficiency[g, All, "All"],
 IGLocalEfficiency[g, All, "In"],
 IGLocalEfficiency[g, All, "Out"]}
{{0.547222, 0.366667, 0.429167, 0.284722, 0., 0.597222, 0.277778, 
 0.166667, 0.375, 0.569444}, {0., 0.25, 0.429167, 0., 0., 0.75, 0.5, 
 0.5, 0., 0.75}, {0.547222, 0.291667, 0., 1., 0., 0., 0.125, 0.5, 
 0.5, 0.}}

Ignore edge directions when computing shortest paths.

IGLocalEfficiency[g, DirectedEdges -> False]
{0.833333, 0.666667, 0.683333, 0.305556, 0., 0.833333, 0.638889, \
0.833333, 0.722222, 0.833333}

References

IGAverageLocalEfficiency

?IGAverageLocalEfficiency

0ubbunoa3ry0b

IGAverageLocalEfficiency[graph] computes the average local efficiency of a network. See IGLocalEfficiency for a definition of this graph measure.

Plot the decrease in average local efficiency during sequential edge removals.

g = RandomGraph[{30, 60}, DirectedEdges -> True];
ListPlot[
 Table[
  {k, IGAverageLocalEfficiency@
    Graph[VertexList[g], Take[EdgeList[g], k]]},
  {k, EdgeCount[g]}
  ],
 AxesLabel -> {"edge count", "local efficiency"}
 ]

0nbcm2efn053m

IGAverageLocalEfficiency simply gives the average of the values returned by IGLocalEfficiency.

{IGAverageLocalEfficiency[g], Mean@IGLocalEfficiency[g]}
{0.21824, 0.21824}

Use only the out-neighbourhood while computing the local efficiency.

IGAverageLocalEfficiency[g, "Out"]
0.171157

Bipartite graphs

?IGBipartite*

1d45n95yx5xhu

IGBipartiteQ

?IGBipartiteQ

0fgqsbqwf5pu8

Generate a graph and verify that it is bipartite.

g = IGBipartiteGameGNM[5, 5, 10, VertexLabels -> "Name"]

05lgagnhx95tp

IGBipartiteQ[g]
True

Verify that no edges run between two disjoint vertex subsets of the graph.

IGBipartiteQ[g, {{1, 2, 3}, {6, 7, 8}}]
True

IGBipartitePartitions

?IGBipartitePartitions

11xtts5gi80sv

Find a bipartite partitioning of a graph.

1r9rxhvtbv3p7

IGBipartitePartitions[g]
{{1, 2, 3, 4}, {5, 6, 7, 8}}

Ensure that the partitions are returned in such an order that the first one contains vertex 5.

IGBipartitePartitions[g, 5]
{{5, 6, 7, 8}, {1, 2, 3, 4}}

$Failed is returned for non-bipartite graphs.

IGBipartitePartitions[CompleteGraph[4]]

0e9jpbkzydy57

$Failed

We can use IGPartitionsToMembership or IGKVertexColoring[…, 2] to obtain a partition index for each vertex.

IGPartitionsToMembership[g]@IGBipartitePartitions[g]
{1, 1, 1, 1, 2, 2, 2, 2}
IGKVertexColoring[g, 2]
{{1, 1, 1, 1, 2, 2, 2, 2}}

IGBipartiteProjections

?IGBipartiteProjections

0719nj6kzysy7

The following bipartite graph described the relationship between diseases and genes.

g = ExampleData[{"NetworkGraph", "BipartiteDiseasomeNetwork"}]

1nvkdjzlajrhy

parts = Values@GroupBy[
    Thread[IGVertexProp["Type"][g] -> VertexList[g]],
    First -> Last
    ];

Construct a disease-disease and gene-gene network from it.

IGBipartiteProjections[g, parts]

1vbp99rw0kvi7

IGBipartiteIncidenceMatrix and IGBipartiteIncidenceGraph

?IGBipartiteIncidenceGraph

02docj8ijsowz

?IGBipartiteIncidenceMatrix

00jpjo4ph9hrv

Compute an incidence matrix. The default partitioning used by IGBipartiteIncidenceMatrix is the one returned by IGBipartitePartitions.

g = IGBipartiteGameGNM[5, 5, 10, VertexLabels -> "Name"]

17gzkg89scqei

bm = IGBipartiteIncidenceMatrix[g];
MatrixForm[bm, TableHeadings -> IGBipartitePartitions[g]]

0z4fgojxvz70c

Reconstruct a graph from an incidence matrix.

IGBipartiteIncidenceGraph[bm, VertexLabels -> "Name", 
 GraphLayout -> "BipartiteEmbedding"]

0sk5ejzmwbjn0

Compute an incidence matrix using a given partitioning / vertex ordering. It is allowed to pass only a subset of vertices.

IGBipartiteIncidenceMatrix[g, {{1, 2, 3}, {6, 7, 8}}]

0axn6daay2sm4

Reconstruct the bipartite graph while specifying vertex names.

IGBipartiteIncidenceGraph[{{a, b, c}, {d, e, f}}, %, 
 VertexLabels -> "Name"]

13krgri8mcq1e

Similarity measures

?IGBibliographicCoupling

16s2ibwtsnbl3

The bibliographic coupling of two vertices in a directed graph is the number of other vertices they both connect to. The bibliographic coupling matrix can also be obtained using IGZeroDiagonal[am.am\[Transpose]], where am is the adjacency matrix of the graph.

?IGCocitationCoupling

0ttzqm3c68l8q

The co-citation coupling of two vertices in a directed graph is the number of other vertices that connect to both of them. The co-citation coupling matrix can also be obtained using IGZeroDiagonal[am\[Transpose].am], where am is the adjacency matrix of the graph.

?IGDiceSimilarity

1ibea78drymma

The Dice similarity coefficient of two vertices is twice the number of common neighbours divided by the sum of the degrees of the vertices.

?IGJaccardSimilarity

1hi43o34pcpgm

The Jaccard similarity coefficient of two vertices is the number of common neighbours divided by the number of vertices that are neighbours of at least one of the two vertices being considered.

?IGInverseLogWeightedSimilarity

0r48yg0mafy4o

The inverse log-weighted similarity of two vertices is the number of their common neighbours, weighted by the inverse logarithm of their degrees. It is based on the assumption that two vertices should be considered more similar if they share a low-degree common neighbour, since high-degree common neighbours are more likely to appear even by pure chance.

Isolated vertices will have zero similarity to any other vertex. Self-similarities are not calculated.

References

Connectivity and graph components

IGConnectedQ and IGWeaklyConnectedQ

?IGConnectedQ

0k1ts4tuwu4bn

?IGWeaklyConnectedQ

1j7nrxj01ql9u

IGConnectedQ checks if the graph is (strongly) connected. It is equivalent to ConnectedGraphQ. IGWeaklyConnectedQ check if a directed graph is weakly connected. It is equivalent to WeaklyConnectedGraphQ. Both of these functions use the implementation from the core igraph library, and will always be consistent with it for edge cases such as the null graph.

This graph is connected.

0hk56i54mhqck

True

This directed graph is only weakly connected.

0l7081upznjtr

False

0kdafzqai3sdr

True

The null graph is considered connected by convention.

IGConnectedQ@IGEmptyGraph[0]
True

IGConnectedComponentSizes and IGWeaklyConnectedComponentSizes

?IGConnectedComponentSizes

19m7sqx96dxts

?IGWeaklyConnectedComponentSizes

1w28jneyxbc9r

IGWeaklyConnectedComponentsSizes and IGConnectedComponentSizes return the sizes of the graph’s weakly or strongly connected components in decreasing order.

In large graphs, these functions will be faster than the equivalent Length /@ ConnectedComponents[g].

The emergence of a giant component as the number of edges in a random graph increases.

Table[
  {m, First@IGConnectedComponentSizes@RandomGraph[{1000, m}]},
  {m, 5, 2000, 5}
  ] // ListPlot

1i6prdlrf23cw

The number of weakly and strongly connected components versus the number of edges in a random directed graph.

Table[
   With[{g = RandomGraph[{1000, m}, DirectedEdges -> True]},
    {{m, Length@IGWeaklyConnectedComponentSizes[g]}, {m, 
      Length@IGConnectedComponentSizes[g]}}
    ],
   {m, 5, 3000, 5}
   ] // Transpose // ListPlot

04v4b4na5x31i

Vertex separators

A vertex separator is a set of vertices whose removal disconnects the graph.

?IGMinimalSeparators

0bwju51zcapkg

?IGMinimumSeparators

158ng9upyarxg

?IGVertexSeparatorQ

0e248y07591dh

?IGMinimalVertexSeparatorQ

0q6hgwgisvi8j

g = ExampleData[{"NetworkGraph", "Friendship"}]

0mqwgmxuzo1a6

separators = IGMinimumSeparators[g]
{{"Anna", "Rose"}, {"Larry", "Rudy"}, {"Larry", "James"}, {"Rudy", 
 "Linda"}, {"Anna", "Nora"}, {"Anna", "Ben"}, {"Anna", 
 "Larry"}, {"Anna", "Linda"}, {"Anna", "James"}}

Removing any of these vertex sets will disconnect the graph:

VertexDelete[g, #] & /@ separators

0adr3qnlb3ert

IGVertexSeparatorQ[g, #] & /@ separators
{True, True, True, True, True, True, True, True, True}
IGMinimalVertexSeparatorQ[g, #] & /@ separators
{True, True, True, True, True, True, True, True, True}

Removing Anna, Nora and Larry also disconnects the graph, thus this vertex set is a separator:

IGVertexSeparatorQ[g, {"Anna", "Nora", "Larry"}]
True

But it is not minimal:

IGMinimalVertexSeparatorQ[g, {"Anna", "Nora", "Larry"}]
False

IGMinimumSeparators returns only those vertex separators which are of the smallest possible size in the graph. IGMinimalSeparators returns all separators which cannot be made smaller by removing a vertex from them. The former is a subset of the latter.

0k8kwt3shgrog

IGMinimalSeparators[g]
{{1, 6}, {0, 2}, {1, 3, 4}, {2, 5}, {3, 4, 6}, {0, 5}, {2, 6}, {1, 
 5}, {0, 3, 4}}
IGMinimumSeparators[g]
{{2, 5}, {1, 5}, {1, 6}, {0, 5}, {2, 6}, {0, 2}}
SubsetQ[%%, %]
True

IGEdgeConnectivity

?IGEdgeConnectivity

15chuc269p2zt

IGEdgeConnectivity ignores edge weights. To take edge weights into account, use IGMinimumCutValue instead.

Compute the edge connectivity of the dodecahedral graph.

IGEdgeConnectivity[GraphData["DodecahedralGraph"]]
3

The edge connectivity of the singleton graph is returned as 0.

IGEdgeConnectivity[IGEmptyGraph[1]]
0

IGVertexConnectivity

?IGVertexConnectivity

0ihim3x1jaocy

According to Steinitz’s theorem, the skeleton of every convex polyhedron is a 3-vertex-connected planar graph.

g = GraphData["DodecahedralGraph"]

0ae6wxawc635b

IGVertexConnectivity[g]
3

To find the specific vertex sets that disconnect the graph, use IGMinimumSeparators or IGMinimalSeparators.

IGMinimumSeparators[g]
{{14, 15, 16}, {5, 6, 13}, {7, 14, 19}, {8, 15, 20}, {2, 11, 19}, {2, 
 12, 20}, {3, 11, 16}, {4, 12, 16}, {10, 14, 17}, {9, 15, 18}, {5, 7,
  12}, {6, 8, 11}, {2, 17, 18}, {9, 13, 19}, {10, 13, 20}, {3, 5, 
 17}, {4, 6, 18}, {1, 3, 9}, {1, 4, 10}, {1, 7, 8}}

The vertex connectivity of the singleton graph is returned as 0.

IGVertexConnectivity[IGEmptyGraph[1]]
0

IGBiconnectedQ

?IGBiconnectedQ

17iqra3nil054

IGBiconnectedQ checks if a graph is biconnected. Edge directions are ignored.

027e3ubh2pm0u

False

Since IGBiconnectedComponents does not return any isolated vertices, Length@IGBiconnectedComponents[g] == 1 cannot be used to check if a graph is biconnected. Use IGBiconnectedQ instead.

1v04ejx2xkfvz

{{4, 3, 2, 1}}

The singleton graph is not considered to be biconnected, but the two-vertex complete graph is.

Table[IGBiconnectedQ@CompleteGraph[k], {k, 1, 2}]
{False, True}

IGBiconnectedComponents and IGBiconnectedEdgeComponents

?IGBiconnectedComponents

1qn0hmnfbarvf

?IGBiconnectedEdgeComponents

11043m3fdc11e

IGBiconnectedCompoments returns the vertices of the maximal biconnected components of the graph. IGBiconnectedEdgeComponents returns the edges of the components. Edge directions are ignored and isolated vertices are excluded.

IGBiconnectedComponents is equivalent to KVertexConnectedComponents[…, 2], except that isolated vertices are not returned as individual components.

The articulation vertices will be part of more than a single component, thus the biconnected components are not disjoint subsets of the vertex set.

0kxuvxndx3zjb

{{3, 2, 1}, {4, 1}}

However, each edge is part of precisely one biconnected components.

00jqvudjz1f52

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

Thus, visualizing biconnected components is best done by colouring the edges, not the vertices.

0e19n0vom8pfp

HighlightGraph[g, IGBiconnectedEdgeComponents[g], 
 GraphStyle -> "ThickEdge"]

0pdnjkdd4l5si

IGArticulationPoints

?IGArticulationPoints

0eeembe4j1i6m

IGArticulationPoints finds vertices whose removal increases the number of (weakly) connected components in the graph. Edge directions are ignored.

g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 4}, 
  DirectedEdges -> False, VertexLabels -> Automatic]

1iwumb8gfh5yj

IGArticulationPoints[g]
{4, 3}
VertexDelete[g, #] & /@ %

0983ft6ikyxc6

Articulation points are also size-1 separators.

IGMinimumSeparators[g]
{{4}, {3}}

Highlight the articulation points of a cactus graph.

1wm6p6rlfbvzm

HighlightGraph[g, IGArticulationPoints[g]]

1nhu7i73arxew

Compute the block-cut tree of a connected graph. The blocks are the biconnected components. Together with the articulation vertices they form a bipartite graph, specifically a tree.

RelationGraph[
 MemberQ,
 Join[IGBiconnectedComponents[g], IGArticulationPoints[g]],
 DirectedEdges -> False,
 GraphStyle -> "ClassicDiagram",
 VertexSize -> {3, 1}/7, VertexLabelStyle -> 8
 ]

173lz87krlfrx

IGBridges

?IGBridges

1nrknjia62zek

A bridge is an edge whose removal disconnects the graph (or increases the number of connected components if the graph was already disconnected). Edge directions are ignored.

IGShorthand["1-2-3-1-4-5-6-4"]

01twtrudomlx9

IGBridges[%]
{1 \[UndirectedEdge] 4}

Highlight bridges in a network.

g = ExampleData[{"NetworkGraph", "FlorentineFamilies"}];
HighlightGraph[g, IGBridges[g]]

0bidvk2a285o3

IGSourceVertexList and IGSinkVertexList

?IGSourceVertexList

1g3cja950q2qs

?IGSinkVertexList

061pykzblhllz

Find and highlight the source and sink vertices of a random acyclic graph.

g = DirectedGraph[RandomGraph[{10, 20}], "Acyclic", 
  VertexLabels -> "Name", VertexSize -> Large, EdgeStyle -> Gray]

12s3pbwwun13r

IGSourceVertexList[g]
{1}
IGSinkVertexList[g]
{4, 8, 9, 10}
HighlightGraph[g, {IGSourceVertexList[g], IGSinkVertexList[g]}]

10ad11de5lrfu

Undirected graphs have neither source nor sink vertices because undirected edges are counted as bidirectional.

103bw6uf3sf1o

{}

The exception is isolated vertices, which are counted both as sources and sinks.

Through[{IGSourceVertexList, IGSinkVertexList}@Graph[{1, 2}, {}]]
{{1, 2}, {1, 2}}

These are merely convenience functions that can be implemented straightforwardly as

Pick[VertexList[g], VertexOutDegree[g], 0]
{4, 8, 9, 10}

IGGiantComponent

?IGGiantComponent

12hizuzby9dm8

IGGiantComponent is a convenience function that returns the largest weakly connected component of graph. If there are multiple components of largest size, there is no guarantee about which one would be returned. If this is a concern, use WeaklyConnectedComponents or WeaklyConnectedGraphComponents instead.

g = RandomGraph[{200, 200}];
HighlightGraph[
  g,
  IGGiantComponent[g]
  ] // IGLayoutFruchtermanReingold

10r4luzqx7gmn

IGGiantComponent takes all standard graph options.

IGGiantComponent[g, GraphStyle -> "BasicGreen", 
 GraphLayout -> "SpringEmbedding"]

1oungi68w2hz7

Size of the giant component of a random subgraph of a grid graph.

g = IGSquareLattice[{30, 30}, "Periodic" -> True];
Table[
  {k, VertexCount@
    IGGiantComponent@Subgraph[g, RandomSample[VertexList[g], k]]},
  {k, 1, VertexCount[g], 1}
  ] // ListPlot

0ew0pu4p6vbqe

Trees

IGTreeQ

?IGTreeQ

1juktgyhpzu0c

IGTreeQ checks if a graph is a tree. An undirected tree is a connected graph with no cycles. A directed tree is similar, with its edges oriented either away from a root vertex (out-tree or arborescence) or towards a root vertex (in-tree or anti-arborescence).

0h1ug6x0an8i3

True

1feptu5yar2nk

False

By convention, the null graph is not a tree.

IGTreeQ[IGEmptyGraph[0]]
False

This is an out-tree.

0cuhds3ir29ft

True

It is not also an in-tree.

1930x41m4eil9

False

It becomes an in-tree if we reverse its edges.

15gxah41rqz2o

True

This graph is neither an out-tree nor an in-tree.

0z9w3uyujlbmz

False

However, it becomes a tree if we ignore edge directions.

0fm88rw1al3wn

True

IGForestQ

?IGForestQ

03ggdbvhb2y05

IGForestQ is a convenience function that tests if all connected components of a graph are trees.

This graph is not a tree, but it is a forest.

13w2nmk423025

{False, True}

By convention, the null graph is not a tree, but it is a forest.

{IGTreeQ[IGEmptyGraph[0]], IGForestQ[IGEmptyGraph[0]]}
{False, True}

Use the second argument to test for forests of out-trees or in-trees. By default, directed graphs are checked to be out-forests.

g = IGShorthand["1->2<-3, 4<-5->6"]

05e74p2plnphz

{IGForestQ[g], IGForestQ[g, "Out"], IGForestQ[g, "In"], 
 IGForestQ[g, "All"]}
{False, False, False, True}

IGStrahlerNumber

?IGStrahlerNumber

1jbid8vpzkcmq

IGStrahlerNumber computes the Horton–Strahler index of each vertex in a rooted tree. The tree must be directed—this is how the root is encoded. The Horton–Strahler index of the tree itself is the index of the root, i.e. the largest returned index. This measure is also called stream order, as it was originally used to characterize river networks.

tree = IGTreeGame[30, DirectedEdges -> True, 
  GraphLayout -> "LayeredDigraphEmbedding"]

0aic59y8mrapt

IGVertexMap[# &, VertexLabels -> IGStrahlerNumber, tree]

1p1nu2w6ou8zp

To get the Horton–Strahler number of the tree, find the maximal element.

Max@IGStrahlerNumber[tree]
15

IGStrahlerNumber requires a directed (i.e. rooted) tree as input.

1mwvamgwtorxr

0y3hdmp5y2par

$Failed

Orient undirected trees, effectively specifying a root vertex, before passing them to IGStrahlerNumber.

0jqpmyp11j0ig

{5, 4, 3, 1, 2, 2, 1, 1, 1, 1}

IGTreelikeComponents

?IGTreelikeComponents

1fllapdcxvl2m

IGTreelikeComponents finds the tree-like components of an undirected graph by repeatedly identifying and removing degree-1 vertices. Vertices in the tree-like components are not part of any undirected cycle, nor are they on a path connecting vertices that belong to a cycle.

g = RandomGraph[{100, 100}];
HighlightGraph[
  g,
  IGTreelikeComponents[g]
  ] // IGLayoutFruchtermanReingold

09jdb6b8ke58y

Highlight both the edges and vertices of tree-like components.

g = IGGiantComponent@RandomGraph[{50, 50}];
HighlightGraph[
 g,
 Join[
  Union @@ (IncidenceList[g, #] &) /@ IGTreelikeComponents[g],
  IGTreelikeComponents[g]
  ]
 ]

1xow7bs5hm7c5

IGLayoutFruchtermanReingold[%]

1cyamj7fer7sw

Remove tree-like components.

VertexDelete[g, IGTreelikeComponents[g]]

0426bex449fcq

Vertices incident to multi-edges or loop-edges are not part of tree-like components.

0pmfg47jp0vl8

{}

IGFromPrufer

?IGFromPrufer

1q7ctqyzz8agz

IGToPrufer

?IGToPrufer

0h8jm0t8mbxta

Spanning trees

IGSpanningTree

?IGSpanningTree

10vvywyrqaejw

IGSpanningTree[RandomGraph[{8, 20}], GraphStyle -> "DiagramGold"]

1j153037qhrse

Find the shortest set of paths connecting a set of points in the plane:

pts = RandomReal[1, {10, 2}];
g = IGMeshGraph@DelaunayMesh[pts];
tree = IGSpanningTree[g, VertexCoordinates -> pts]

0sl7n7tnv9qdc

The edge weights are preserved in the result.

IGEdgeWeightedQ[tree]
True

Compute the total path length.

Total@IGEdgeProp[EdgeWeight][tree]
2.09924

Find a maximum spanning tree by negating the weights before running the algorithm.

IGSpanningTree[IGEdgeMap[Minus, EdgeWeight, g], 
 VertexCoordinates -> pts]

1af3ve8fiz9wc

IGRandomSpanningTree

?IGRandomSpanningTree

1a50uap706tuz

IGRandomSpanningTree samples the spanning trees (or forests) of a graph uniformly by performing a loop-erased random walk. Edge directions are ignored.

If a spanning forest of the entire graph is requested using IGRandomSpanningTree[g], then the vertex names and ordering are preserved. If a spanning tree of only a single component is requested using IGRandomSpanningTree[{g, v}], then this is not the case.

Highlight a few random spanning trees of the Petersen graph.

g = PetersenGraph[];
HighlightGraph[g, #, GraphHighlightStyle -> "Thick"] & /@ 
 IGRandomSpanningTree[g, 9]

0ykl1e7shwbdp

If the input is a multi-graph, each edge will be considered separately for the purpose of spanning tree calculations. Thus the following graph has not 3, but 5 different spanning trees. Two pairs of these are indistinguishable based on their adjacency matrix due to the indistinguishability of the two parallel 1 \[UndirectedEdge] 2 edges. However, since all 5 spanning trees are generated with equal probability, two of the 3 adjacency matrices will appear twice as frequently as the third one.

g = IGShorthand["1-2-3-1,1-2", MultiEdges -> True, ImageSize -> Small]

0a1v1c1dilqm0

IGRandomSpanningTree[g, 10000] // CountsBy[AdjacencyMatrix] // 
  KeySort // KeyMap[MatrixForm]

1ano2ckygkd11

Edge directions are ignored for the purpose of spanning tree calculation. Thus the result may not be an out-tree.

IGRandomSpanningTree@WheelGraph[11, DirectedEdges -> True]

1wvkzyyu3jj6q

Create mazes by taking random spanning trees of grid graphs.

g = GridGraph[{10, 10}, GraphStyle -> "Web"];
HighlightGraph[g, IGRandomSpanningTree[g], 
 GraphHighlightStyle -> "DehighlightHide"]

19djmjr9mpbnp

g = GridGraph[{6, 6, 6}, VertexCoordinates -> Tuples[Range[6], {3}]];
HighlightGraph[g, IGRandomSpanningTree[g], 
 GraphHighlightStyle -> "DehighlightHide"]

1jil9pl2a8viy

Generate a random spanning tree of the component containing vertex 8.

0jw1lj1pdwft3

0acxnxy9bubwy

IGSpanningTreeCount

?IGSpanningTreeCount

07n2o0nzvetf8

IGSpanningTreeCount computes the number of spanning trees of a graph using Kirchhoff’s theorem. Multigraphs and directed graphs are supported.

0pldx1b3gsh9e

3

The number of spanning trees of a directed graph, rooted in any vertex.

03md2fhx58uhr

3

The number of spanning trees rooted in vertex 1.

0w9h74uwttdcm

1
IGSpanningTreeCount[PetersenGraph[]]
2000

IGSpanningTreeCount works on large graphs.

g = HypercubeGraph[6]

0uwr5zz4bv4wm

IGSpanningTreeCount[g]
1657509127047778993870601546036901052416000000

Edge multiplicities are taken into account. Thus the following graph has not 3, but 5 different spanning trees.

1rel2ve4zj3zh

5

Dominance

In a directed graph, a vertex \(d\) is said to dominate a vertex \(v\) if every path from the root to \(v\) passes through \(d\). We say that \(d\) is an immediate dominator of \(v\) if it does not dominate any other dominator of \(v\).

A dominator tree of a graph consists of the same vertices as the graph, and the children of a vertex are those other vertices which it immediately dominates.

IGDominatorTree

?IGDominatorTree

1imi96eqp1txw

Find the dominator tree of a directed graph.

1u0nzblvgb6ed

IGDominatorTree[g, "a", GraphStyle -> "VintageDiagram"]

1vk0betd3zans

Vertices that cannot be reached from the specified root are left isolated in the returned graph.

IGDominatorTree[g, "b", GraphStyle -> "VintageDiagram"]

184ovo94o2c6j

IGDominatorTree accepts all standard Graph options.

1n7fc0rpvpxkg

07rqa02bnee1r

IGImmediateDominators

?IGImmediateDominators

0c48gimackb73

Directly find the immediate dominators of vertices in a graph.

023oenwaqxhbb

<|"b" -> "a", "c" -> "b", "d" -> "a", "e" -> "a", "f" -> "e"|>

The immediate dominator of a vertex is its parent in the dominator tree.

tree = IGDominatorTree[g, "a", VertexLabels -> Automatic]

1eicnk7wbpmss

IGAdjacencyList[tree, "In"]
<|"a" -> {}, "b" -> {"a"}, "c" -> {"b"}, "d" -> {"a"}, "e" -> {"a"}, 
"f" -> {"e"}|>

Neither the root, nor vertices unreachable from the root are included in the keys of the returned association.

IGImmediateDominators[g, "b"]
<|"c" -> "b", "d" -> "c"|>

\(k\)-cores

?IGCoreness

0t71dq2mb2anq

A \(k\)-core of a graph is a maximal subgraph in which each vertex has degree at least \(k\). The coreness of a vertex is the highest order of \(k\)-cores that contain it.

0o76w931ib7te

IGCoreness[g]
{3, 3, 3, 3, 2, 2, 2, 2}
{KCoreComponents[g, 2], KCoreComponents[g, 3]}
{{{1, 2, 3, 4, 6, 7, 8, 5}}, {{1, 2, 3, 4}}}

By default, edge directions are ignored, and multi-edges are considered.

1wghqwgmbpqov

IGCoreness[g]
{4, 4, 4, 3}

Use the second argument to consider only in- or out-degrees.

IGCoreness[g, "In"]
{2, 2, 2, 1}
IGCoreness[g, "Out"]
{2, 2, 2, 2}

Matchings

IGMaximumMatching

?IGMaximumMatching

1ovi8gem7ncby

A matching of a graph is also known as an independent edge set.

IGMaximumMatching ignores edge directions and edge weights.

g = RandomGraph[{10, 20}];
IGMaximumMatching[g]
{9 \[UndirectedEdge] 10, 7 \[UndirectedEdge] 8, 5 \[UndirectedEdge] 6,
 3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 2}
HighlightGraph[g, IGMaximumMatching[g], 
 GraphHighlightStyle -> "Thick"]

0nlu04byk3loy

IGMatchingNumber

?IGMatchingNumber

1nch38rhtmuj6

The matching number of a graph is the size of its maximum matchings.

Graph traversal

IGUnfoldTree

?IGUnfoldTree

0x1cu966ekxh9

IGUnfoldTree creates a tree based on the breadth-first traversal of a graph. Each time a graph vertex is found, a new tree vertex is created.

Available options:

1ik0e32mnaxmj

0jjn6hakbd2nt

The original vertex that generates a tree node is stored in the "OriginalVertex" property.

IGVertexProp["OriginalVertex"][tree]
{1, 2, 3, 4, 6, 7, 8, 5, 3, 4, 4, 8}

We can label the tree nodes with the name of the original vertex either using pattern matching in VertexLabels along with PropertyValue

IGLayoutReingoldTilford[
 tree,
 "RootVertices" -> {1}, 
 VertexLabels -> (v_ :> PropertyValue[{tree, v}, "OriginalVertex"])
 ]

1j1qpy3cc6k5t

… or using IGVertexMap.

IGLayoutReingoldTilford[tree, "RootVertices" -> {1}] // 
 IGVertexMap[# &, VertexLabels -> IGVertexProp["OriginalVertex"]]

1j1qpy3cc6k5t

In directed graphs, the search is done along edge directions. It may be necessary to give multiple starting roots to fully unfold a weakly connected (or unconnected) graph.

IGUnfoldTree[Graph[{1 -> 2, 2 -> 3}], {2, 1}] // 
 IGVertexMap[# &, VertexLabels -> IGVertexProp["OriginalVertex"]]

096drc3cs52ox

Use DirectedEdges -> False to ignore edge directions during the search. Edge directions are still preserved in the result.

IGUnfoldTree[Graph[{1 -> 2, 2 -> 3}], {2}, DirectedEdges -> False] // 
 IGVertexMap[# &, VertexLabels -> IGVertexProp["OriginalVertex"]]

01aizrb2igr5y

Other structural properties

IGNullGraphQ

?IGNullGraphQ

124hjw6mclwf4

IGNullGraphQ returns True only for the null graph, i.e. the graph that has no vertices.

IGNullGraphQ[IGEmptyGraph[]]
True

For graphs that have vertices, but no edges, it returns False.

IGNullGraphQ[IGEmptyGraph[5]]
False

In contrast, the built-in EmptyGraphQ tests if there are no edges:

EmptyGraphQ[IGEmptyGraph[5]]
True

IGCompleteQ

?IGCompleteQ

1hb6xd7cvqzre

IGCompleteQ tests if a graph is complete, i.e. if all pairs of vertices are connected.

IGCompleteQ@IGCompleteGraph[10]
True
IGCompleteQ@IGCompleteGraph[5, DirectedEdges -> True]
True

IGCompleteQ ignores self-loops and multi-edges.

0nwejuk47tpzx

True

Check if each connected component of a graph is a clique.

g = GraphData[{8, 911}]

1wdbgslnqhdgo

AllTrue[ConnectedGraphComponents[g], IGCompleteQ]
True

The null graph is considered complete.

IGCompleteQ@IGEmptyGraph[]
True

IGCactusQ

?IGCactusQ

0ttfxppa8zs81

IGCactusQ tests if a graph is a cactus. A cactus graph is a connected undirected graph in which any two simple cycles share at most one vertex. Equivalently, a cactus is a connected graph in which every edge belongs to at most one simple cycle.

1oih649f8plnc

True
IGCactusQ[GridGraph[{2, 3}]]
False

IGCactusQ supports multigraphs and ignores self-loops.

0fxqpfja3ozrb

{True, False}

The null graph is not considered to be a cactus, but the singleton graph is.

IGCactusQ /@ {IGEmptyGraph[0], IGEmptyGraph[1]}
{False, True}

Currently, IGCactusQ does not support directed graphs.

IGCactusQ[Graph[{1 -> 2}]]

0ybt6xr4re8vi

$Failed

Motifs and subgraphs

Motifs

IGraph/M’s motif-related functions count the number of times each possible connectivity pattern of \(k\) vertices (i.e. induced subgraph of size \(k\)) occurs in a graph. The patterns are called motifs. As of IGraph/M 0.4, only size 3 and 4 motifs are supported, and only (weakly) connected subgraphs are considered.

To count larger induced subgraphs, see IGLADSubisomorphismCount. To identify where a subgraph occurs, see IGLADFindSubisomorphisms.

To count non-connected size-3 subgraphs, use IGTriadCensus.

igraph’s motif functions use the RAND-ESU algorithm, which is able to uniformly sample a random subset of motifs (connected subgraphs), and can thus estimate motif counts even in very large graphs. See the description of IGMotifs for an example.

References

IGMotifs

?IGMotifs

1uk4ka6zxc4fx

IGMotifs counts how many times each motif (i.e. induced subgraph) of the given size occurs in the graph. For subgraphs that are not weakly connected, Indeterminate is returned.

Available options are:

Motifs are returned by their IGIsoclass, i.e. the same order as listed in IGData.

mot3 = Graph[#, ImageSize -> 36, VertexSize -> 0.1] & /@ 
  IGData[{"AllDirectedGraphs", 3}]

03t2ehdjctqgy

Let us count size-3 motifs in the following graph, and summarize them a table. For non-weakly-connected subgraphs, Indeterminate is returned.

g = RandomGraph[{10, 40}, DirectedEdges -> True]

1p4u5nvnnzqnk

Grid[{mot3, IGMotifs[g, 3]}\[Transpose], Frame -> All]

0c43ryv6ui666

Empty graphs are treated as undirected by default. To treat them as directed, use DirectedEdges -> True. The result will be different as the number of non-isomorphic graphs on \(k\) vertices is not the same in the directed and undirected cases.

IGMotifs[IGEmptyGraph[5], 3, DirectedEdges -> #] & /@ {Automatic, 
  True, False}
{{Indeterminate, Indeterminate, 0, 0}, {Indeterminate, Indeterminate, 
 0, Indeterminate, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
 0}, {Indeterminate, Indeterminate, 0, 0}}

Example: metabolic network

Let us find the size-4 motifs that stand out in the E. coli metabolic network by comparing the motif counts to that of a rewired graph:

g = ExampleData[{"NetworkGraph", "MetabolicNetworkEscherichiaColi"}];
rg = IGRewire[g, 50000];

1g4l01zj13c7g

{Indeterminate, Indeterminate, Indeterminate, 1.3876, Indeterminate, \
Indeterminate, Indeterminate, 1.39018, 0.326385, Indeterminate, \
Indeterminate, Indeterminate, 0.602171, 0.648379, 0., Indeterminate, \
0.0130276, 0., 0., 4.94656, 0., 0., Indeterminate, Indeterminate, \
1.35607, 0.321909, 0.136086, Indeterminate, Indeterminate, 0.679966, \
0., 0.0147949, 0., Indeterminate, Indeterminate, 0., 0., 0., 0., \
Indeterminate, 0.223818, 0.740163, 0., 0.23653, 0., 0.232967, \
0.0427742, 0., 0., 0., 0., 0., 1.4501, 0., 0.0584416, 0., 0., 0., 0., \
0., 0., 0., Indeterminate, 0., 0., 0., 31.6166, 0., 0.168168, 0., 0., \
0., 0., 0.210526, 0., 0., 1.30323, 0., 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0., 0., 0., 0., 0., 0.312473, 0.105382, 1.0263, 0., \
0.0166665, 0., 0.265449, 0., 0.0360626, 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0.496183, 0., 0.205128, 0., 0., 0., 0., 0., 0., 0., \
Indeterminate, 0.431452, 0., 0., 0., 1.95238, 0., 0., 43.2243, 0., \
0.512035, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., \
2.10526, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.166667, \
0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0., 0., 0., 0., 0., 0., 0., Indeterminate, 0., Indeterminate, \
0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}
largeRatios = Select[ratios, # > 5 &]
{31.6166, 43.2243}

There are two motifs that are more than 30 times more common in the metabolic network than in the rewired graph.

Extract[IGData[{"AllDirectedGraphs", 4}], 
   FirstPosition[ratios, #]] & /@ largeRatios

1l4mlpehatnid

The Davidson–Harel algorithm attempts to reduce edge crossings and can draw these subgraphs in a clearer way:

IGLayoutDavidsonHarel /@ %

1c6eavli5aw7v

Estimating motif counts in large graphs

IGMotifs uses the RAND-ESU algorithm which can uniformly sample a random subset of motifs, and thus estimate motif counts even in very large graphs. To enable random sampling, set a cutoff probability 1vfttme7v6jau for stopping the search at each level of the ESU tree. The length of the cutoff probability vector, n, must be the same as the motif size. The number of sampled motifs is, on average, a fraction 1n37wvvl1nx7z of the total number.

bigG = ExampleData[{"NetworkGraph", "WorldWideWeb"}];
{VertexCount[bigG], EdgeCount[bigG]}
{325729, 1497134}

Sample a fraction \(0.1^3=0.001\) of all motifs.

IGMotifs[bigG, 3, 1 - 0.1 {1, 1, 1}] // AbsoluteTiming
{0.649749, {Indeterminate, Indeterminate, 122935, Indeterminate, 1295,
  3423, 50000, 373, 275, 982, 5131, 4, 37, 505, 94, 7025}}

Sample 12.5% of motifs, i.e. a fraction of \(0.5^3\).

IGMotifs[bigG, 3, 1 - 0.5 {1, 1, 1}] // AbsoluteTiming
{13.6651, {Indeterminate, Indeterminate, 31438059, Indeterminate, 
 379526, 633115, 7040753, 62382, 40739, 230814, 704867, 2335, 5100, 
 158393, 13956, 801974}}

IGMotifsVertexParticipation

?IGMotifsVertexParticipation

1rh6o4og1209p

IGMotifsVertexParticipation counts how many times each vertex participates in each motif. For each vertex, the result is returned in the same format as with IGMotifs.

Available options are:

Count how many times each vertex appears in each 3-motif in a directed graph.

08v121ngogwcx

mot = IGMotifsVertexParticipation[g, 3]
<|"A" -> {Indeterminate, Indeterminate, 0, Indeterminate, 2, 0, 0, 2, 
  1, 1, 0, 2, 0, 0, 0, 0}, 
"B" -> {Indeterminate, Indeterminate, 0, Indeterminate, 1, 1, 0, 3, 
  0, 2, 0, 1, 1, 1, 0, 0}, 
"C" -> {Indeterminate, Indeterminate, 1, Indeterminate, 1, 1, 0, 0, 
  0, 2, 0, 0, 0, 1, 0, 0}, 
"D" -> {Indeterminate, Indeterminate, 0, Indeterminate, 2, 1, 0, 0, 
  1, 1, 0, 1, 1, 0, 0, 0}, 
"E" -> {Indeterminate, Indeterminate, 1, Indeterminate, 0, 0, 0, 2, 
  1, 2, 0, 1, 1, 0, 0, 0}, 
"F" -> {Indeterminate, Indeterminate, 1, Indeterminate, 3, 0, 0, 2, 
  0, 1, 0, 1, 0, 1, 0, 0}|>

The sum of the participation counts in 3-motifs is 3 times the total motif counts of the graph.

Total[mot] === 3 IGMotifs[g, 3]
True

IGMotifsTotalCount and IGMotifsTotalCountEstimate

?IGMotifsTotalCount

0j038lsr396dq

?IGMotifsTotalCountEstimate

0kvdk53fc65ox

IGMotifsTotalCount[graph, motifSize] counts the number of weakly connected subgraphs of the given size in a graph.

IGMotifsTotalCountEstimate[graph, motifSize, sampleSize] estimates the total number of motifs by taking a random subset of vertices of the specified size, and counting motifs in which these vertices participate. The total number is estimated as motifCount*vertexCount/sampleSize. IGMotifsTotalCountEstimate[graph, motifSize, vertices] uses the specified vertices as the sample.

Let us create a graph.

g = RandomGraph[{20, 50}];

The number of size-4 subgraphs it has is:

Binomial[VertexCount[g], 4]
4845

However, only a small fraction of these is connected:

IGMotifsTotalCount[g, 4]
760

IGMotifsTotalCount is effectively equivalent to (but much faster than) the following:

Count[Subsets[VertexList[g], {4}], 
 subset_ /; WeaklyConnectedGraphQ@Subgraph[g, subset]]
760

Estimate the count of connected subgraphs by subsampling: at each level of the ESU tree, continue only with probability 0.9.

IGMotifsTotalCount[g, 4, 1 - 0.9 {1, 1, 1, 1}]/0.9^4
431.337

Estimate the count of connected subgraphs by considering a random subset of 15 vertices (out of a total of 20).

IGMotifsTotalCountEstimate[g, 4, 15]
624

Use the first 15 vertices tot estimate the count.

IGMotifsTotalCountEstimate[g, 4, Range[15]]
1013

Triad and dyad census

?IGTriadCensus

1mx0wk9ttxpjf

?IGDyadCensus

16w2jxliquvr7

See IGData["MANTriadLabels"] for the mapping between MAN labels and graphs.

IGTriadCensus[g] does not return triad counts in the same order as IGMotifs[g, 3], i.e. ordered according to the triads’ IGIsoclass[]. To get the result ordered by isoclass, use

Lookup[IGTriadCensus[g], Keys@IGData["MANTriadLabels"]]

IGData["MANTriadLabels"] are ordered according to isoclass.

Finding triangles

IGTriangles

?IGTriangles

1erudu13mzjbw

Highlight all triangles in a graph.

g = RandomGraph[{8, 16}, VertexSize -> Large];
HighlightGraph[g, Subgraph[g, #], ImageSize -> Tiny, 
   GraphHighlightStyle -> "Thick"] & /@ IGTriangles[g]

060nb2czrlzkg

IGAdjacenctTriangleCount

?IGAdjacentTriangleCount

1xo1dfsmcnvzf

Label a graph’s vertices based on the number of adjacent triangles.

RandomGraph[{8, 16}, VertexSize -> Large] // 
 IGVertexMap[Placed[#, Center] &, 
  VertexLabels -> IGAdjacentTriangleCount]

18rzjs413ql0c

IGTriangleFreeQ

Triangle-free graphs do not have any fully connected subgraphs of size 3. Equivalently, they do not have any cliques (other than 2-cliques, which are edges).

?IGTriangleFreeQ

1igrajpp5vu4h

Mycielski graphs are triangle-free.

IGTriangleFreeQ@GraphData[{"Mycielski", 10}]
True

Isomorphism and the automorphism group

igraph implements three isomorphism testing algorithms: BLISS, VF2 and LAD. These support slightly different functionality.

Naming: Most of IGraph/M’s isomorphism related functions include the name of the algorithm as a prefix, e.g. IGBlissIsomorphicQ. Functions named as …GetIsomorphism will find a single isomorphism. Functions named as …FindIsomorphisms can find multiple isomorphisms. Both return a result in a format compatible with the built-in FindGraphIsomorphism.

Additionally, IGIsomorphicQ[] and IGSubisomorphicQ[] try to select the best algorithm for the given graphs. For graphs without multi-edges, they use igraph’s default algorithm selection. For multigraphs, they use VF2 after internally transforming the multigraphs to edge- and vertex-coloured simple graphs, in a manner similar to IGColoredSimpleGraph.

Basic functions

IGIsomorphicQ

?IGIsomorphicQ

12kg958ipf79x

?IGGetIsomorphism

0s04cs6pjys8z

IGIsomorphicQ decides if two graphs are isomorphic.

IGIsomorphicQ[IGShorthand["a-b-c-a-d"], IGShorthand["1-2,3-4-2-3"]]
True

IGIsomorphicQ supports multigraphs.

1b19ve2bowsif

True

1kvkqg286mark

False

Get a specific mapping between the vertices of the graphs.

140qgh0gn87js

{<|1 -> 4, 2 -> 3, 3 -> 1, 4 -> 2|>}

When the graphs are not isomorphic, an empty list is returned.

IGGetIsomorphism[CycleGraph[4], IGCompleteGraph[4]]
{}

IGSubisomorphicQ

?IGSubisomorphicQ

1dongpicmr9q5

?IGGetSubisomorphism

084liqyo8rdlk

IGSubisomorphicQ decides if a subgraph is part of a larger graph.

A dodecahedral graph does not contain a [1, 2, 3] symmetric tree.

target = GraphData["DodecahedralGraph"];
pattern = IGSymmetricTree[{1, 2, 3}];
IGSubisomorphicQ[pattern, target]
False

It does contain a [3, 2, 1] tree.

pattern = IGSymmetricTree[{3, 2, 1}];
IGSubisomorphicQ[pattern, target]
True

Let us retrieve a specific mapping …

{iso} = IGGetSubisomorphism[pattern, target]
{<|1 -> 1, 2 -> 14, 3 -> 15, 4 -> 16, 5 -> 3, 6 -> 9, 7 -> 4, 8 -> 10,
  9 -> 7, 10 -> 8, 11 -> 19, 12 -> 17, 13 -> 20, 14 -> 18, 15 -> 11, 
 16 -> 12|>}

… and highlight it.

HighlightGraph[target, VertexReplace[pattern, Normal[iso]],
 GraphHighlightStyle -> "Thick"
 ]

0bnhbhcr5e7wi

IGSubisomorphicQ supports multigraphs.

18uo4ab25vrgc

True

0mur7mhejtulm

{<|"a" -> 1, "b" -> 2|>}

19ei1vqqdn205

True

1hv3lwp948wyt

False

Bliss

The Bliss library was developed by Tommi Junttila and Petteri Kaski. It is capable of canonical labelling of directed or undirected vertex coloured graphs.

Bliss generally outperforms Mathematica’s built-in isomorphisms functions (including finding and counting automorphisms) as of Mathematica 12.0. However, this advantage will only be apparent for large and difficult graphs. For small ones the overhead of having to copy the graph and convert it to igraph’s internal format is much larger than the actual computation time.

?IGBliss*

0uazzyp14t4vl

All Bliss functions take a "SplittingHeuristics" option, which can influence the performance of the method. Possible values are:

The default setting is "FirstLargest", which performs well on average on sparse graphs.

Note: The result of the IGBlissCanonicalLabeling, IGBlissCanonicalPermutation and IGBlissanonicalGraph functions depend on the choice of "SplittingHeuristics". See the Bliss documentation for more information.

Basic examples

Let us take the cuboctahedral graph from GraphData …

g1 = GraphData["CuboctahedralGraph"]

1oesn1pzr05ad

… and also generate it based on its LCF notation.

g2 = IGLCF[{4, 2}, 6]

00rprv4sakt9g

The two graphs are isomorphic:

IGBlissIsomorphicQ[g1, g2]
True

One particular mapping between them is the following:

IGBlissGetIsomorphism[g1, g2]
{<|1 -> 1, 2 -> 2, 3 -> 5, 4 -> 12, 5 -> 9, 6 -> 4, 7 -> 10, 8 -> 3, 
 9 -> 6, 10 -> 11, 11 -> 8, 12 -> 7|>}

How many mappings are there in total? The same number as the number of automorphisms of either graph.

IGBlissAutomorphismCount[g1]
48

Bliss cannot generate all 48 of these mappings directly. We can either use VF2 for this …

IGVF2FindIsomorphisms[g1, g2] // Length
48

… or we can use the automorphism group computed by the IGBlissAutomorphismGroup function.

group = IGBlissAutomorphismGroup[g1]
PermutationGroup[{Cycles[{{2, 3}, {4, 5}, {8, 9}, {10, 11}}], 
 Cycles[{{2, 4}, {3, 5}, {6, 7}, {8, 10}, {9, 11}}], 
 Cycles[{{1, 2}, {3, 6}, {5, 8}, {7, 10}, {11, 12}}]}]
GroupOrder[group]
48

Ask for all 48 vertex permutations that create isomorphic graphs:

PermutationReplace[VertexList[g1], group]
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {1, 3, 2, 5, 4, 6, 7, 9, 8, 
 11, 10, 12}, {1, 4, 5, 2, 3, 7, 6, 10, 11, 8, 9, 12}, {1, 5, 4, 3, 
 2, 7, 6, 11, 10, 9, 8, 12}, {2, 1, 6, 4, 8, 3, 10, 5, 9, 7, 12, 
 11}, {2, 4, 8, 1, 6, 10, 3, 7, 12, 5, 9, 11}, {2, 6, 1, 8, 4, 3, 10,
  9, 5, 12, 7, 11}, {2, 8, 4, 6, 1, 10, 3, 12, 7, 9, 5, 11}, {3, 1, 
 6, 5, 9, 2, 11, 4, 8, 7, 12, 10}, {3, 5, 9, 1, 6, 11, 2, 7, 12, 4, 
 8, 10}, {3, 6, 1, 9, 5, 2, 11, 8, 4, 12, 7, 10}, {3, 9, 5, 6, 1, 11,
  2, 12, 7, 8, 4, 10}, {4, 1, 7, 2, 10, 5, 8, 3, 11, 6, 12, 9}, {4, 
 2, 10, 1, 7, 8, 5, 6, 12, 3, 11, 9}, {4, 7, 1, 10, 2, 5, 8, 11, 3, 
 12, 6, 9}, {4, 10, 2, 7, 1, 8, 5, 12, 6, 11, 3, 9}, {5, 1, 7, 3, 11,
  4, 9, 2, 10, 6, 12, 8}, {5, 3, 11, 1, 7, 9, 4, 6, 12, 2, 10, 
 8}, {5, 7, 1, 11, 3, 4, 9, 10, 2, 12, 6, 8}, {5, 11, 3, 7, 1, 9, 4, 
 12, 6, 10, 2, 8}, {6, 2, 3, 8, 9, 1, 12, 4, 5, 10, 11, 7}, {6, 3, 2,
  9, 8, 1, 12, 5, 4, 11, 10, 7}, {6, 8, 9, 2, 3, 12, 1, 10, 11, 4, 5,
  7}, {6, 9, 8, 3, 2, 12, 1, 11, 10, 5, 4, 7}, {7, 4, 5, 10, 11, 1, 
 12, 2, 3, 8, 9, 6}, {7, 5, 4, 11, 10, 1, 12, 3, 2, 9, 8, 6}, {7, 10,
  11, 4, 5, 12, 1, 8, 9, 2, 3, 6}, {7, 11, 10, 5, 4, 12, 1, 9, 8, 3, 
 2, 6}, {8, 2, 10, 6, 12, 4, 9, 1, 7, 3, 11, 5}, {8, 6, 12, 2, 10, 9,
  4, 3, 11, 1, 7, 5}, {8, 10, 2, 12, 6, 4, 9, 7, 1, 11, 3, 5}, {8, 
 12, 6, 10, 2, 9, 4, 11, 3, 7, 1, 5}, {9, 3, 11, 6, 12, 5, 8, 1, 7, 
 2, 10, 4}, {9, 6, 12, 3, 11, 8, 5, 2, 10, 1, 7, 4}, {9, 11, 3, 12, 
 6, 5, 8, 7, 1, 10, 2, 4}, {9, 12, 6, 11, 3, 8, 5, 10, 2, 7, 1, 
 4}, {10, 4, 8, 7, 12, 2, 11, 1, 6, 5, 9, 3}, {10, 7, 12, 4, 8, 11, 
 2, 5, 9, 1, 6, 3}, {10, 8, 4, 12, 7, 2, 11, 6, 1, 9, 5, 3}, {10, 12,
  7, 8, 4, 11, 2, 9, 5, 6, 1, 3}, {11, 5, 9, 7, 12, 3, 10, 1, 6, 4, 
 8, 2}, {11, 7, 12, 5, 9, 10, 3, 4, 8, 1, 6, 2}, {11, 9, 5, 12, 7, 3,
  10, 6, 1, 8, 4, 2}, {11, 12, 7, 9, 5, 10, 3, 8, 4, 6, 1, 2}, {12, 
 8, 9, 10, 11, 6, 7, 2, 3, 4, 5, 1}, {12, 9, 8, 11, 10, 6, 7, 3, 2, 
 5, 4, 1}, {12, 10, 11, 8, 9, 7, 6, 4, 5, 2, 3, 1}, {12, 11, 10, 9, 
 8, 7, 6, 5, 4, 3, 2, 1}}

Permuting the adjacency matrix with any of these leaves it invariant.

perms = PermutationList[#, VertexCount[g1]] & /@ 
   GroupElements[group];
Equal @@ (AdjacencyMatrix[g1][[#, #]] & /@ perms)
True

Bliss works by computing a canonical labelling of vertices. Then isomorphism can be tested for by comparing the canonically relabelled graphs.

IGBlissCanonicalGraph[g1] === IGBlissCanonicalGraph[g2]
True

IGBlissCanonicalGraph returns graphs in a consistent format so that two graphs are isomorphic if and only if their canonical graphs will compare equal with ===. Note that in Mathematica, graphs may not always compare equal even if they have the same vertex and edge lists.

The corresponding permutation and labelling are

IGBlissCanonicalPermutation[g1]
{12, 11, 9, 10, 8, 7, 6, 5, 3, 4, 2, 1}
IGBlissCanonicalLabeling[g1]
<|1 -> 12, 2 -> 11, 3 -> 9, 4 -> 10, 5 -> 8, 6 -> 7, 7 -> 6, 8 -> 5, 
9 -> 3, 10 -> 4, 11 -> 2, 12 -> 1|>

Notice that the canonical labelling is simply

AssociationThread[VertexList[g1], IGBlissCanonicalPermutation[g1]]
<|1 -> 12, 2 -> 11, 3 -> 9, 4 -> 10, 5 -> 8, 6 -> 7, 7 -> 6, 8 -> 5, 
9 -> 3, 10 -> 4, 11 -> 2, 12 -> 1|>

Also notice that it is a mapping from g1 to IGBlissCanonicalGraph[g1]:

MemberQ[
 IGVF2FindIsomorphisms[g1, IGBlissCanonicalGraph[g1]],
 IGBlissCanonicalLabeling[g1]
 ]
True

The canonical graph returned by IGBlissCanonicalGraph always has vertices labelled by the integers 1, 2, … It can also be used to filter duplicates from a list of graphs

For example, let us generate all possible adjacency matrices of 3-vertex simple directed graphs.

(* fills nondiagonal entries of n by n matrix from vector *)

toMat[vec_, n_] := 
 SparseArray@
  Partition[Flatten@Riffle[Partition[vec, n], 0, {1, -1, 2}], n]

There are 2^(3 2) = 2^6 = 64 such matrices.

graphs = AdjacencyGraph[toMat[#, 3], DirectedEdges -> True] & /@ 
   IntegerDigits[Range[2^6] - 1, 2, 6];

But only 16 of them correspond to non-isomorphic graphs

DeleteDuplicatesBy[graphs, IGBlissCanonicalGraph] // Length
16

When IGBlissCanonicalGraph is given a vertex coloured graph, it will encode the colours into a vertex property named "Color". This allows distinguishing between graphs whose canonical graphs are identical in structure, but differ in colouring.

Take for example the following coloured graphs:

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3}, 
   VertexSize -> Large, GraphStyle -> "BasicBlack"];
colg1 = Graph[g, 
   Properties -> {1 -> {"color" -> 1}, 2 -> {"color" -> 3}, 
     3 -> {"color" -> 2}}];
colg2 = Graph[g, 
   Properties -> {1 -> {"color" -> 1}, 2 -> {"color" -> 3}, 
     3 -> {"color" -> 1}}];

Visualize them for clarity:

IGVertexMap[ColorData[97], 
  VertexStyle -> IGVertexProp["color"]] /@ {colg1, colg2}

19q9yd8acwd88

The vertex and edge lists of their canonical graphs are identical:

cang1 = IGBlissCanonicalGraph[{colg1, "VertexColors" -> "color"}];
cang2 = IGBlissCanonicalGraph[{colg2, "VertexColors" -> "color"}];
VertexList /@ {cang1, cang2}
EdgeList /@ {cang1, cang2}
{{1, 2, 3}, {1, 2, 3}}
{{1 \[UndirectedEdge] 3, 
 2 \[UndirectedEdge] 3}, {1 \[UndirectedEdge] 3, 
 2 \[UndirectedEdge] 3}}

But they differ in colouring, and therefore do not compare equal:

IGVertexPropertyList[cang1]
{"Color", VertexCoordinates, VertexShape, VertexShapeFunction, \
VertexSize, VertexStyle}
IGVertexProp["Color"] /@ {cang1, cang2}
{{1, 2, 3}, {1, 1, 3}}
cang1 === cang2
False

The performance of Bliss functions may depend significantly on the choice of splitting heuristics.

g = LineGraph@GraphData[{"Hadamard", {24, 6}}];
timings = {#, 
     First@Timing@
       IGBlissAutomorphismGroup[g, 
        "SplittingHeuristics" -> #]} & /@
   {"First", 
    "FirstSmallest", "FirstLargest", "FirstMaximallyConnected", 
    "FirstSmallestMaximallyConnected", 
    "FirstLargestMaximallyConnected"};
TableForm[timings, 
 TableHeadings -> {None, {"Splitting heuristics", "Timing (s)"}}]

1kzgf9r298gbi

Additional examples

Let us visualize the vertex equivalence classes induced by a graph’s automorphism group. Two vertices are considered equivalent if there is an automorphism that maps one into the other.

With[{g = GraphData[{"Mycielski", 4}]}, 
 HighlightGraph[g, GroupOrbits@IGBlissAutomorphismGroup[g],
  VertexSize -> Large, GraphStyle -> "BasicBlack"]
 ]

0xyo4tl4qfe94

Visualize the edge equivalence classes of a polyhedron, induced by its skeleton’s automorphism group.

mesh = PolyhedronData["TruncatedOctahedron", "BoundaryMeshRegion"]

10kvro62x0lnn

With[{g = IGMeshGraph[mesh, VertexStyle -> Black]},
 HighlightGraph[g,
  EdgeList[g][[#]] & /@ 
   GroupOrbits@IGBlissAutomorphismGroup@LineGraph[g]
  ]
 ]

106zjbggf4q73

References

VF2

?IGVF2*

149e5p9rpr0gv

VF2 supports vertex coloured and edge coloured graphs. A colour specification consists of one or more of the "VertexColors" and "EdgeColors" options. Allowed formats for these options are a list of integers, an association assigning integers to the vertices/edges, or None. When using associations, it is not necessarily to specify a colour for each vertex/edge. The omitted ones are assumed to have colour 0.

The VF2 algorithm only supports simple graphs.

The following graph has two automorphisms: {1, 2} and {2, 1}.

g = Graph[{1 \[UndirectedEdge] 2}];
IGVF2IsomorphismCount[g, g]
2

If we colour one of the vertices, the permutation {2, 1} becomes forbidden, so only one automorphism remains.

IGVF2IsomorphismCount[{g, "VertexColors" -> {1, 2}}, {g, 
  "VertexColors" -> {1, 2}}]
1

Multigraphs are not directly supported for isomorphism checking, but we can map the multigraph isomorphism problem into an edge-coloured graph isomorphism one by designating the multiplicity of each edge as its colour.

g1 = EdgeAdd[PathGraph[Range[5], VertexLabels -> "Name"], 
  2 \[UndirectedEdge] 3]

12snzrqfqkwl3

g2 = EdgeAdd[PathGraph[Range[5], VertexLabels -> "Name"], 
  4 \[UndirectedEdge] 3]

178wqe5u3qc7v

IGVF2IsomorphicQ[g1, g2]

1b2jgdxhe8761

$Failed

Since g1 and g2 are undirected, we need to bring their edges into a sorted canonical form before counting them. This ensures that 4 \[UndirectedEdge] 3 and 3 \[UndirectedEdge] 4 are treated as the same edge.

colors1 = Counts[Sort /@ EdgeList[g1]]
<|1 \[UndirectedEdge] 2 -> 1, 2 \[UndirectedEdge] 3 -> 2, 
3 \[UndirectedEdge] 4 -> 1, 4 \[UndirectedEdge] 5 -> 1|>
colors2 = Counts[Sort /@ EdgeList[g2]]
<|1 \[UndirectedEdge] 2 -> 1, 2 \[UndirectedEdge] 3 -> 1, 
3 \[UndirectedEdge] 4 -> 2, 4 \[UndirectedEdge] 5 -> 1|>
IGVF2IsomorphicQ[{Graph@Keys[colors1], 
  "EdgeColors" -> colors1}, {Graph@Keys[colors2], 
  "EdgeColors" -> colors2}]
True

IGIsomorphicQ and IGSubisomorphicQ check multigraph isomorphism in a similar way, based on edge colouring.

References

LAD

The LAD library was developed by Christine Solnon. It is capable of finding subgraphs in a larger graph.

The LAD algorithm only supports simple graphs.

?IGLAD*

0b6pendcv3qui

With the "Induced" -> True option LAD will search for induced subgraphs.

0x8p5l1mh5n5x

True

0g7bpkrgzubs6

False

1lndc9zdpgh87

True

Highlight subgraphs in a grid graph.

g = GridGraph[{3, 3}];
HighlightGraph[g, Subgraph[g, #], GraphHighlightStyle -> "Thick"] & /@
  Union[Sort@*Values /@ 
   IGLADFindSubisomorphisms[GridGraph[{2, 2}], g]]

1mo4w3fpqh3zm

Count how many times each vertex of a graph appears at the apex of the following subgraph (motif):

0t457ug2vkdqx

Generate a directed random graph to do the counting in.

g = RandomGraph[{20, 120}, DirectedEdges -> True]

1cwde97k85dzs

IGShorthand provides a concise way to input this subgraph.

motif = IGShorthand["2<->1<->3"]

0fomi0qwgd1bl

This motif has a two-fold symmetry, as revealed by its automorphism group. We divide the final counts by two.

Counts@Lookup[
   IGLADFindSubisomorphisms[motif, g, "Induced" -> True],
   1
   ]/IGBlissAutomorphismCount[motif]
<|10 -> 3, 3 -> 1, 4 -> 1, 5 -> 2, 20 -> 2, 1 -> 3, 9 -> 1, 13 -> 1, 
17 -> 1|>

Check that a graph is claw-free.

clawFreeQ[graph_?UndirectedGraphQ] :=
 Not@IGLADSubisomorphicQ[
   StarGraph[4], (* claw graph *)
   graph,
   "Induced" -> True
   ]
clawFreeQ /@ {GraphData["DodecahedralGraph"], 
  GraphData["TruncatedPrismGraph"]}
{False, True}

References

Isomorphism of coloured graphs

All three included isomorphism algorithms support vertex coloured graphs, and VF2 supports edge coloured graphs as well. A coloured graph is specified as {g, "VertexColors" -> …, "EdgeColors" -> …}, where both vertex and edge colour specifications are optional. Colours are represented by integers and may be specified in one of the following ways:

Example. Define a graph along with the colours of its vertices.

g = CycleGraph[4];
vcols = <|
   1 -> 1, 2 -> 1,
   3 -> 2, 4 -> 2
   |>;

Visualize it.

Graph[g,
 VertexStyle -> Normal[ColorData[24] /@ vcols],
 VertexSize -> Medium, VertexLabels -> Placed["Name", Center]
 ]

1q80tlx74iaq5

Compute its automorphism group, taking vertex colours into account.

IGBlissAutomorphismGroup[{g, "VertexColors" -> vcols}]
PermutationGroup[{Cycles[{{1, 2}, {3, 4}}]}]

The functions in this section test for properties related to a graph’s automorphism group. The summary table below illustrates the functions on a set of graphs which all have different properties.

graphs = {StarGraph[4], IGSquareLattice[{2, 3}, "Periodic" -> True], 
   HypercubeGraph[3], GraphData[{"Rook", {4, 4}}], 
   GraphData["ShrikhandeGraph"], GraphData["HoltGraph"], 
   GraphData["Tutte12Cage"], GraphData[{"Paulus", {25, 1}}]};

functions = <|
   "regular" -> IGRegularQ,
   "strongly regular" -> IGStronglyRegularQ, 
   "distance regular" -> IGDistanceRegularQ,
   "vertex transitive" -> IGVertexTransitiveQ,
   "edge transitive" -> IGEdgeTransitiveQ,
   "arc transitive" -> IGEdgeTransitiveQ@*DirectedGraph,
   "distance transitive" -> IGDistanceTransitiveQ
   |>;

TableForm[
  Through[Values[functions][#]] & /@ graphs,
  TableHeadings -> {Show[#, ImageSize -> 50] & /@ graphs, 
    Keys[functions]},
  TableDirections -> Row
  ] // Style[#, "Text"] &

1xq683vl3hw94

IGRegularQ

?IGRegularQ

1sj00agpomx5c

IGRegularQ checks if a graph is regular. All vertices of a regular graph have the same degrees. In regular directed graphs, the in- and out-degrees are also equal to each other.

IGRegularQ[IGSquareLattice[{3, 4}, "Periodic" -> True]]
True

Check if a graph is \(k\)-regular for \(k=2\) and \(k=3\).

IGRegularQ[CycleGraph[10], 2]
True
IGRegularQ[CycleGraph[10], 3]
False

The null graph is considered 0-regular.

IGRegularQ[IGEmptyGraph[]]
True

Check if a directed graph is regular.

IGRegularQ[CycleGraph[5, DirectedEdges -> True]]
True

IGRegularQ considers self-loops and multi-edges when computing vertex degrees.

1aehq0btpm2ej

True

IGStronglyRegularQ

?IGStronglyRegularQ

1gda4echluhxt

IGStronglyRegularQ checks if a graph is strongly regular. A strongly regular graph is a regular graph where each pair of connected vertices have the same number of common neighbours, \(\lambda\), and each pair of unconnected vertices also have the same number of common neighbours, \(\mu\).

IGStronglyRegularQ@GraphData["ShrikhandeGraph"]
True

Hypercube graphs and 3 and higher dimensions are not strongly regular, even though they are regular.

IGStronglyRegularQ /@ HypercubeGraph /@ Range[2, 4]
{True, False, False}

Some authors exclude empty and complete graph from the definition, as they satisfy these conditions trivially. IGStronglyRegularQ returns True for these.

IGStronglyRegularQ /@ {IGEmptyGraph[5], IGCompleteGraph[6]}
{True, True}

It also returns True for graphs on 0, 1 and 2 vertices.

IGStronglyRegularQ /@ IGCompleteGraph /@ Range[0, 2]
{True, True, True}

Currently, IGStronglyRegularQ does not support directed graphs.

IGStronglyRegularQ@Graph[{1 -> 2}]

0uq9065wl4dx9

$Failed

IGStronglyRegularParameters

?IGStronglyRegularParameters

0r3xca4ft4ng9

IGStronglyRegularParameters returns the parameters \((v,k,\lambda ,\mu )\) of a strongly regular graph. \(v\) is the number of vertices, \(k\) the degree of the vertices, \(\lambda\) the number of common neighbours of connected vertices and \(\mu\) the number of common neighbours of unconnected vertices.

IGStronglyRegularParameters[PetersenGraph[]]
{10, 3, 0, 1}
IGStronglyRegularParameters[CycleGraph[5]]
{5, 2, 0, 1}

The parameters of a strongly regular graph satisfy the equation \((v-k-1)\mu =k(k-\lambda -1)\).

{v, k, lambda, mu} = 
 IGStronglyRegularParameters[GraphData[{"Paley", 101}]]
{101, 50, 24, 25}
(v - k - 1) mu == k (k - lambda - 1)
True

\(\lambda\) and \(\mu\) are not well-defined for empty and complete graphs, respectively. In these cases, 0 is returned.

IGStronglyRegularParameters /@ {IGEmptyGraph[5], IGCompleteGraph[6]}
{{5, 0, 0, 0}, {6, 5, 4, 0}}

For non-strongly-regular graphs, {} is returned.

IGStronglyRegularParameters[HypercubeGraph[3]]
{}

IGDistanceRegularQ

?IGDistanceRegularQ

0e1a1o5i4ewel

IGDistanceRegularGraph checks if a graph is distance regular.

IGDistanceRegularQ@HypercubeGraph[5]
True
IGDistanceRegularQ@IGSquareLattice[{2, 5}, "Periodic" -> True]
False

A distance regular graph with a diameter of 2 is also strongly regular.

g = GraphData[{"Paley", 13}]

1pfzsh6ckpwqp

{IGDiameter[g], IGDistanceRegularQ[g], IGStronglyRegularQ[g]}
{2, True, True}

The Shrikhande graph is the smallest graph that is distance regular, but not distance transitive.

Through[{IGDistanceRegularQ, IGDistanceTransitiveQ}[
  GraphData["ShrikhandeGraph"]]]
{True, False}

A disconnected graph is distance regular if its components are distance regular and they are co-spectral. The following graphs are co-spectral:

components = {GraphData[{"Rook", {4, 4}}], 
  GraphData["ShrikhandeGraph"]}

1sa2rweuflu0x

Eigenvalues /@ AdjacencyMatrix /@ components
{{6, -2, -2, -2, -2, -2, -2, -2, -2, -2, 2, 2, 2, 2, 2, 
 2}, {6, -2, -2, -2, -2, -2, -2, -2, -2, -2, 2, 2, 2, 2, 2, 2}}

They are both distance regular with the same intersection array.

IGIntersectionArray /@ components
{{{6, 3}, {1, 2}}, {{6, 3}, {1, 2}}}

Thus their disjoint union is also distance regular.

IGDistanceRegularQ@IGDisjointUnion[components]
True

All distance transitive graphs are also distance regular, but the reverse is not true.

IGDistanceTransitiveQ /@ components
{True, False}

IGDistanceRegularQ does not currently support directed graphs or non-simple graphs.

IGDistanceRegularQ[Graph[{1 -> 2}]]

0hogmjz7eu30z

$Failed
IGDistanceRegularQ[
 Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 2}]]

0ik0hrwm0d8mq

$Failed

IGIntersectionArray

?IGIntersectionArray

04aqhdqpr4u8q

IGIntersectionArray@GraphData["IcosahedralGraph"]
{{5, 2, 1}, {1, 2, 5}}
IGIntersectionArray@GraphData["SuzukiGraph"]
{{416, 315}, {1, 96}}
IGIntersectionArray@CycleGraph[6]
{{2, 1, 1}, {1, 1, 2}}

For non-distance-regular graphs, {} is returned.

IGIntersectionArray[GridGraph[{3, 3}]]
{}

IGIntersectionArray does not currently support directed graphs.

IGIntersectionArray[Graph[{1 -> 2}]]

1o8fakwjb44jd

$Failed

IGVertexTransitiveQ

?IGVertexTransitiveQ

066p2lxzyhth2

IGVertexTransitiveQ checks if a graph is vertex transitive, i.e. if any vertex can be mapped into any other by some automorphism of the graph.

1agg4gmin3k4e

True

14sqormzcidki

False

All Cayley graphs are vertex transitive.

cg = CayleyGraph@IGBlissAutomorphismGroup@IGLCF[{2, -1, 2}, 3]

1lprnfl16fdsv

IGVertexTransitiveQ[cg]
True

IGEdgeTransitiveQ

?IGEdgeTransitiveQ

1gu66e9iex9rf

IGEdgeTransitiveQ checks if a graph is edge transitive, i.e. if any edge can be mapped into any other by some automorphism of the graph.

07q5zknxyot88

False

18lypuor3a2gu

True

The Folkman graph is not vertex transitive but it is edge transitive.

Through[{IGVertexTransitiveQ, IGEdgeTransitiveQ}@
  GraphData["FolkmanGraph"]]
{False, True}

IGEdgeTransitiveQ takes into account edge directions.

IGEdgeTransitiveQ@Graph[{1 -> 2, 2 -> 3}]
False
IGEdgeTransitiveQ@Graph[{1 -> 2, 3 -> 2}]
True

Arc transitivity in an undirected graph refers to edge transitivity when each undirected edge is replaced by two opposite directed edges.

arcTransitiveQ[graph_?UndirectedGraphQ] := 
 IGEdgeTransitiveQ@DirectedGraph[graph]

Some graphs are edge transitive, but not arc transitive.

IGEdgeTransitiveQ@GraphData[{"Bouwer", {2, 4, 15}}]
True
arcTransitiveQ@GraphData[{"Bouwer", {2, 4, 15}}]
False

Most graphs are edge transitive if their line graphs are vertex transitive. The exceptions are disjoint unions of the 3-star and 3-cycle. These two graphs have the same line graph, but they are not isomorphic.

0w49gr4dsg64j

{IGEdgeTransitiveQ[g], IGVertexTransitiveQ@LineGraph[g]}
{False, True}

IGSymmetricQ

?IGSymmetricQ

0qvbfx2mixy88

IGSymmetricQ checks if a graph is both vertex transitive and edge transitive. Note that this property is distinct from being arc transitive, which is the definition used for “symmetric” by some authors.

IGSymmetricQ[GraphData["DodecahedralGraph"]]
True

Make a table of symmetric graphs up to size 7:

Grid[
 Table[
  Graph[#, ImageSize -> 50, PlotTheme -> "Business"] & /@ 
   Select[GraphData /@ GraphData[k], IGSymmetricQ],
  {k, 1, 7}
  ], Frame -> All, ItemSize -> All]

04e1i7o896qm3

Some authors use the term symmetric graph to refer to arc transitive graphs. Arc transitivity can be checked using IGEdgeTransitiveQ@DirectedGraph[#] &. All arc-transitive graphs are both vertex- and edge-transitive, but the reverse is not true. The smallest graph that is both vertex- and edge-transitive, but not arc-transitive, is the 27-vertex Doyle graph, also known as the Holt graph.

doyle = GraphData["DoyleGraph"]

0po2lur2ho335

{IGVertexTransitiveQ[doyle], IGEdgeTransitiveQ[doyle]}
{True, True}
IGEdgeTransitiveQ@DirectedGraph[doyle]
False

IGDistanceTransitiveQ

?IGDistanceTransitiveQ

1wm1miqf8u768

IGDistanceTransitiveQ checks if a graph is distance transitive. In a distance transitive graph, any two ordered pairs of vertices which are the same distance apart can be mapped into each other by some automorphism.

All Platonic graphs are distance transitive.

IGMeshGraph@PolyhedronData[#, "BoundaryMeshRegion"] & /@ 
 PolyhedronData["Platonic"]

14vfohrh1n1c1

IGDistanceTransitiveQ /@ %
{True, True, True, True, True}

Some graphs are symmetric, but not distance transitive.

g = GraphData[{"Circulant", {10, {1, 4}}}]

0f3afvnx791d3

{IGSymmetricQ[g], IGDistanceTransitiveQ[g]}
{True, False}

IGDistanceTransitiveQ does not exclude non-connected graphs.

0trpnashdhit3

True

IGDistanceTransitiveQ works with directed graphs.

g = With[{n = 11},
  RelationGraph[
   MemberQ[Rest@Union@Mod[Range[n]^2, n], Mod[#1 - #2, n]] &, 
   Range[n] - 1]
  ]

0nbwyjrj7b8rp

IGDistanceTransitiveQ[g]
True

The following directed graph is vertex transitive, but not distance transitive.

0bf68ts96p6vw

False

Homeomorphism

?IGHomeomorphicQ

1xvpkmaxd6hgr

IGHomeomorphicQ tests if two graphs are homeomorphic, i.e. whether they have the same topological structure. Two graphs \(G_1\) and \(G_2\) are homeomorphic if there is an isomorphism from a subdivision of \(G_1\) to a subdivision of \(G_2\).

0gpeury5rutqc is effectively implemented as 1bt8h2913eesv.

The following graphs are homeomorphic.

1cwrl2me7jroa

True

They smoothen to the same graph.

1mcl184jqe6cd

1mt35y6362u29

Any two cycle graphs are homeomorphic.

IGHomeomorphicQ[CycleGraph[5], CycleGraph[9]]
True

A cycle and a path graph are not homeomorphic.

IGHomeomorphicQ[CycleGraph[5], PathGraph@Range[5]]
False

A triangular and a square lattice on the same number of vertices are, in general, topologically different.

IGHomeomorphicQ[IGSquareLattice[{3, 3}], IGTriangularLattice[{3, 3}]]
False

When testing empirical graphs for equivalence, it is often useful to remove tree-like components. For example, the face-face and the face-edge adjacency graphs of a geometric mesh are equivalent, save for the tree-like components.

mesh = IGLatticeMesh["SnubSquare", {3, 3}];
ffg = IGMeshCellAdjacencyGraph[mesh, 2, 
  VertexCoordinates -> Automatic]

0780y0s5dlizn

feg = IGMeshCellAdjacencyGraph[mesh, 1, 2, 
  VertexCoordinates -> Automatic]

089verex88a6i

IGHomeomorphicQ[feg, ffg]
False
feg = VertexDelete[feg, IGTreelikeComponents[feg]]

0ezzdxik17v2h

ffg = VertexDelete[ffg, IGTreelikeComponents[ffg]]

1nszwb2sybzc7

IGHomeomorphicQ[feg, ffg]
True

Other functions

IGSelfComplementaryQ

?IGSelfComplementaryQ

0528oqgacgf9t

A graph is called self-complementary if it is isomorphic with its complement.

The 4-vertex path graph is self-complementary.

IGSelfComplementaryQ[PathGraph@Range[4]]
True

Find all 3-vertex self-complementary directed graphs.

Select[IGData[{"AllDirectedGraphs", 3}], IGSelfComplementaryQ]

0t81561nsb060

IGColoredSimpleGraph

?IGColoredSimpleGraph

1jkbdn4jdwrn6

IGColoredSimpleGraph is a helper function that encodes a non-simple graph (i.e a graph with self-loops or multi-edges) into an edge- and vertex-colored simple graph. The coloured simple graph can be used directly as an input to coloured isomorphism checking functions such as IGVF2IsomorphicQ.

The vertex colours are computed as the multiplicity of self-loops at each vertex. The edge colours are computed as the multiplicities or non-loop edges.

The following graphs are not simple and cannot be used with IGVF2IsomorphicQ directly.

19hsi4qxwk90w

IGVF2IsomorphicQ[g1, g2]

1fz422arzo3j0

$Failed

IGColoredSimpleGraph can encode them as coloured graphs. Its output can be supplied directly to IGVF2IsomorphicQ.

IGColoredSimpleGraph[g1]

0gs3ws8ntl1z4

Now can can determine that g1 is isomorphic to g2, but not to g3.

IGVF2IsomorphicQ[IGColoredSimpleGraph[g1], IGColoredSimpleGraph[g2]]
True
IGVF2IsomorphicQ[IGColoredSimpleGraph[g1], IGColoredSimpleGraph[g3]]
False

When searching for subgraphs in multigraphs with this method, be aware that a match occurs only if the edge multiplicities are the same. This sort of matching is useful e.g. in substructure search chemistry, where a double bond must only match another double bond, but not a single one.

1ky32co1v2qgt

False

18rbq0ajw2g7l

True

Use IGSubisomorphicQ to match any subgraph.

0mhfaoe72crou

True

Maximum flow and minimum cut

Maximum flow

IGMaximumFlowValue

?IGMaximumFlowValue

1ov8iczos0rqb

IGMaximumFlowValue is equivalent to IGMinimumCutValue except that it uses the EdgeCapacity property instead of EdgeWeight.

Edge capacities are taken from the EdgeCapacity property.

1mzv8jpd9uok8

{3.5, 2, 1, 2.5, 5, 1, 3.5, 4}
IGMaximumFlowValue[g, 1, 4]
3.5

IGMaximumFlowMatrix

?IGMaximumFlowMatrix

1mqt8oswmfcdn

Element \(F_{ij}\) of the flow matrix is the flow through the edge connecting the \(i\)th node to the \(j\)th one. In an undirected graph, \(F_{ij}=-F_{ij}\).

Edge capacities are taken from the EdgeCapacity property.

Let us take a directed graph with edge capacities set …

0yfh9chrxui7o

IGEdgeProp[EdgeCapacity][g]
{3.5, 2, 1, 2.5, 5, 1, 3.5, 4}

… and compute the maximum flow between two of its vertices.

flowMat = IGMaximumFlowMatrix[g, 1, 4]

05k26skx39v5y

The result is returned as a sparse matrix containing the flows through each edge.

MatrixForm[flowMat]

02hs6idsmwcbg

If the input is an undirected graph, the flow matrix contains entries of opposing sign for the two directions along each edge.

IGMaximumFlowMatrix[UndirectedGraph[g], 1, 4] // MatrixForm

1ibqao6ahklyo

Minimum edge cuts

IGMinimumCut

?IGMinimumCut

0gqjlh1t8gmem

IGMinimumCutValue

?IGMinimumCutValue

1t78fyztb5eym

Unlike IGEdgeConnectivity, IGMinimumCutValue takes weights into account.

IGMinimumCutValue[
 Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3}, 
  EdgeWeight -> {3.5, 5.6}]]
3.5

The minimum cut value of the null graph and singleton graph are returned as 0 and , respectively.

IGMinimumCutValue /@ {IGEmptyGraph[0], IGEmptyGraph[1]}
{0., ∞}

IGGomoryHuTree

?IGGomoryHuTree

0zlw2erj4drdy

The Gomory–Hu tree is a weighted tree that encodes the minimum cuts between all pairs of vertices of an undirected graph. The Gomory–Hu tree has the same vertices as the graph it characterizes. The minimum cut between an \(s\)-\(t\) pair of the graph has the same size as smallest edge weight on the path from \(s\) to \(t\) in the Gomory–Hu tree.

Weighted graphs are supported.

0e5p6hpqjsfp7

t = IGGomoryHuTree[g,
  EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"
  ]

033st3xp30yj7

The path from 1 to 9 is 1 \[UndirectedEdge] 2 \[UndirectedEdge] 5 \[UndirectedEdge] 9 and has the weights {3, 5, 4}. The smallest one, 3, is the minimum value of a cut separating 1 from 9.

{IGMinimumCutValue[g, 1, 9], IGMinimumCutValue[t, 1, 9]}
{3., 3.}

Cohesive blocks

?IGCohesiveBlocks

0oqc8ir9k635h

The following examples are based on the ones in the R/igraph documentation.

This is the network from the Moody-White paper:

mw = Graph[{"1" \[UndirectedEdge] "2", "1" \[UndirectedEdge] "3", 
    "1" \[UndirectedEdge] "4", "1" \[UndirectedEdge] "5", 
    "1" \[UndirectedEdge] "6", "2" \[UndirectedEdge] "3", 
    "2" \[UndirectedEdge] "4", "2" \[UndirectedEdge] "5", 
    "2" \[UndirectedEdge] "7", "3" \[UndirectedEdge] "4", 
    "3" \[UndirectedEdge] "6", "3" \[UndirectedEdge] "7", 
    "4" \[UndirectedEdge] "5", "4" \[UndirectedEdge] "6", 
    "4" \[UndirectedEdge] "7", "5" \[UndirectedEdge] "6", 
    "5" \[UndirectedEdge] "7", "5" \[UndirectedEdge] "21", 
    "6" \[UndirectedEdge] "7", "7" \[UndirectedEdge] "8", 
    "7" \[UndirectedEdge] "11", "7" \[UndirectedEdge] "14", 
    "7" \[UndirectedEdge] "19", "8" \[UndirectedEdge] "9", 
    "8" \[UndirectedEdge] "11", "8" \[UndirectedEdge] "14", 
    "9" \[UndirectedEdge] "10", "10" \[UndirectedEdge] "12", 
    "10" \[UndirectedEdge] "13", "11" \[UndirectedEdge] "12", 
    "11" \[UndirectedEdge] "14", "12" \[UndirectedEdge] "16", 
    "13" \[UndirectedEdge] "16", "14" \[UndirectedEdge] "15", 
    "15" \[UndirectedEdge] "16", "17" \[UndirectedEdge] "18", 
    "17" \[UndirectedEdge] "19", "17" \[UndirectedEdge] "20", 
    "18" \[UndirectedEdge] "20", "18" \[UndirectedEdge] "21", 
    "19" \[UndirectedEdge] "20", "19" \[UndirectedEdge] "22", 
    "19" \[UndirectedEdge] "23", "20" \[UndirectedEdge] "21", 
    "21" \[UndirectedEdge] "22", "21" \[UndirectedEdge] "23", 
    "22" \[UndirectedEdge] "23"}, VertexLabels -> "Name"];
{blocks, cohesion} = IGCohesiveBlocks[mw]
{{{"1", "2", "3", "4", "5", "6", "7", "21", "8", "11", "14", "19", 
  "9", "10", "12", "13", "16", "15", "17", "18", "20", "22", 
  "23"}, {"1", "2", "3", "4", "5", "6", "7", "21", "19", "17", "18", 
  "20", "22", "23"}, {"7", "8", "11", "14", "9", "10", "12", "13", 
  "16", "15"}, {"1", "2", "3", "4", "5", "6", "7"}, {"7", "8", "11", 
  "14"}}, {1, 2, 2, 5, 3}}
CommunityGraphPlot[mw, Rest@blocks, 
 CommunityRegionStyle -> 
  Table[Directive[Opacity[0.5], ColorData[96][i]], {i, 
    Length[blocks] - 1}]]

0tycxdgkazjk6

cohesion
{1, 2, 2, 5, 3}

Science camp network:

sc = Graph[{"Pauline" \[UndirectedEdge] "Jennie", 
    "Pauline" \[UndirectedEdge] "Ann", 
    "Jennie" \[UndirectedEdge] "Ann", 
    "Jennie" \[UndirectedEdge] "Michael", 
    "Michael" \[UndirectedEdge] "Ann", 
    "Holly" \[UndirectedEdge] "Jennie", 
    "Jennie" \[UndirectedEdge] "Lee", 
    "Michael" \[UndirectedEdge] "Lee", 
    "Harry" \[UndirectedEdge] "Bert", "Harry" \[UndirectedEdge] "Don",
     "Don" \[UndirectedEdge] "Bert", "Gery" \[UndirectedEdge] "Russ", 
    "Russ" \[UndirectedEdge] "Bert", 
    "Michael" \[UndirectedEdge] "John", 
    "Gery" \[UndirectedEdge] "John", "Russ" \[UndirectedEdge] "John", 
    "Holly" \[UndirectedEdge] "Pam", "Pam" \[UndirectedEdge] "Carol", 
    "Holly" \[UndirectedEdge] "Carol", 
    "Holly" \[UndirectedEdge] "Bill", 
    "Bill" \[UndirectedEdge] "Pauline", 
    "Bill" \[UndirectedEdge] "Michael", 
    "Bill" \[UndirectedEdge] "Lee", "Harry" \[UndirectedEdge] "Steve",
     "Steve" \[UndirectedEdge] "Don", 
    "Steve" \[UndirectedEdge] "Bert", 
    "Gery" \[UndirectedEdge] "Steve", 
    "Russ" \[UndirectedEdge] "Steve", 
    "Pam" \[UndirectedEdge] "Brazey", 
    "Brazey" \[UndirectedEdge] "Carol", "Pam" \[UndirectedEdge] "Pat",
     "Brazey" \[UndirectedEdge] "Pat", 
    "Carol" \[UndirectedEdge] "Pat", "Holly" \[UndirectedEdge] "Pat", 
    "Gery" \[UndirectedEdge] "Pat"}, VertexLabels -> "Name"];
{blocks, cohesion} = IGCohesiveBlocks[sc]
{{{"Pauline", "Jennie", "Ann", "Michael", "Holly", "Lee", "Harry", 
  "Bert", "Don", "Gery", "Russ", "John", "Pam", "Carol", "Bill", 
  "Steve", "Brazey", "Pat"}, {"Harry", "Bert", "Don", 
  "Steve"}, {"Holly", "Pam", "Carol", "Brazey", "Pat"}, {"Pauline", 
  "Jennie", "Ann", "Michael", "Lee", "Bill"}}, {2, 3, 3, 3}}
CommunityGraphPlot[sc, Rest@blocks, 
 CommunityRegionStyle -> ColorData[96], ImageSize -> Large]

03fqxqe7uhcwq

Cliques and independent vertex sets

?IG*Clique*

1kacpr5ljirw3

A clique is a fully connected subgraph. An independent vertex set is a subset of a graph’s vertices with no connections between them.

Counting cliques

Mathematica’s FindClique function only finds maximal cliques. IGraph/M provides functions for finding or counting all cliques, i.e. complete subgraphs, of a graph.

g = ExampleData[{"NetworkGraph", "CoauthorshipsInNetworkScience"}];
{VertexCount[g], EdgeCount[g]}
{1589, 2742}

Simply counting cliques is much more memory efficient (and faster) than returning all of them.

IGCliqueSizeCounts[g]
{1589, 2742, 3764, 7159, 17314, 39906, 78055, 126140, 167993, 184759, \
167960, 125970, 77520, 38760, 15504, 4845, 1140, 190, 20, 1}
BarChart[%, ChartLabels -> Range@Length[%]]

1syn1bwfy0k9c

IGMaximalCliqueSizeCounts[g]
{128, 221, 195, 108, 52, 19, 3, 8, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
BarChart[%, ChartLabels -> Range@Length[%]]

15qhjl1dx93hn

IGLargestCliques[g]
{{"J. Rothberg", "L. Giot", "P. Uetz", "G. Cagney", "T. Mansfield", 
 "R. Judson", "J. Knight", "D. Lockshon", "V. Narayan", 
 "M. Srinivasan", "P. Pochart", "A. Qureshiemili", "Y. Li", 
 "B. Godwin", "D. Conover", "T. Kalbfleisch", "G. Vijayadamodar", 
 "M. Yang", "M. Johnston", "S. Fields"}}

Cliques in directed graphs

The clique finder in IGraph/M ignores edge directions.

g = RandomGraph[{10, 60}, DirectedEdges -> True]

0zm0wmibzb76l

IGMaximalCliques[g]

0a9kn3he87p0f

{{10, 1, 7, 6, 2, 3}, {10, 1, 7, 6, 2, 5, 9}, {10, 1, 7, 6, 4, 5, 
 9}, {10, 1, 7, 6, 4, 8, 3}, {10, 1, 7, 6, 4, 8, 9}}

To find cliques in directed graphs, convert them to undirected and keep mutual (bidirectional) edges only.

IGMaximalCliques@IGUndirectedGraph[g, "Mutual"]
{{7, 8}, {7, 1}, {8, 4, 9}, {3, 6, 2}, {3, 6, 4}, {4, 9, 6}, {4, 9, 
 10}, {5, 9, 6}, {5, 9, 10}, {5, 1, 6}, {5, 1, 10}, {6, 2, 1}}

Clique cover

?IGCliqueCover

10xy17fpj28bg

?IGCliqueCoverNumber

0dcgxubvm5c61

A clique cover of a graph is a partitioning of its vertices such that each partition forms a clique. IGCliqueCover finds a minimum clique cover, i.e. a partitioning into a smallest number of cliques.

The clique cover number of a graph is the smallest number of cliques that can be used to cover its vertices.

Available Method option values are:

Compute a minimum clique cover of a random graph.

g = RandomGraph[{10, 20}]

003443uuywgx3

IGCliqueCover[g]
{{1, 3, 9}, {2, 4, 5}, {6, 8}, {7, 10}}

Visualize the clique cover.

HighlightGraph[g, IGCliqueCover[g], VertexSize -> Large]

12xpfxkjt8s4h

Find the clique cover number without returning a cover.

IGCliqueCoverNumber[g]
4

The clique cover problem is equivalent to the colouring of the complement graph. IGCliqueCover is effectively implemented as

IGMembershipToPartitions[g]@IGMinimumVertexColoring@GraphComplement[g]
{{1, 3, 9}, {2, 4, 5}, {6, 8}, {7, 10}}

For difficult problems, it may be useful to use IGMinimumVertexColoring or IGVertexColoring directly instead of IGCliqueCover, and tune their options to achieve better performance. See the "ForcedColoring" option of IGMinimumVertexColoring on how to do this.

Reconstruct bipartite graph of co-occurrence network

g = ExampleData[{"NetworkGraph", "LesMiserables"}]

1rzdeawm44wbx

ExampleData[{"NetworkGraph", "LesMiserables"}, "LongDescription"]
"Coappearance network of characters in the novel Les Miserables. \
EdgeWeight describes the number of coappearance."

The maximal cliques of the graph can approximate the scenes in which characters appear together.

cliques = IGMaximalCliques[g];

We can construct a bipartite graph of connections between potential scenes and characters

IGLayoutBipartite[
  Graph@Catenate[
    Thread /@ Thread[Range@Length[cliques] <-> cliques]],
  VertexSize -> 0.5, ImageSize -> 220
  ] // IGVertexMap[Placed[#, If[IntegerQ[#], Before, After]] &, 
  VertexLabels -> VertexList]

0m0df1bsppu2s

Graphlet decomposition

Note: The term “graphlet” is used for multiple unrelated concepts in the literature. This section deals with decomposing weighted graphs into cliques. If you are looking to count induced subgraphs, see the IGMotifs function.

?IGGraphlets

0ohn181ki7qy2

?IGGraphletBasis

08652pton5657

?IGGraphletProject

1pu83lp5bpbyu

g = IGShorthand["A,B,D,E,C, A-B-C-A, C-E-D-B, D-C, E-B",
  EdgeWeight -> {2, 3, 2, 4, 4, 1, 4, 1},
  EdgeLabels -> "EdgeWeight", VertexLabels -> None,
  VertexShapeFunction -> "Name", PerformanceGoal -> "Quality",
  GraphLayout -> "CircularEmbedding"
  ]

02n9tdzw5z0mk

basis = IGGraphletBasis[g]
<|{"A", "B", "C"} -> 2., {"B", "D", "E", "C"} -> 1., {"B", "C"} -> 
 3., {"D", "E", "C"} -> 4.|>
IGGraphletProject[g, Keys[basis]]
<|{"A", "B", "C"} -> 0.925543, {"B", "D", "E", "C"} -> 
 0.861478, {"B", "C"} -> 2.90881*10^-253, {"D", "E", "C"} -> 1.13842|
>
IGGraphlets[g]
<|{"D", "E", "C"} -> 1.13842, {"A", "B", "C"} -> 
 0.925543, {"B", "D", "E", "C"} -> 0.861478, {"B", "C"} -> 
 2.90881*10^-253|>

References

Layout algorithms

The following functions are available:

?IGLayout*

1orf7ckchs7mb

If you are looking for the Sugiyama layout from igraph, try the built-in GraphLayout -> "LayeredDigraphEmbedding", or LayeredGraphPlot. These are also based on the Sugiyama algorithm.

Common options and examples

Layout functions also take any standard Graph option.

Many layout algorithms take the following options:

"MaxIterations" controls either the maximum number of iterations performed by the algorithm or the exact number of iterations, depending on the specific algorithm and settings. The option name is the same for all functions to make it easier to interchange them when visualizing dynamic graphs.

"Align" -> True aligns the output horizontally. Examples:

{IGLayoutFruchtermanReingold[IGSquareLattice[{2, 4}](*, 
  "Align" -> True is the default *)], 
 IGLayoutFruchtermanReingold[IGSquareLattice[{2, 4}], 
  "Align" -> False]}

00a7sqlf3xbmo

"Continue" -> True allows using existing vertex coordinates as starting points for algorithms that update vertex positions incrementally. We can use this to visualize how the layout algorithms work …

g = IGLayoutRandom@
   RandomGraph[BarabasiAlbertGraphDistribution[100, 1]];
ListAnimate@
 NestList[IGLayoutGraphOpt[#, "Continue" -> True, 
    "MaxIterations" -> 80] &, g, 40]

09wc0qvdwk32j

… or to visualize dynamic graph processes such as adding edges to the graph one by one:

g = IGLayoutKamadaKawai@
   Graph[Range[25], {1 \[UndirectedEdge] 25}, 
    VertexLabels -> "Name"];
ListAnimate@NestList[
  IGLayoutKamadaKawai[
    EdgeAdd[#, UndirectedEdge @@ RandomSample[VertexList[#], 2]], 
    "MaxIterations" -> 15, "Continue" -> True, "Align" -> False] &,
  g,
  30
  ]

0ay48pvqadnno

Visualize a planar graph without edge crossings using the Davidson–Harel simulated annealing method, and taking starting coordinates from GraphLayout -> "PlanarEmbedding".

g = Graph@GraphData[{"Fullerene", {60, 1}}, "EdgeList"]

0fnu1n0albgle

This layout avoids crossings, but it is not pleasing:

Graph[g, GraphLayout -> "PlanarEmbedding"]

0nxykc8pipneo

We can post process it while avoiding the introduction of any edge crossings:

IGLayoutDavidsonHarel[
 IGVertexMap[# &, 
  VertexCoordinates -> (Rescale@
      GraphEmbedding[#, "PlanarEmbedding"] &), g],
 "Continue" -> True, "EdgeCrossingWeight" -> 1000
 ]

1bngy6964mdtd

Weighted graphs

Several of the graph layout algorithms in igraph can take edge weights into accounts. How the weights are used during layout differs between them.

Drawing trees

IGLayoutReingoldTilford[] and IGLayoutReingoldTilfordCircular[] are designed for laying out trees. The following options are available:

Drawing bipartite graphs

?IGLayoutBipartite

1d7p17o7pj1dq

IGLayoutBipartite draws a bipartite graph, attempting to minimize the number of edge crossing using the Sugiyama algorithm.

The available options are:

IGLayoutBipartite[IGBipartiteGameGNP[10, 10, 0.2], 
 VertexLabels -> "Name"]

0v9664z38sbh6

By default, a partitioning is computed automatically.

g = Graph[{1 \[UndirectedEdge] 2, 3 \[UndirectedEdge] 4}, 
   VertexLabels -> "Name"];
IGLayoutBipartite[g]

1qwosta2n1lj3

The partitioning can also be specified explicitly.

IGLayoutBipartite[g, "BipartitePartitions" -> {{2, 3}, {4, 1}}]

00g2wyo0z4dt8

Draw a bipartite layout with curved edges.

0bo3k4dzdjblm

00s4qc0il49as

Drawing large graphs

IGLayoutDrL is designed specifically for visualizing large graphs with high clustering. The following image is created using DrL and shows a 36000 node network of collaborations between condensed matter scientists.

0cozhnbrly2o9

The image was generated using the following code:

lg = ExampleData[{"NetworkGraph", 
    "CondensedMatterCollaborations2005"}];
lg = IndexGraph@Subgraph[lg, First@ConnectedComponents[lg]];
c = IGCommunitiesMultilevel[lg]
pts = GraphEmbedding@
   IGLayoutDrL[lg]; (* this takes a while *)
figure = Graphics[
  GraphicsComplex[pts,
   {
    {White, AbsoluteThickness[0.3], Opacity[0.05],
     Line[List @@@ EdgeList[lg]]},
    {AbsolutePointSize[2], Opacity[0.7],
     MapIndexed[
      {ColorData[45]@First[#2], Point[#1]} &,
      c["Communities"]
      ]}
    }
   ],
  Background -> Black
  ]

shift-enter evaluation is disabled in the cell above to avoid running it accidentally. Running the code takes about 2-3 minutes on a modern computer. Copy the code to a new cell to try it.

Create galleries of the various graph layouts available in IGraph/M.

Visualise a tree graph with all layouts.

g = RandomGraph[BarabasiAlbertGraphDistribution[30, 1]];
layouts = 
  Graph[#[g], PlotLabel -> #, LabelStyle -> 7] & /@ {IGLayoutCircle, 
    IGLayoutDavidsonHarel, IGLayoutDrL, IGLayoutDrL3D, 
    IGLayoutFruchtermanReingold, IGLayoutFruchtermanReingold3D, 
    IGLayoutGEM, IGLayoutGraphOpt, IGLayoutKamadaKawai, 
    IGLayoutKamadaKawai3D, IGLayoutRandom, IGLayoutReingoldTilford, 
    IGLayoutReingoldTilfordCircular, IGLayoutSphere, 
    IGLayoutBipartite, IGLayoutPlanar};
Multicolumn[layouts]

1msxhsl8stkut

Visualise a polyhedral graph with all layouts.

g = GraphData["DodecahedralGraph"];
layouts = 
  Graph[#[g], PlotLabel -> #, LabelStyle -> 7] & /@ {IGLayoutCircle, 
    IGLayoutDavidsonHarel, IGLayoutDrL, IGLayoutDrL3D, 
    IGLayoutFruchtermanReingold, IGLayoutFruchtermanReingold3D, 
    IGLayoutGEM, IGLayoutGraphOpt, IGLayoutKamadaKawai, 
    IGLayoutKamadaKawai3D, IGLayoutRandom, IGLayoutSphere, 
    IGLayoutPlanar, IGLayoutTutte};
Multicolumn[layouts]

0kpmon46egwih

Community detection

The following functions are available:

?IGCommunities*

1oe8nwe5be6jc

Concepts

Modularity is defined for a given partitioning of a graph’s vertices into communities. It is defined as

\[Q=\frac{1}{2m}\sum _{i,j} \left(A_{ij}-\frac{k_ik_j}{2m}\right)\delta _{c_ic_j},\]

where \(m\) is the number of edges, \(A\) is the adjacency matrix, \(k_i\) is the degree of node \(i\), and \(c_i\) is the community that node \(i\) belongs to. \(\delta _{ij}\) is the Kronecker \(\delta\) symbol. For weighted graphs, \(A\) is the weighted adjacency matrix, \(k_i\) are the sum of weights of edges incident on node \(i\), and \(m\) is the sum of all weights.

Modularity characterizes the tendency of vertices to connect more within their own group than with other groups. For a given partitioning, it can be computed using IGModularity. Community detection functions find a partitioning of the graph which results in high modularity.

Basic usage and utility functions

Community detection functions return IGClusterData objects.

g = ExampleData[{"NetworkGraph", "FamilyGathering"}]

18lai7ldrga19

cl = IGCommunitiesGreedy[g]

17q5mj1z58qkj

The data available in the object can be queried using IGClusterData[…]["Properties"]. See the Examples section below for more information. In Mathematica 12.0 and later, Information can be used to get a quick human-readable summary.

cl["Properties"]
{"Algorithm", "Communities", "ElementCount", "Elements", \
"HierarchicalClusters", "Merges", "Modularity", "Properties", "Tree"}
cl["Communities"]
{{"Elisabeth", "James", "Anna", "Nancy"}, {"John", "Dorothy", "David",
  "Arlene", "Rudy"}, {"Linda", "Michael", "Nora", "Julia"}, {"Larry",
  "Carol", "Ben", "Oscar", "Felicia"}}
CommunityGraphPlot[g, cl["Communities"], ImageSize -> Medium]

1ftpir3wdnm1x

IGModularity[g, cl]
0.454735

IGClusterData

?IGClusterData

1jjaclmu4pqm0

IGClusterData represents a partitioning of a graph into communities. This object cannot be created directly. It is returned by community detection functions. See the Examples section below for more information.

cl = IGCommunitiesLabelPropagation@
  ExampleData[{"NetworkGraph", "FamilyGathering"}]

03mqqvltnsdn5

Query the available properties.

cl["Properties"]
{"Algorithm", "Communities", "ElementCount", "Elements", \
"Modularity", "Properties"}

Retrieve the communities.

cl["Communities"]
{{"Elisabeth", "James", "Anna", "Linda", "Larry", "Carol", "Nancy", 
 "Ben", "Oscar", "Felicia", "Arlene"}, {"John", "Dorothy", 
 "David"}, {"Michael", "Nora", "Julia"}, {"Rudy"}}

When the "Modularity" property is available, Max[cl["Modularity"]] gives the modularity of the current partitioning.

Max[cl["Modularity"]]
0.264828

IGModularity

?IGModularity

1rxjbuddunhkf

IGModularity[graph, communities] is equivalent to GraphAssortativity[graph, communities, "Normalized" -> False].

IGCompareCommunities

?IGCompareCommunities

1bhxixh692aux

g = ExampleData[{"NetworkGraph", "FamilyGathering"}];
{cl1, cl2} = {IGCommunitiesGreedy[g], IGCommunitiesEdgeBetweenness[g]}

0vphfj5pv2lti

IGCompareCommunities[cl1, cl2]
<|"VariationOfInformation" -> 0.278001, 
"NormalizedMutualInformation" -> 0.899283, "SplitJoinDistance" -> 2, 
"UnadjustedRandIndex" -> 0.947712, "AdjustedRandIndex" -> 0.841942|>

Community detection methods

IGCommunitiesEdgeBetweenness

?IGCommunitiesEdgeBetweenness

13zj33mvmmvpc

IGCommunitiesEdgeBetweenness[] implements the Girvan–Newman algorithm.

Weighted graphs are supported. Weights are treated as “distances”, i.e. a large weight represents a weak connection.

Available option values:

Special properties returned with the result:

References

IGCommunitiesFluid

?IGCommunitiesFluid

0x0q223g07jh5

IGCommunitiesFluid[] implements the fluid communities algorithm.

Reference

IGCommunitiesGreedy

?IGCommunitiesGreedy

0am2gxq2h52bt

IGCommunitiesGreedy[] implements greedy optimization of modularity.

Weighted graphs are supported.

Reference

IGCommunitiesInfoMAP

?IGCommunitiesInfoMAP

0mjey8us8foo3

IGCommunitiesInfoMAP[] implements the InfoMAP algorithm.

It supports both edge weights and vertex weights.

The default number of trials is 10.

Special properties returned with the result:

References

IGCommunitiesLabelPropagation

?IGCommunitiesLabelPropagation

1onxtf0k4c1g8

Weighted graphs are supported.

References

IGCommunitiesLeadingEigenvector

?IGCommunitiesLeadingEigenvector

1az96yq83ecny

Weighted graphs are supported.

Available option values:

References

IGCommunitiesMultilevel

?IGCommunitiesMultilevel

06lmjbweq0buy

IGCommunitiesMultilevel[] implements the Louvain community detection method.

Weighted graphs are supported.

References

IGCommunitiesLeiden

?IGCommunitiesLeiden

1fwm8hiyhx3ro

The Leiden algorithm is similar to the multilevel algorithm, often called the Louvain algorithm, but it is faster and yields higher quality solutions. It can optimize both modularity and the Constant Potts Model, which does not suffer from the resolution-limit (see preprint http://arxiv.org/abs/1104.3083).

The Leiden algorithm consists of three phases: (1) local moving of nodes, (2) refinement of the partition and (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. In the local move procedure in the Leiden algorithm, only nodes whose neighborhood has changed are visited. The refinement is done by restarting from a singleton partition within each cluster and gradually merging the subclusters. When aggregating, a single cluster may then be represented by several nodes (which are the subclusters identified in the refinement).

The Leiden algorithm provides several guarantees. The Leiden algorithm is typically iterated: the output of one iteration is used as the input for the next iteration. At each iteration all clusters are guaranteed to be connected and well-separated. After an iteration in which nothing has changed, all nodes and some parts are guaranteed to be locally optimally assigned. Finally, asymptotically, all subsets of all clusters are guaranteed to be locally optimally assigned.

The Leiden method maximizes a quality measure (a generalization of modularity) defined as

\[Q=\frac{1}{2m}\sum _{i,j}\left(A_{ij}-\gamma n_in_j\right)\delta _{c_ic_j}\]

where \(m\) is the sum of edge weights (number of edges if the graph is unweighted), \(A\) is the weighted adjacency matrix, \(n_i\) is the weight of vertex \(i\), and \(c_i\) is the community that vertex \(i\) belongs to. \(\delta _{ij}\) is the Kronecker \(\delta\) symbol.

\(\gamma\) is a resolution parameter that can be set with the "Resolution" option.

The function chooses the vertex weights automatically, according to the value of the VertexWeight option:

Other available options:

Special properties returned with the result :

Examples:

g = Graph[ExampleData[{"NetworkGraph", "LesMiserables"}], 
   GraphStyle -> "BasicBlack", VertexSize -> 2];

With the default option values VertexWeight -> "NormalizedStrength" and "Resolution" -> 1, IGCommunitiesLeiden effectively uses the modularity as the quality measure.

cl = IGCommunitiesLeiden[g]

0jhhfy7ge8jii

{cl["Quality"], IGModularity[g, cl]}
{0.566298, 0.566298}
HighlightGraph[g, cl["Communities"]]

1xk7ebq5g9mzc

A higher "Resolution" value results in more communities.

HighlightGraph[
 g,
 IGCommunitiesLeiden[g, "Resolution" -> 3]["Communities"]
 ]

0d8k1t9fabr8v

With VertexWeight -> "Constant", it is recommended to set "Resolution" explicitly. A reasonable starting point is GraphDensity[g].

HighlightGraph[
 g,
 IGCommunitiesLeiden[g, VertexWeight -> "Constant", 
   "Resolution" -> 0.1]["Communities"]
 ]

04w3cforeyi2b

References

IGCommunitiesOptimalModularity

?IGCommunitiesOptimalModularity

0zmlpvtwxfz2k

Finds the clustering that maximizes modularity exactly. This algorithm is very slow.

Weighted graphs are supported.

IGCommunitiesSpinGlass

?IGCommunitiesSpinGlass

0exfw0umk0pfu

Weighted graphs are supported.

Option values for Method are:

Option values for "UpdateRule" are: "Simple", "Configuration"

Special properties returned with the result:

References

IGCommunitiesWalktrap

?IGCommunitiesWalktrap

1xbe7h9gioryy

IGCommunitiesWalktrap[] finds communities using short random walks, exploiting the fact that random walks tend to stay within the same cluster.

Weighted graphs are supported.

The default number of steps is 4.

Available option values:

References

Examples

g = ExampleData[{"NetworkGraph", "LesMiserables"}]

1rzdeawm44wbx

IGEdgeWeightedQ[g]
True

Community detection functions return IGClusterData objects.

cl1 = IGCommunitiesEdgeBetweenness[g, "ClusterCount" -> 7]
cl2 = IGCommunitiesWalktrap[g]

1073r3wxsskz3

1sict57um93of

Various properties of these objects can be queried:

cl1["Communities"]
{{"Myriel", "Napoleon", "Mlle Baptistine", "Mme. Magloire", 
 "Countess De Lo", "Geborand", "Champtercier", "Cravatte", "Count", 
 "Old Man"}, {"Labarre", "Valjean", "Marguerite", "Mme. De R", 
 "Isabeau", "Gervais", "Bamatabois", "Perpetue", "Simplice", 
 "Scaufflaire", "Woman1", "Judge", "Champmathieu", "Brevet", 
 "Chenildieu", "Cochepaille"}, {"Tholomyes", "Listolier", "Fameuil", 
 "Blacheville", "Favourite", "Dahlia", "Zephine", 
 "Fantine"}, {"Mme. Thenardier", "Thenardier", "Cosette", "Javert", 
 "Boulatruelle", "Eponine", "Anzelma", "Woman2", "Gueulemer", 
 "Babet", "Claquesous", "Montparnasse", "Toussaint", 
 "Brujon"}, {"Fauchelevent", "Mother Innocent", 
 "Gribier"}, {"Pontmercy", "Gillenormand", "Magnon", 
 "Mlle Gillenormand", "Mme. Pontmercy", "Mlle Vaubois", 
 "Lt. Gillenormand", "Marius", "Baroness T"}, {"Jondrette", 
 "Mme. Burgon", "Gavroche", "Mabeuf", "Enjolras", "Combeferre", 
 "Prouvaire", "Feuilly", "Courfeyrac", "Bahorel", "Bossuet", "Joly", 
 "Grantaire", "Mother Plutarch", "Child1", "Child2", 
 "Mme. Hucheloup"}}

Visualize the detected communities in two different ways:

CommunityGraphPlot[g, cl1["Communities"]]

0lyomu58jvy4k

HighlightGraph[g, Subgraph[g, #] & /@ cl1["Communities"], 
 GraphHighlightStyle -> "DehighlightGray"]

0y5qebiknx6qy

Plot the adjacency matrix, reordered to show the community structure.

IGAdjacencyMatrixPlot[g, Catenate@cl1["Communities"]]

12j0wm6k29xj5

The available properties depend on which algorithm was used for community detection. The following are always present:

These are present for hierarchical clustering methods:

Additionally, the following, and other, algorithm-specific properties may be present:

The "RemovedEdges" property is specific to the "EdgeBetweenness" method, and isn’t present for "Walktrap".

cl1["Properties"]
{"Algorithm", "Bridges", "Communities", "EdgeBetweenness", \
"ElementCount", "Elements", "HierarchicalClusters", "Merges", \
"Properties", "RemovedEdges", "Tree"}
Take[cl1["RemovedEdges"], 10]
{"Valjean" \[UndirectedEdge] "Myriel", 
"Valjean" \[UndirectedEdge] "Mlle Baptistine", 
"Valjean" \[UndirectedEdge] "Mme. Magloire", 
"Gavroche" \[UndirectedEdge] "Valjean", 
"Gavroche" \[UndirectedEdge] "Javert", 
"Thenardier" \[UndirectedEdge] "Fantine", 
"Bamatabois" \[UndirectedEdge] "Javert", 
"Bossuet" \[UndirectedEdge] "Valjean", 
"Montparnasse" \[UndirectedEdge] "Valjean", 
"Gueulemer" \[UndirectedEdge] "Gavroche"}
cl2["Properties"]
{"Algorithm", "Communities", "ElementCount", "Elements", \
"HierarchicalClusters", "Merges", "Modularity", "Properties", "Tree"}

Multiple properties may be retrieved at the same time.

cl2[{"Algorithm", "ElementCount"}]
{"Walktrap", 77}

Compare the two clusterings:

IGCompareCommunities[cl1, cl2]
<|"VariationOfInformation" -> 0.804544, 
"NormalizedMutualInformation" -> 0.786844, "SplitJoinDistance" -> 29,
 "UnadjustedRandIndex" -> 0.879699, "AdjustedRandIndex" -> 0.555464|>

Visualize the hierarchical clustering using the Hierarchical Clustering Package.

<< HierarchicalClustering`
DendrogramPlot[cl1["HierarchicalClusters"], 
 LeafLabels -> (Rotate[#, Pi/2] &), ImageSize -> 750, 
 AspectRatio -> 1/2]

0d1gugy3dxw2r

Hierarchical community structures can also be obtained as a vertex-weighted tree graph.

g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];
cl = IGCommunitiesGreedy[g];
clusteringTree = cl["Tree"]

0znc2wxeuf4hv

{GraphQ[clusteringTree], IGVertexWeightedQ[clusteringTree]}
{True, True}

This tree can be supplied as input to Dendrogram.

Dendrogram[clusteringTree, Left]

0vbdwsg1tvawd

Graph colouring

The graph colouring problem is assigning “colours” or “labels” to the vertices of a graph so that no two adjacent vertices will have the same colour. Similarly, edge colouring assigns colours to edges so that adjacent edges never have the same colour.

IGraph/M represents colours with the integers 1, 2, …. Edge directions and self-loops are ignored.

Fast heuristic colouring

?IGVertexColoring

1tkfl1j8110fe

?IGEdgeColoring

05c804jdho1rx

These function will find a colouring of the graph using a fast heuristic algorithm. The colouring may not be minimal. Edge directions are ignored.

Compute a vertex colouring of a Mycielski graph.

g = GraphData[{"Mycielski", 4}]

00cilx7rp9iwk

IGVertexColoring returns a list of integers, each representing the colour of the vertex that is in the same position in the vertex list.

IGVertexColoring[g]
{4, 3, 1, 1, 3, 1, 2, 2, 2, 2, 2}

Associate the colours with vertex names.

AssociationThread[VertexList[g], IGVertexColoring[g]]
<|1 -> 4, 2 -> 3, 3 -> 1, 4 -> 1, 5 -> 3, 6 -> 1, 7 -> 2, 8 -> 2, 
9 -> 2, 10 -> 2, 11 -> 2|>

Visualize the colours using IGraph/M’s property mapping functionality. See the Property handling functions documentation section for more information.

Graph[g, VertexSize -> 1/3, EdgeStyle -> Gray] //
 
 IGVertexMap[ColorData[97], VertexStyle -> IGVertexColoring]

17j66h9slou47

Visualize an edge colouring of the same graph.

Graph[g, GraphStyle -> "ThickEdge", EdgeStyle -> Opacity[0.7], 
  VertexStyle -> Black] //
 
 IGEdgeMap[ColorData[106], EdgeStyle -> IGEdgeColoring]

0i0nnpynpd5xl

Compute a checkerboard-like colouring of a three-dimensional grid graph.

IGVertexMap[ColorData[97], VertexStyle -> IGVertexColoring, 
 Graph3D@GridGraph[{4, 4, 4}, VertexSize -> 0.8]]

11mp2wicyu1m5

Compute a colouring of a Voronoi mesh.

mesh = VoronoiMesh[RandomReal[1, {20, 2}]]

0lxevt43wp287

col = IGVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2]
{3, 4, 3, 1, 3, 4, 2, 1, 2, 1, 1, 2, 2, 4, 3, 3, 2, 3, 1, 1}
SetProperty[{mesh, {2, All}}, MeshCellStyle -> ColorData[97] /@ col]

1ofjci5jyjxq4

Compute a colouring of the map of African countries.

countries = CountryData["Africa"];
borderingQ[c1_, c2_] := MemberQ[c1["BorderingCountries"], c2]
graph = RelationGraph[borderingQ, countries];
GeoGraphics@
 MapThread[{GeoStyling[{Opacity[0.5], #2}], 
    Polygon[#1]} &, {countries, 
   ColorData[97] /@ IGVertexColoring[graph]}]

1a1t1qozfz8g8

\(k\)-colouring

?IGKVertexColoring

11yh5wbj5iglt

?IGKEdgeColoring

11cvel1p7mzmd

These functions find a colouring with \(k\) or fewer colours. They work by transforming the colouring into a satisfiability problem and using SatisfiabilityInstances.

The available option values are:

The default setting for "ForcedColoring" is "MaxDegreeClique".

The Moser spindle is not 3-colourable, so no solution is returned.

moser = GraphData["MoserSpindle"];
IGKVertexColoring[moser, 3]
{}

Find a 4-colouring of the Moser spindle …

IGKVertexColoring[moser, 4]
{{4, 1, 3, 1, 3, 2, 2}}

… and visualize it.

Graph[moser, GraphStyle -> "BasicBlack", VertexSize -> Large] // 
 IGVertexMap[ColorData[112], 
  VertexStyle -> (First@IGKVertexColoring[#, 4] &)]

0rh1g24xqlw8a

Find a 4-edge-colouring of the Petersen graph.

PetersenGraph[GraphStyle -> "ThickEdge", EdgeStyle -> Opacity[2/3]] //
  IGEdgeMap[ColorData[112], 
  EdgeStyle -> (First@IGKEdgeColoring[#, 4] &)]

0k0w05b8rsibj

The following examples illustrate the use of the "ForcedColoring" option. The 6th order Mycielski graph has chromatic number 6. A 6-colouring is easily found even with "ForcedColoring" -> None.

g = GraphData[{"Mycielski", 6}];
IGKVertexColoring[g, 6, "ForcedColoring" -> None] // Timing
{0.011646, {{6, 4, 5, 5, 4, 4, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 
  3, 3, 3, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
  2, 2, 2, 2, 2, 1}}}

However, showing that the graph is not 5-colourable takes considerably longer.

TimeConstrained[IGKVertexColoring[g, 5, "ForcedColoring" -> None], 5]
$Aborted

Forcing colours in the appropriate way reduces the computation time significantly.

IGKVertexColoring[g, 5, 
  "ForcedColoring" -> "MaxDegreeClique"] // Timing
{0.307734, {}}

Minimum colouring

?IGMinimumVertexColoring

09ulxoyd6h6ma

?IGMinimumEdgeColoring

1wsraqpgjrci0

IGMinimumVertexColoring and IGMinimumEdgeColoring find minimum colourings of graphs, i.e. they find a colouring with the fewest possible number of colours. The current implementation tries successively larger \(k\)-colourings until it is successful.

IGMinimumVertexColoring and IGMinimumEdgeColoring can use the same "ForcedColoring" option values as IGKVertexColoring and IGKEdgeColoring.

WheelGraph[7, GraphStyle -> "BasicBlack", VertexSize -> Large] // 
 IGVertexMap[ColorData[97], VertexStyle -> IGMinimumVertexColoring]

0gcb88eurgmsx

Find a colouring of a large graph.

IGMinimumVertexColoring@RandomGraph[{100, 400}]
{2, 2, 2, 4, 4, 3, 4, 3, 1, 3, 2, 3, 1, 2, 2, 1, 3, 2, 4, 3, 4, 2, 4, \
3, 2, 3, 2, 2, 1, 2, 1, 3, 1, 4, 2, 4, 3, 4, 3, 4, 3, 2, 4, 2, 2, 3, \
3, 1, 4, 4, 4, 2, 1, 4, 1, 3, 2, 1, 4, 2, 1, 4, 4, 3, 1, 1, 3, 3, 3, \
1, 1, 2, 4, 4, 2, 3, 3, 4, 3, 1, 4, 1, 1, 3, 4, 2, 4, 3, 3, 4, 1, 4, \
2, 1, 2, 1, 1, 1, 1, 1}

Implement a multipartite graph layout: vertex colouring is equivalent to partitioning the vertices of the graph into groups such that all connections run between different groups, and never within the same group. The colours can be thought of as the indices of groups. IGMembershipToPartitions can be used to convert from a group-index (i.e. membership) representation to a partition representation.

multipartiteLayout[g_?GraphQ, separation : _?NumericQ : 1.5, 
   opt : OptionsPattern[]] := 
  Module[{n, partitions, partitionSizes, vertexCoordinates},
   partitions = IGMembershipToPartitions[g]@IGMinimumVertexColoring[g];
   partitionSizes = Length /@ partitions;
   n = Length[partitions];
   vertexCoordinates = 
    With[{hl = N@Sin[Pi/n], 
      ir = separation If[n == 2, 1/2, N@Cos[Pi/n]]},
     Catenate@Table[
       RotationTransform[2 Pi/n k][{#, ir} & /@ 
         Subdivide[-hl, hl, partitionSizes[[k]] - 1]],
       {k, 1, n}
       ]
     ];
   IGReorderVertices[Catenate[partitions], g, 
    VertexCoordinates -> vertexCoordinates, opt]
   ];

Lay out a bipartite graph.

g = IGBipartiteGameGNM[10, 10, 30];
multipartiteLayout[g]

1tbcemknnhnzd

Lay out multipartite graphs.

g = RandomGraph[{40, 40}];
multipartiteLayout[g]

19mt5l7iks3e5

g = RandomGraph[{40, 160}];
multipartiteLayout[g, GraphStyle -> "BasicBlack", 
 EdgeStyle -> Opacity[0.2]]

1anarbuselg0w

Compute a minimum colouring of a triangulation. It can be shown, e.g. based on Brooks’s theorem, that any triangulation of a polygon is 3-colourable.

mesh = DelaunayMesh[RandomReal[1, {20, 2}], 
   MeshCellStyle -> {1 -> Black}];
col = IGMinimumVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2];
SetProperty[{mesh, {2, All}}, MeshCellStyle -> ColorData[97] /@ col]

1b3t2opvkl8hj

Find a minimum edge colouring of a graph.

Graph[
  GraphData["SixteenCellGraph"],
  GraphStyle -> "ThickEdge", EdgeStyle -> Opacity[2/3]
  ] //
 IGEdgeMap[
  ColorData[104],
  EdgeStyle -> IGMinimumEdgeColoring
  ]

1x0ue2t74oc2o

Chromatic number

?IGChromaticNumber

1od8a98olk63p

?IGChromaticIndex

0mrisz9vrlkza

The chromatic number of a graph is the smallest number of colours needed to colour its vertices. The chromatic index, or edge chromatic number, is the smallest number of colours needed to colour its edges.

Find the chromatic number and chromatic index of a graph.

g = GraphData["IcosahedralGraph"]

0f8e3s3cyr5ch

{IGChromaticNumber[g], IGChromaticIndex[g]}
{4, 5}

The implementation of IGChromaticNumber and IGChromaticIndex is effectively the following:

{Max@IGMinimumVertexColoring[g], Max@IGMinimumEdgeColoring[g]}
{4, 5}

Perfect graphs

?IGPerfectQ

0ha61ldokqns9

IGPerfectQ tests if a graph is perfect. The clique number and the chromatic number is the same for every induced subgraph of a perfect graph.

The current implementation of IGPerfectQ uses the strong perfect graph theorem: it checks that neither the graph nor its complement have a graph hole of odd length.

g = GraphData[{"GeneralizedQuadrangle", {2, 1}}]

1bjc31x7qj8mh

IGPerfectQ[g]
True

The clique number and the chromatic number is the same for every induced subgraph.

AllTrue[
 Subgraph[g, #] & /@ Subsets@VertexList[g],
 IGCliqueNumber[#] == IGChromaticNumber[#] &
 ]
True

Utility functions

?IGVertexColoringQ

1pf4zt1vp2tb6

IGVertexColoringQ checks whether neighbouring vertices of a graph are assigned different colours.

The colours may be given as a list, with the same ordering as VertexList[graph].

07ijntov0q0ux

True

0axsax7gjcifc

False

The colours may also be given as an association from vertices to colours.

1whz3890wv1h3

True

Any expression may be used for the colours, not only integers.

1sjd8n69bbwpy

True

Processes on graphs

Random walks

IGRandomWalk

?IGRandomWalk

00l9ic3hmp07j

IGRandomWalk[] takes a random walk over a directed or undirected graph. If the graph is weighted, the next edge to traverse is selected with probability proportional to its weight.

The available options are:

Traversing self-loops in different directions is considered as distinct probabilities in an undirected graph. Thus vertices 1 and 3 are visited more often in the below graphs than vertex 2:

g = Graph[{1 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 
   2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 3}, 
  VertexLabels -> "Name"]

0pccnbf4gshjx

IGRandomWalk[g, 1, 100000] // Counts // KeySort
<|1 -> 37456, 2 -> 24972, 3 -> 37572|>

This is consistent with their degrees:

VertexDegree[g]
{3, 2, 3}

Convert the graph to a directed version to traverse self-loops only in one direction.

dg = DirectedGraph[g]

0iwrh0rrivyg0

{VertexOutDegree[dg], VertexInDegree[dg]}
{{2, 2, 2}, {2, 2, 2}}
IGRandomWalk[dg, 1, 100000] // Counts // KeySort
<|1 -> 33246, 2 -> 33326, 3 -> 33428|>

If the walker gets stuck, a list shorter than steps will be returned. This may happen in a non-connected directed graph, or in a single-vertex graph component.

IGRandomWalk[IGEmptyGraph[1], 1, 10]
{1}
IGRandomWalk[Graph[{1 -> 2}], 1, 10]
{1, 2}

How much time does a random walker spend on each node of a network?

g = IGBarabasiAlbertGame[50, 2, DirectedEdges -> False]

1cgm05e3b7np4

counts = Counts@IGRandomWalk[g, First@VertexList[g], 10000] /@ 
  VertexList[g]
{437, 662, 736, 318, 275, 594, 284, 582, 229, 101, 390, 86, 113, 200, \
346, 189, 183, 194, 104, 144, 85, 147, 98, 228, 91, 255, 103, 105, \
99, 184, 149, 157, 111, 160, 153, 150, 78, 115, 101, 198, 101, 83, \
97, 103, 132, 87, 169, 115, 91, 88}

The exact answer can be computed as the leading eigenvector of the process’s stochastic matrix:

13lu4yhrvvnvy

Compare the exact answer with a finite sample:

1lgdmidcgo1zm

1ersy3lvx1hdm

Random walk on a square grid.

grid = IGSquareLattice[{50, 50}];
counts = Counts@IGRandomWalk[grid, 1, 5000];
Graph[grid,
 VertexStyle ->
  Prepend[
   Normal[ColorData["SolarColors"] /@ Normalize[counts, Max]],
   Black (* colour of unvisited nodes, i.e. default colour *)
   ],
 EdgeShapeFunction -> None,
 Background -> Black
 ]

1o1azsx4iwryg

The fraction of nodes reached after \(n\) steps on a grid and a comparable random regular graph.

nodesReached[graph_] := 
 Length@Union@IGRandomWalk[graph, 1, VertexCount[graph]]/
  VertexCount[graph]
grid = IGSquareLattice[{50, 50}, "Periodic" -> True];
regular = IGKRegularGame[50^2, 4];
Table[
   {nodesReached[grid], nodesReached[regular]},
   {5000}
   ] // Transpose // Histogram

1wv4wqbw3j6az

Generate random spanning trees using loop erased random walks.

randomSpanningTree[graph_?GraphQ] :=
 
 Module[{visited = <||>, i = 2, k = 1, 
   batchSize = 2 VertexCount[graph], walk},
  walk = IGRandomWalk[graph, RandomChoice@VertexList[graph], 
    batchSize];
  visited[walk[[1]]] = True;
  While[k < VertexCount[graph],
      (* register a traversed edge only when it leads to a yet \
unvisited vertex *)
      If[! TrueQ[visited[walk[[i]]]],
       Sow[walk[[i - 1]] \[UndirectedEdge] walk[[i]]];
       visited[walk[[i]]] = True;
       k++
       ];
      i++;
      (* if the walk has not yet visited all vertices, keep walking *)

            If[i > Length[walk],
       walk = 
        Join[walk, Rest@IGRandomWalk[graph, Last[walk], batchSize]]
       ];
      ] // Reap // Last // First
  ]

By taking random spanning trees of spatially embedded planar graphs, we can generate mazes.

0q2wjzixfekjq

0xi9sde26m4nd

1lr4rtkm8b1ih

1x7kf55cueufv

Take a sample of a large graph using a random walk. The following graph is too large to easily visualize, but visualizing a random-walk-based sample immediately shows signs of a community structure.

g = ExampleData[{"NetworkGraph", "AstrophysicsCollaborations"}];
{VertexCount[g], VertexCount@IGGiantComponent[g]}
{16706, 14845}
Subgraph[g, 
 IGRandomWalk[g, RandomChoice@VertexList@IGGiantComponent[g], 200]]

0eb3o964295zt

CommunityGraphPlot[%]

1jm4ugu9e09e4

IGRandomEdgeWalk and IGRandomEdgeIndexWalk

?IGRandomEdgeWalk

18jwfa0pfwzvi

?IGRandomEdgeIndexWalk

1ruvuuqa50pho

IGRandomEdgeWalk takes a random walk on a graph and returns the list of traversed edges. If the graph is weighted, the next edge to traverse is selected with probability proportional to its weight.

The available options are:

Take a random walk on a De Bruijn graph, and retrieve the traversed edges.

g = IGDeBruijnGraph[3, 3];
IGRandomEdgeWalk[g, RandomChoice@VertexList[g], 20]
{16 \[DirectedEdge] 21, 21 \[DirectedEdge] 9, 9 \[DirectedEdge] 26, 
26 \[DirectedEdge] 22, 22 \[DirectedEdge] 12, 12 \[DirectedEdge] 7, 
7 \[DirectedEdge] 19, 19 \[DirectedEdge] 3, 3 \[DirectedEdge] 9, 
9 \[DirectedEdge] 27, 27 \[DirectedEdge] 26, 26 \[DirectedEdge] 22, 
22 \[DirectedEdge] 11, 11 \[DirectedEdge] 5, 5 \[DirectedEdge] 13, 
13 \[DirectedEdge] 10, 10 \[DirectedEdge] 1, 1 \[DirectedEdge] 3, 
3 \[DirectedEdge] 8, 8 \[DirectedEdge] 24}

IGRandomEdgeIndexWalk returns the list of indices of the traversed edges instead. This makes it useful for working with multigraphs, as it allows distinguishing between parallel edges.

As an example application, let us consider the following set of affine transformations:

10pxht23th7ly

trafos = {a11, a21, b21, a12, a22};

Let us visualize them by showing an initial (black) triangle and its (red) transformation.

07y3peyytna53

09b2epgwdirpd

These transformations describe the mutual self-similarity structure of two fractal curves, according to the following directed graph. Each edge of the graph corresponds to a transformation.

1ulfp9ks0nhnu

1abwe0yi9ov1b

Let us compute a random walk on this graph, and iteratively apply transformations to the point {0, 0} according to the traversed edges.

walk = IGRandomEdgeIndexWalk[graph, 1, 20000];
pts = Rest@FoldList[#2[#1] &, {0., 0.}, trafos[[walk]]];

The resulting list of points will approximate the union of the two fractal curves.

Image@Graphics[{AbsolutePointSize[1], Point[pts]}]

1uouls2z99s60

The two curves can be separated by filtering points according to which graph vertex the corresponding directed edge targets. For example, if the point was generated by a transformation corresponding to 1 \[DirectedEdge] 2, it will belong to curve 2.

targets = Last /@ EdgeList[graph]
{1, 1, 1, 2, 2}
Image@Graphics[{AbsolutePointSize[1], 
   Point@Pick[pts, targets[[walk]], 1]}]

10t94emw53yc2

Image@Graphics[{AbsolutePointSize[1], 
   Point@Pick[pts, targets[[walk]], 2]}]

1ff7etjez1bfi

The technique described here is taken from “Generating self-affine tiles and their boundaries” by Mark McClure.

Epidemic models

IGSIRProcess

?IGSIRProcess

0nee4dkl7j8eb

IGSIRProcess simulates a stochastic version of the well known SIR model of disease spreading. In this model, each node of the network may be in one of three states: susceptible, infected or recovered, denoted by \(S\), \(I\) and \(R\), respectively. A susceptible node with \(k\) infected neighbours becomes infected with rate \(k \beta\), while an infected node recovers with rate \(\gamma\). At the start of the simulation, a random node is chosen to be infected. The simulation runs until no more infected nodes are left.

When performing a single simulation, IGSIRProcess returns a TimeSeries expression of {s, i, r} values. When multiple runs are requested, the resulting time series are combined into a TemporalData expression.

g = IGWattsStrogatzGame[100, 0.05];

Perform a single SIR simulation:

ts = IGSIRProcess[g, {5, 1}]

0le95pqztmtqi

Plot the results with a legend:

ListLinePlot[ts, PlotLegends -> ts["ComponentNames"]]

0vol7wft04l19

Plot only the number of infected nodes:

(* In Mathematica 12.0 and later,
   ts["PathComponent", "I"] can also be used. *)
ListLinePlot[
 ts["PathComponent", 2],
 AxesLabel -> {"time", "infected"}, PlotStyle -> ColorData[97][2]]

0gmip20rjz6cn

Find the number of susceptible, infected and recovered nodes at a specific time point:

ts[1.0]
{11., 63., 26.}

The ResamplingMethod of the TimeSeries object is set to 0th order interpolation, therefore the last value is used beyond the last available time point.

ts[10]

1szlgkykaj56k

{0., 0., 100.}

Perform 100 simulations simultaneously:

td = IGSIRProcess[g, {5, 1}, 100]

0w2ulpqxglbb8

Plot the median number of susceptible, infected and recovered nodes:

Show[
    ListLinePlot[#, PlotStyle -> GrayLevel[0, 0.1], 
     PlotRange -> {0, VertexCount[g]}],
    Quiet@Plot[Median[#[t]], {t, 0, 4}, PlotStyle -> Red]
    ] & /@ td["PathComponents"] // GraphicsColumn

14y0vj0u72gfe

The sum of the three components, \(S+I+R\), always equals the total number of graph nodes.

First@Normal@Total[td["PathComponents"]] // Short

1fobaxb32k7ut

In the next example, we compare epidemic spreading on a periodic grid, i.e. a network that only has spatially local connections, with a rewired version of the same network which also includes long range links. We rewire 5% of links while ensuring that the graph stays connected.

g1 = IGSquareLattice[{30, 30}, "Periodic" -> True];
g2 = IGTryUntil[IGConnectedQ][IGRewireEdges[g1, 0.05]];

Generate 1000 simulations for each network.

r1 = IGSIRProcess[g1, {1, 1}, 1000];
r2 = IGSIRProcess[g2, {1, 1}, 1000];

Plot the histogram of the total duration of the epidemic.

Histogram[{r1["LastTimes"], r2["LastTimes"]}, 
 ChartLegends -> {"grid", "rewired"}]

05dlsdzkpd5rk

Plot the fraction of recovered nodes at the end of the epidemic.

tmax = Max[r1["MaximumTime"], r2["MaximumTime"]];
Histogram[
 {r1["PathComponent", 3]["SliceData", tmax]/VertexCount[g1],
   r2["PathComponent", 3]["SliceData", tmax]/VertexCount[g2]} // Quiet,
 {0, 1, 0.02},
 ChartLegends -> {"grid", "rewired"}
 ]

1mc89ognctcik

Planar graphs

A graph is said to be planar if it can be drawn in the plane without edge crossings.

A useful concept when working with planar graphs is their combinatorial embedding. A combinatorial embedding of a graph is a counter-clockwise ordering of the incident edges around each vertex. IGraph/M represents combinatorial embeddings as associations from vertices to an ordering of their neighbours. Currently, only embeddings of simple graphs are supported.

Some of the planar graph functionality makes use of the LEMON Graph Library.

IGPlanarQ

?IGPlanarQ

0706lsrqy3y87

IGPlanarQ[graph] checks if a graph is planar using the Boyer–Myrvold algorithm.

IGPlanarQ@GraphData[{"Apollonian", 6}]
True
IGPlanarQ@CompleteGraph[5]
False

IGPlanarQ[embedding] checks if a combinatorial embedding is planar. The following are both embeddings of the \(K_4\) complete graph. However, only the first one is planar.

emb1 = <|1 -> {2, 3, 4}, 2 -> {1, 4, 3}, 3 -> {2, 4, 1}, 
   4 -> {3, 2, 1}|>;
emb2 = <|1 -> {2, 4, 3}, 2 -> {4, 3, 1}, 3 -> {1, 2, 4}, 
   4 -> {3, 1, 2}|>;
IGPlanarQ /@ {emb1, emb2}
{True, False}

The second embedding generates only 2 faces instead of 4, which can be embedded on a torus, but not in the plane (or on a sphere).

Length /@ IGFaces /@ {emb1, emb2}
{4, 2}

Unlike the built-in PlanarGraphQ, IGPlanarQ considers the null graph to be planar.

{IGPlanarQ@IGEmptyGraph[], PlanarGraphQ@IGEmptyGraph[]}
{True, True}

IGMaximalPlanarQ

?IGMaximalPlanarQ

0nbwgpveoct2d

A simple graph is maximal planar if no new edges can be added to it without breaking planarity. Maximal planar graphs are sometimes called triangulated graphs or triangulations.

The 3-cycle is maximal planar.

IGMaximalPlanarQ[CycleGraph[3]]
True

The 4-cycle is not because a chord can be added to it without breaking planarity.

IGMaximalPlanarQ[CycleGraph[4]]
False
IGPlanarQ[EdgeAdd[CycleGraph[4], 1 \[UndirectedEdge] 3]]
True

Apollonian graphs are maximal planar.

g = GraphData[{"Apollonian", 2}]

1h3eozez4tnfv

IGMaximalPlanarQ[g]
True

All faces of a maximal planar graph are triangles.

Length /@ IGFaces[g]
{3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

Therefore the edge count \(E\) and the face count \(F\) of a maximal planar graph on more than 2 vertices satisfy \(2E=3F\). Each edge is incident to two faces and each face is incident to three edges.

{2 EdgeCount[g], 3 Length@IGFaces[g]}
{30, 30}

IGOuterplanarQ

?IGOuterplanarQ

1570tn5xi48j6

IGOuterplanarQ[graph] checks if a graph is outerplanar, i.e. if it can be drawn in the plane without edge crossings and with all vertices being on the outer face.

Outerplanar graphs are also called circular planar. They can be drawn without edge crossings and all vertices on a circle. See the documentation of IGOuterplanarEmbedding for an example.

1x34ovf4bmqqz

False

0if4am3mfgphz

True

IGOuterplanarQ[embedding] checks if a combinatorial embedding is outerplanar. Not all planar embeddings of an outerplanar graph are also outerplanar embeddings.

Consider the following outerplanar graph …

g = IGShorthand["0-1-2-3-4-2,1-4"]

0kln9qbtobcma

IGOuterplanarQ[g]
True

… and two of its embeddings:

emb1 = <|0 -> {1}, 1 -> {2, 0, 4}, 2 -> {1, 3, 4}, 3 -> {2, 4}, 
   4 -> {3, 1, 2}|>;
emb2 = <|0 -> {1}, 1 -> {0, 2, 4}, 2 -> {1, 3, 4}, 3 -> {2, 4}, 
   4 -> {3, 1, 2}|>;

They are both planar, but only the second one is outerplanar.

IGPlanarQ /@ {emb1, emb2}
{True, True}
IGOuterplanarQ /@ {emb1, emb2}
{False, True}
Graph[g, VertexCoordinates -> IGEmbeddingToCoordinates[#]] & /@ {emb1,
   emb2}

1mejm00zntkyg

IGKuratowskiEdges

?IGKuratowskiEdges

1bswh0rjd55x7

IGKuratowskiEdges finds a Kuratowski subgraph of a non-planar graph. The subgraph is returned as a set of edges. If the graph is planar, {} is returned.

According to Kuratowski’s theorem, any non-planar graph contains a subgraph homeomorphic to the \(K_5\) complete graph or the \(K_{3,3}\) complete bipartite graph. This is called a Kuratowski subgraph.

Generate a random graph, which is non-planar with high probability.

g = RandomGraph[{20, 40}]

1ob6b5mc0u4g9

IGPlanarQ[g]
False

Compute a set of edges belonging to a Kuratowski subgraph.

kur = IGKuratowskiEdges[g]
{18 \[UndirectedEdge] 19, 16 \[UndirectedEdge] 18, 
13 \[UndirectedEdge] 17, 12 \[UndirectedEdge] 17, 
12 \[UndirectedEdge] 15, 11 \[UndirectedEdge] 13, 
10 \[UndirectedEdge] 16, 10 \[UndirectedEdge] 15, 
7 \[UndirectedEdge] 12, 3 \[UndirectedEdge] 19, 
3 \[UndirectedEdge] 7, 2 \[UndirectedEdge] 18, 
2 \[UndirectedEdge] 15, 2 \[UndirectedEdge] 13, 
1 \[UndirectedEdge] 11, 1 \[UndirectedEdge] 10}

Highlight the Kuratowski subgraph.

HighlightGraph[g, Graph[kur]]

1wtd6otic29my

Display the Kuratowski subgraph on its own.

Graph[kur]

1w9pba6fc0wgr

By smoothening the Kuratowski subgraph, we obtain either \(K_5\) or \(K_{3,3}\).

IGSmoothen@Graph[kur]

0z8wa6oywludw

IGHomeomorphicQ[Graph[kur], #] & /@ {CompleteGraph[5], 
  CompleteGraph[{3, 3}]}
{False, True}

For planar graphs, {} is returned.

IGKuratowskiEdges@CycleGraph[5]
{}

IGFaces

?IGFaces

11x5w8b8o3a3k

IGFaces returns the faces of a planar graph, or the faces corresponding to a specific (not necessarily planar) embedding. The faces are represented by a counter-clockwise ordering of vertices. The current implementation ignores self-loops and multi-edges.

The faces of a planar graph are unique if the graph is 3-vertex-connected. This can be checked using KVertexConnectedGraphQ.

g = GraphData["DodecahedralGraph"]

0ae6wxawc635b

IGFaces[g]
{{1, 14, 9, 10, 15}, {1, 15, 4, 8, 16}, {1, 16, 7, 3, 14}, {2, 5, 11, 
 12, 6}, {2, 6, 20, 18, 13}, {2, 13, 17, 19, 5}, {3, 7, 11, 5, 
 19}, {3, 19, 17, 9, 14}, {4, 15, 10, 18, 20}, {4, 20, 6, 12, 8}, {7,
  16, 8, 12, 11}, {9, 17, 13, 18, 10}}
KVertexConnectedGraphQ[g, 3]
True

If the graph is not connected and has \(C\) connected components, then \(C-1\) faces will be redundant.

g = IGDisjointUnion[{CycleGraph[3], CycleGraph[3]}, 
  VertexLabels -> Automatic]

15myf0w85gqv0

IGFaces[g]
{{{1, 1}, {1, 2}, {1, 3}}, {{1, 1}, {1, 3}, {1, 2}}, {{2, 1}, {2, 
  2}, {2, 3}}, {{2, 1}, {2, 3}, {2, 2}}}

In the above-drawn arrangement, the outer faces of the two triangles are the same face. However, one triangle could have been drawn inside of the other. Then the inner face of one would be the same as the outer face of the other. Thus the choice of faces to be eliminated as redundant is arbitrary, and is left up to the user.

IGFaces can also be used with a non-planar combinatorial embedding. The below embeddings both belong to the 4-vertex complete graph, however, only the first is planar.

emb1 = <|1 -> {2, 3, 4}, 2 -> {1, 4, 3}, 3 -> {2, 4, 1}, 
   4 -> {3, 2, 1}|>;
emb2 = <|1 -> {2, 4, 3}, 2 -> {4, 3, 1}, 3 -> {1, 2, 4}, 
   4 -> {3, 1, 2}|>;
IGFaces[emb1]
{{1, 2, 3}, {1, 3, 4}, {1, 4, 2}, {2, 4, 3}}
IGFaces[emb2]
{{1, 2, 3, 1, 4, 3, 2, 4}, {1, 3, 4, 2}}

Determine the genus \(g\) of an embedding belonging to a connected graph based on its face count \(F\), vertex count \(V\), and edge count \(E\), using the formula for the Euler characteristic \(2g-2=\chi =V-E+F\).

genus[emb_?
   IGEmbeddingQ] := (2 + Total[Length /@ emb]/2 - Length[emb] - 
    Length@IGFaces[emb])/2
genus /@ {emb1, emb2}
{0, 1}

IGDualGraph

?IGDualGraph

0dqjndzocp9ra

IGDualGraph returns a dual graph of a planar graph, or the dual corresponding to a specific embedding. The ordering of the dual graph’s vertices is consistent with the result of IGFaces.

Limitations:

The dual of a simple 3-vertex-connected graph is simple and unique, thus such graphs are not affected by the above limitations.

TableForm[
 Table[{CompleteGraph[k], IGDualGraph@CompleteGraph[k]}, {k, 1, 4}],
 TableHeadings -> {None, {"graph", "dual"}}
 ]

1eox2orsmigwj

Currently, if the input is a graph, it must be planar.

IGDualGraph[CompleteGraph[5]]

1ejq6eg1tc943

$Failed

If the input is a combinatorial embedding, it does not need to be planar.

emb = <|1 -> {2, 4, 3}, 2 -> {4, 3, 1}, 3 -> {1, 2, 4}, 
   4 -> {3, 1, 2}|>;
IGPlanarQ[emb]
False
IGDualGraph[emb]

0jbprjlilnx9v

Find the dual of a square lattice graph. The dual graph also includes the outer face as a vertex.

IGSquareLattice[{5, 5}]

0ofva8o8gj8c0

IGDualGraph[%]

1gbijqspxu05w

The dual is unique if the graph is 3-vertex-connected. This can be verified using KVertexConnectedGraphQ. In this case, IGDualGraph@IGDualGraph[g] is isomorphic to g.

g = GraphData["IcosahedralGraph"]

0f8e3s3cyr5ch

dg = IGDualGraph[g]

13mlsuuixim8j

IGIsomorphicQ[dg, GraphData["DodecahedralGraph"]]
True
IGIsomorphicQ[IGDualGraph[dg], g]
True

If the graph is not connected, the dual of each component is effectively computed separately.

IGDualGraph@IGDisjointUnion[{CycleGraph[3], CycleGraph[3]}]

17sjdmz6upm9a

IGEmbeddingQ

?IGEmbeddingQ

0rav2oeix5acz

IGEmbeddingQ checks if an embedding is valid, and whether it belongs to a graph without self-loops and multi-edges.

This is a valid combinatorial embedding of the graph 1 \[UndirectedEdge] 3 \[UndirectedEdge] 2.

IGEmbeddingQ[<|1 -> {3}, 2 -> {3}, 3 -> {1, 2}|>]
True

The following embeddings do not belong to simple (i.e. loop free and multi-edge free) graphs:

IGEmbeddingQ[<|1 -> {3}, 2 -> {3, 3}, 3 -> {1, 2, 2}|>]
False
IGEmbeddingQ[<|1 -> {1, 2}, 2 -> {1}|>]
False

The following embedding is not valid because it does not contain the arc 2 \[DirectedEdge] 1 but it does contain 1 \[DirectedEdge] 2.

IGEmbeddingQ[<|1 -> {2}, 2 -> {}|>]
False

IGPlanarEmbedding

?IGPlanarEmbedding

1kza47mseirel

IGPlanarEmbedding computes a combinatorial embedding of a planar graph. The current implementation ignores self-loops and multi-edges.

g = IGShorthand["a:b:c:d -- a:b:c:d"]

1tht714pdcz0f

emb = IGPlanarEmbedding[g]
<|"a" -> {"b", "c", "d"}, "b" -> {"a", "d", "c"}, 
"c" -> {"b", "d", "a"}, "d" -> {"c", "b", "a"}|>

The representation of a combinatorial embedding is also a valid adjacency list, thus it can be easily converted back to an undirected graph using IGAdjacencyGraph.

IGAdjacencyGraph[emb, VertexLabels -> Automatic]

106nf4iotkije

IGOuterplanarEmbedding

?IGOuterplanarEmbedding

14aggc1qwwlg8

IGOuterplanarEmbedding returns an outerplanar combinatorial embedding of a graph, if it exists. If the corresponding graph is connected, then one face of such an embedding contains all vertices of the graph.

g = IGTriangularLattice[{5, 2}]

1pguiilkqp7se

emb = IGOuterplanarEmbedding[g]
<|1 -> {6, 2}, 2 -> {1, 6, 7, 8, 3}, 3 -> {2, 8, 4}, 
4 -> {3, 8, 9, 10, 5}, 5 -> {4, 10}, 6 -> {2, 1, 7}, 7 -> {6, 8, 2}, 
8 -> {7, 9, 4, 3, 2}, 9 -> {8, 10, 4}, 10 -> {9, 5, 4}|>
IGLayoutCircle@
 IGReorderVertices[First@MaximalBy[Length]@IGFaces[emb], g]

0tjf0jt3tat9l

IGCoordinatesToEmbedding

?IGCoordinatesToEmbedding

0ispctuszk9ng

IGCoordinatesToEmbedding computes a combinatorial embedding, i.e. a cyclic ordering of neighbours around each vertex, based on the given vertex coordinates. By default, the coordinates are taken from the VertexCoordinates property.

g = CompleteGraph[4, VertexLabels -> "Name"]

0qru914kbp5vg

emb = IGCoordinatesToEmbedding[g]
<|1 -> {4, 2, 3}, 2 -> {3, 1, 4}, 3 -> {4, 1, 2}, 4 -> {2, 1, 3}|>

The embedding can then be used to compute the faces of the graph …

IGFaces[emb]
{{1, 4, 2}, {1, 2, 3}, {1, 3, 4}, {2, 4, 3}}

… or can be converted back to coordinates.

Graph[g, VertexCoordinates -> IGEmbeddingToCoordinates[emb]]

18gu8bxortkel

If we start with a non-planar graph layout, the embedding will not be planar either.

g = CompleteGraph[4, GraphLayout -> "SpringElectricalEmbedding", 
  VertexLabels -> "Name"]

0xnbj2cglrgb1

emb = IGCoordinatesToEmbedding[g]
<|1 -> {2, 3, 4}, 2 -> {1, 3, 4}, 3 -> {4, 2, 1}, 4 -> {2, 1, 3}|>
IGFaces[emb]
{{1, 2, 4, 3}, {1, 3, 2, 1, 4, 2, 3, 4}}
IGPlanarQ[emb]
False

IGEmbeddingToCoordinates

?IGEmbeddingToCoordinates

1wkre0cx3tt6u

IGEmbeddingToCoordinates computes the coordinates of a straight-line planar drawing based on the given combinatorial embedding, using Schnyder’s algorithm.

emb1 = <|1 -> {2, 3, 4}, 2 -> {1, 4, 3}, 3 -> {2, 4, 1}, 
   4 -> {3, 2, 1}|>;
IGEmbeddingToCoordinates[emb1]
{{1, 1}, {1, 0}, {2, 1}, {0, 2}}

The embedding must be planar.

emb2 = <|1 -> {2, 4, 3}, 2 -> {4, 3, 1}, 3 -> {1, 2, 4}, 
   4 -> {3, 1, 2}|>;
IGPlanarQ[emb2]
False
IGEmbeddingToCoordinates[emb2]

1a5uesetx14cr

$Failed

IGLayoutPlanar

?IGLayoutPlanar

19h1vou0br6d4

IGLayoutPlanar computes a layout of a planar graph without edge crossings using Schnyder’s algorithm. The vertex coordinates will lie on an \((n-2) \times (n-2)\) integer grid, where \(n\) is the number of vertices.

Create a random planar graph and lay it out without edge crossings.

g = IGTryUntil[IGPlanarQ]@
  RandomGraph[{10, 20}, VertexLabels -> "Name"]

0sox8ziogshux

IGLayoutPlanar[g]

0zlzufsum8l9m

IGLayoutPlanar produces a drawing based on the combinatorial embedding returned IGPlanarEmbedding. A combinatorial embedding is a counter-clockwise ordering of the incident edges around each vertex.

emb = IGPlanarEmbedding[g]
<|1 -> {2, 9, 4, 5}, 2 -> {1, 5, 7, 10, 4, 3, 8, 6}, 3 -> {2, 8}, 
4 -> {2, 10, 7, 5, 1, 8}, 5 -> {4, 2, 1}, 6 -> {2, 8, 9}, 
7 -> {4, 10, 2}, 8 -> {6, 2, 3, 4, 9}, 9 -> {8, 1, 6}, 
10 -> {7, 4, 2}|>

The embedding can also be used to directly compute coordinates for a drawing.

IGEmbeddingToCoordinates[emb]
{{4, 2}, {1, 0}, {8, 1}, {0, 8}, {3, 2}, {6, 1}, {2, 2}, {7, 1}, {5, 
 2}, {1, 2}}
Graph[g, VertexCoordinates -> %]

12n6apzbs1hul

IGLayoutTutte

?IGLayoutTutte

1k50stehsr3rf

The Tutte embedding can be computed for a 3-vertex-connected planar graph. The faces of such a graph are uniquely defined. This embedding ensures that the coordinates of any vertex not on the outer face are the average of its neighbour’s coordinates, thus it is also called barycentric embedding.

IGLayoutTutte supports weighted graphs, and uses the weights for computing barycentres.

The available options are:

By default, a largest face is chosen to be the outer one.

g = IGShorthand["1-2-3-1,4-5-6-4,1-4,2-5,3-6"]

1dlpeqhbmda61

IGLayoutTutte[g]

1plxsj25jrn3j

We can specify a different outer face manually.

IGLayoutTutte[g, "OuterFace" -> {5, 4, 6}]

1jvq6yqgw61l3

For some graphs, the best result is achieved when the outer face is not chosen to be a largest one.

g = GraphData["TutteGraph"];
{IGLayoutTutte[g], 
 IGLayoutTutte[g, "OuterFace" -> {2, 8, 9, 10, 7, 6, 5, 4, 3}]}

11z3uniymogig

IGLayoutTutte requires a 3-vertex-connected planar input.

IGLayoutTutte[CompleteGraph[5]]

0uhlkc49ef60y

1dziamqj04ir7

1rs94x5tz07m2

IGLayoutTutte[CycleGraph[5]]

1s5g0i66kqdm4

1m3ym4n1esovz

IGLayoutTutte will take into account edge weights. For a weighted graph, the barycenter of neighbours is computed with a weighting corresponding to the edge weights.

A disadvantage of the Tutte embedding is that the ratio of the shortest and longest edge it creates is often very large. This can be partially remedied by first computing an unweighted Tutte embedding, then setting edge weights based on the obtained edge lengths.

pg = IGLayoutTutte@GraphData["GreatRhombicosidodecahedralGraph"]

0zo7dzdlc3u2n

IGLayoutTutte@
 IGEdgeMap[Apply[EuclideanDistance], 
  EdgeWeight -> IGEdgeVertexProp[VertexCoordinates], pg]

00e5pk9st04p8

By applying a further power-transformation of the weight, we can fine-tune the layout.

Manipulate[
 IGLayoutTutte[
  IGEdgeMap[(EuclideanDistance @@ #)^power &, 
   EdgeWeight -> IGEdgeVertexProp[VertexCoordinates], pg],
  VertexSize -> 1/2
  ],
 {{power, 1}, 0.5, 3}
 ]

1pql9k3049f00

Geometrical computation and meshes

Geometrical meshes

IGMeshGraph

?IGMeshGraph

0ve3046rrsaoc

The available options are:

The following example demonstrates finding a shortest path on a geometric mesh.

mesh = DiscretizeRegion[
  RegionDifference[Rectangle[{0, 0}, {3, 3}], 
   Rectangle[{0, 1}, {2, 2}]], MaxCellMeasure -> 0.02]

1b4wrcowo5nyv

IGMeshGraph preserves the vertex coordinates, and uses edge lengths as edge weights by default.

g = IGMeshGraph[mesh]

1x88uaqtiy96q

Find the corners.

st = First /@ Through[
   {MinimalBy, MaximalBy}[VertexList[g], 
    Norm@PropertyValue[{g, #}, VertexCoordinates] &]
   ]
{48, 20}

Highlight the shortest path.

HighlightGraph[g,
 PathGraph@FindShortestPath[g, First[st], Last[st]],
 Frame -> True, FrameTicks -> True
 ]

1k77y69rujsjf

Find a Hamiltonian path on a mesh.

g = IGMeshGraph@DiscretizeRegion[Disk[], MaxCellMeasure -> 1/40];
HighlightGraph[g, PathGraph@FindHamiltonianPath[g], 
 GraphHighlightStyle -> "DehighlightHide"]

1a4n9pp4t0jvg

Get a spikey as a graph.

IGMeshGraph@PolyhedronData["Spikey", "BoundaryMeshRegion"]

1ror10dlvejcf

IGMeshCellAdjacencyGraph and IGMeshCellAdjacencMatrix

?IGMeshCellAdjacencyGraph

0y3k4twmuan0d

?IGMeshCellAdjacencyMatrix

04tsb153a84bi

The available options for IGMeshCellAdjacencyGraph are:

Compute the connectivity of mesh vertices (zero-dimensional cells).

mesh = DiscretizeRegion[Disk[], MaxCellMeasure -> 0.1]

1aqh1uqkaliek

IGMeshCellAdjacencyGraph[mesh, 0, VertexCoordinates -> Automatic]

07r8hs1yi8zzj

Compute the connectivity of faces (two-dimensional cells).

IGMeshCellAdjacencyGraph[mesh, 2]

0yw3k5cov63ti

Create the graph of a Goldberg polyhedron.

IGMeshCellAdjacencyGraph[
 BoundaryDiscretizeRegion[Ball[], PrecisionGoal -> 1, 
  MaxCellMeasure -> 0.5], 2,
 VertexCoordinates -> Automatic]

0tg2jqvujokq3

Compute the connectivity of faces and edges, and colour nodes based on whether they represent a face or an edge.

g = IGMeshCellAdjacencyGraph[
  mesh, 2, 1,
  VertexSize -> 0.9, 
  VertexStyle -> {EdgeForm[], {1, _} -> Red, {2, _} -> Black}, 
  EdgeStyle -> Gray]

1dkbenhkc8rxj

This is a bipartite graph.

IGBipartiteQ[g]
True

The vertex names are the same as the mesh cell indices (see MeshCellIndex).

VertexList[g] // Short

00uhwpmnasrrg

Colour the faces of the mesh.

SetProperty[{mesh, {2<