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`"]

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`*

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

?IGVersion

IGVersion[]

"IGraph/M 0.6.5 (December 21, 2022)
igraph 0.9.10-23-g5635203bd (Dec 21 2022)
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]]

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 13.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]]

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

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

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]

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"]

Deterministic graph generators▴

IGShorthand▴

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

?IGShorthand

The available options are:

• SelfLoops -> True keeps self-loops in the graph.

• MultiEdges -> True keeps parallel edges in the graph.

Construct a cycle graph.

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

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

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

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

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

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

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

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

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

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"]

Disconnected components are separated by commas.

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

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"]

… or a complete bipartite graph.

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

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"]

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]

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

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

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}

Create an interactive graph editor that dynamically visualizes betweenness.

Manipulate[
 IGShorthand[spec, VertexSize -> {"Scaled", 0.06}, 
   EdgeStyle -> Gray] //
  IGVertexMap[ColorData["NeonColors"], 
   VertexStyle -> IGBetweenness/*Rescale],
 {{spec, "1-2-3-1-4"}, 
  InputField[#, String, ContinuousAction -> True] &},
 Initialization :> Needs["IGraphM`"]
 ]

IGEmptyGraph▴

?IGEmptyGraph

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]

The built-in EmptyGraphQ returns True for these graphs.

EmptyGraphQ[%]

True

IGLCF▴

?IGLCF

creates a graph based on the LCF notation.

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

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

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

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

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

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

IGChordalRing▴

?IGChordalRing

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:

• DirectedEdges -> True creates a graph with directed edges.

• SelfLoops -> False prevents the creation of self-loops.

• MultiEgdes -> False prevents the creation of multi-edges.

Create an extended chordal graph.

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

Negative offsets are allowed.

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

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]

Create a chordal graph with directed edges.

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

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]}]
    ]
  ]

IGSquareLattice▴

?IGSquareLattice

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

• "Radius" controls the size of the neighbourhood within which vertices will be connected.

• "Periodic" -> True creates a periodic lattice.

• "Mutual" -> True inserts directed edges in both directions when DirectedEdges -> True is used.

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"]

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

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

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

IGTriangularLattice▴

?IGTriangularLattice

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:

• DirectedEdges -> True creates a directed graph.

• "Periodic" -> True creates a periodic lattice.

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

IGTriangularLattice[6, GraphStyle -> "SmallNetwork"]

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"]

Create a triangle lattice and colour its vertices.

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

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}]
 ]

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

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

IGKaryTree▴

?IGKaryTree

The available options are:

• DirectedEdges -> True creates a directed tree.

IGKaryTree[15]

IGKaryTree[10, 3, DirectedEdges -> True]

IGSymmetricTree▴

?IGSymmetricTree

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}]

Create a directed tree.

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

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

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

IGBetheLattice▴

?IGBetheLattice

A Bethe lattice, also called a regular tree, 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]

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

IGBetheLattice[5, 4, DirectedEdges -> True]

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]
 ]

Visualize the nested line graph of a degree-4 regular tree.

Graph3D@Nest[LineGraph, IGBetheLattice[5, 4], 2]

IGFromPrufer▴

?IGFromPrufer

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"]

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}]

Of these, only two are non-isomorphic.

DeleteDuplicates[CanonicalGraph /@ %]

IGExpressionTree▴

?IGExpressionTree

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:

• VertexLabels -> "Head" labels branch vertices with the Head of the corresponding subexpression and leaf vertices with the corresponding atomic expression.

• VertexLabels -> "Subexpression" labels vertices with the corresponding subexpression.

• VertexLabels -> "Name" labels vertices with their name, i.e. the position of the corresponding subexpression.

• VertexLabels -> None uses no labels.

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

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

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]

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
 ]

Create an undirected graph, labelled with subexpressions.

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

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

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

An equivalent of IGSymmetricTree can be easily implemented using IGExpressionTree.

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

Define a tree through a substitution system.

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

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] &

IGCompleteGraph▴

?IGCompleteGraph

The available options are:

• DirectedEdges -> True creates a directed graph.

• SelfLoops -> True includes self-loops.

Create an undirected complete graph with loops.

IGCompleteGraph[5, SelfLoops -> True]

Create a directed complete graph with loops.

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

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

IGCompleteGraph /@ Range[0, 3]

Create a complete graph on the given vertices.

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

IGCompleteAcyclicGraph▴

?IGCompleteAcyclicGraph

Create a complete acyclic directed graph on 5 vertices.

IGCompleteAcyclicGraph[5]

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"]

IGKautzGraph▴

?IGKautzGraph

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]

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
 ]

IGDeBruijnGraph▴

?IGDeBruijnGraph

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

IGRealizeDegreeSequence▴

?IGRealizeDegreeSequence

This function constructs an undirected graph with the given degree sequence, or a directed graph with the given in- and out-degree sequences. For constructing simple graphs, it uses the Havel–Hakimi algorithm (undirected case) or Kleitman–Wang algorithm (directed case). These algorithms work by selecting a “hub” 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. For constructing a loop-free multigraph, a similar algorithm is used, but the hub is connected to only one other vertex in each step, instead of to as many as its degree. If self-loops are allowed as well, the same algorithm is used, and if a loop-free result cannot be created, an appropriate number of self-loops will be added to the very last hub. The order in which hub vertices are selected is controlled by the Method option.

To randomly sample multiple realizations of a degree sequence, use IGDegreeSequenceGame, or first create a single graph with IGRealizeDegreeSequence, then randomly rewire it using IGRewire.

The available options are:

• SelfLoops -> True allows creating self-loops (disallowed by default).

• MultiEdges -> True allows creating multi-edges (disallowed by default).

• The Method option controls the order in which hub vertices are chosen.

Available Method option values:

• "SmallestFirst" will choose a smallest-degree vertex in each step of the algorithm (this is the default). This results in a disassortative network. In the undirected case, this method is guaranteed to construct a connected graph, if one exists, both when constructing simple graphs or multigraphs. See Horvát and Modes (2020), as well as http://szhorvat.net/pelican/hh-connected-graphs.html for the proof. In the directed case, it tends to construct weakly-connected graphs, but this is not guaranteed.

• "LargestFirst" will choose a largest-degree vertex. This results in an assortative network. This method tends to construct disconnected graphs. This is the most common variant of the Havel–Hakimi algorithm implemented in other packages.

• "Index" will choose vertices in the order of their indices.

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}

The default Method -> "SmallestFirst" tends to create highly disassortative graphs. The result is guaranteed to be connected if the input degree sequence was potentially connected.

IGRealizeDegreeSequence[degseq]

N@GraphAssortativity[%]

-0.524347

Method -> "LargestFirst" tends to create highly assortative disconnected graphs.

IGRealizeDegreeSequence[degseq, Method -> "LargestFirst"]

N@GraphAssortativity[%]

0.904728

Allow parallel edges.

IGRealizeDegreeSequence[degseq, MultiEdges -> True, 
   Method -> #] & /@ {"SmallestFirst", "LargestFirst", "Index"}

Create a directed graph.

g = IGBarabasiAlbertGame[50, 1]

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

IGRealizeDegreeSequence[outdegseq, indegseq]

Verify that the degrees sequences of the result match the input to the function.

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

{False, False}

References

• S. L. Hakimi, On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, Journal of the Society for Industrial and Applied Mathematics 10, 3 (1962). http://eudml.org/doc/19050

• V. Havel, Poznámka O Existenci Konečných Grafů (A Remark on the Existence of Finite Graphs), Časopis Pro Pěstování Matematiky 80, 4 (1955). https://www.jstor.org/stable/2098746

• D. J. Kleitman and D. L. Wang, Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics 6, 1 (1973). https://doi.org/10.1016/0012-365X(73)90037-X

• Sz. Horvát and C. D. Modes, Connectivity matters: Construction and exact random sampling of connected graphs (2020). https://arxiv.org/abs/2009.03747

IGGraphAtlas▴

?IGGraphAtlas

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]

IGFamousGraph▴

?IGFamousGraph

This function returns various “named” graphs from the igraph C library’s built-in database. It is included in IGraph/M for compatibility with other igraph interfaces. It is recommended to use Mathematica’s built-in GraphData function instead. See the documentation of the igraph C library for the list of supported graph names.

Create Krackhardt’s kite graph:

g = IGFamousGraph["Krackhardt_Kite"]

Krackhardt’s kite was devised to illustrate the difference between various centrality measures:

#[g] & /@ {
  IGVertexMap[0.1 # &, VertexSize -> IGBetweenness],
  IGVertexMap[# &, VertexSize -> IGCloseness],
  IGVertexMap[# &, VertexSize -> IGHarmonicCentrality],
  IGVertexMap[0.1 # &, VertexSize -> VertexDegree]
  }

IGFromNauty▴

?IGFromNauty

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"]

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

IGFromNauty[":I`ESgTlVF"]

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

IGFromNauty["&FKB?oMB_W?"]

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"]

$Failed

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

Random graph generators▴

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

?IG*Game*

Basic random graphs▴

?IGErdosRenyiGameGNM

?IGErdosRenyiGameGNP

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:

• DirectedEdges -> True produces a directed graph.

• SelfLoops -> True allows self-loops.

Create a random graph with 10 vertices and 20 edges.

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

Create a directed graph and allow self-loops.

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

Insert each edge with a probability of 20%.

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

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}
 ]

Random bipartite graphs▴

?IGBipartiteGameGNM

?IGBipartiteGameGNP

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

The available options are:

• DirectedEdges -> True creates a directed graph.

• "Bidirectional" -> True allows directed edges to run in either direction between the two partitions. The default is False, which means that edges will run only from the first partition to the second. This option is ignored for undirected graphs.

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

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}

IGTreeGame▴

?IGTreeGame

IGTreeGame samples uniformly from the set of labelled trees.

Available options:

• DirectedEdges -> True will create a directed tree, with edges oriented away from the root.

• Method can be used to choose the tree generation algorithm. All methods sample labelled trees uniformly.

Available Method options:

• "PruferCode", works by generating a random Prüfer sequence, then constructing a tree from it. It does not currently support directed trees.

• "LoopErasedRandomWalk", uses a loop-erased random walk to uniformly sample the spanning trees of the complete graph.

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

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

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

Generate directed trees.

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

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]

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]
 ]

IGDegreeSequenceGame▴

?IGDegreeSequenceGame

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:

• "ConfigurationModel" implements the configuration model: it connects up vertex stubs randomly. It may generate both self-loops and multi-edges. Undirected graphs are generated with probability proportional to \(\left(\prod _{i<j}A_{ij}!\prod _iA_{ii}\text{!!}\right){}^{-1}\), where \(A\) is the adjacency matrix, having twice the number of loops for each vertex on the diagonal. Directed ones are generated with probability proportional to \(\left(\prod _{i,j}A_{ij}!\right){}^{-1}\).

  All simple graphs are generated with the same probability, but the probability of multigraphs and graphs with self-loops differs from that of simple graphs and depends on their specific structure.

• "ConfigurationModelSimple" also implements the configuration model, but it rejects non-simple graphs. It samples uniformly from the set of all simple graphs with the given degree sequence. This method can be very slow for dense graphs.

• "FastSimple" is a fast generation algorithm that avoids self-loops and multi-edges. This method can generate any simple graph with the given degree sequence, but it does not sample them uniformly.

• "VigerLatapy" can sample undirected, connected simple graphs uniformly and uses Monte-Carlo methods to randomize the graphs. This generator should be favoured if undirected and connected graphs are to be generated and execution time is not a concern. igraph uses the original implementation of Fabien Viger; see https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html and the corresponding paper at https://arxiv.org/abs/cs/0502085.

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

degseq = VertexDegree@RandomGraph[{50, 100}];

IGDegreeSequenceGame[degseq, Method -> "ConfigurationModel"]

SimpleGraphQ[%]

False

IGDegreeSequenceGame[degseq, Method -> "ConfigurationModelSimple"]

SimpleGraphQ[%]

True

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

ds = VertexDegree@RandomGraph[{10, Binomial[10, 2] - 5}]

{9, 7, 7, 9, 9, 8, 8, 7, 8, 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"]

ds == VertexDegree[%]

True

IGKRegularGame▴

?IGKRegularGame

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:

• DirectedEdges -> True creates a directed graph.

• MultiEdges -> True allows the creation of parallel edges.

IGKRegularGame[10, 3]

Not all parameters are valid:

IGKRegularGame[5, 3]

$Failed

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

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

False

IGGrowingGame▴

?IGGrowingGame

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:

• DirectedEdges -> True creates a directed graph.

• "Citation" -> True connects newly added edges to the newly added vertex.

IGGrowingGame[50, 2]

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

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

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"]

IGBarabasiAlbertGame▴

?IGBarabasiAlbertGame

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:

• DirectedEdges -> False creates an undirected graph.

• "TotalDegreeAttraction" -> True computes the attachment probability based on the the total degree of existing vertices (i.e. the sum of in- and out-degrees), not their in-degree. Always assumed to be True when using DirectedEdges -> True.

• "StartingGraph" -> g will use graph g as the starting point for building the preferential attachment graph. The vertex names of g are ignored; the result always uses positive integers as vertex names.

Available Method option values:

• "Bag" works by putting the IDs of the vertices into a bag exactly as many times as their (in-)degree, plus once more. Then the required number of cited vertices are drawn from the bag, with replacement. This method might generate multi-edges. It only works if \(\beta =1\) and \(A=1\).

• "PSumTree" uses a partial prefix-sum tree to generate the graph. It does not generate multi-edges and works for any \(\beta\) and \(A\) values.

• "PSumTreeMultiple" works like "PSumTree" but allows multi-edges.

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

IGBarabasiAlbertGame[100, 1]

Use attachment probability proportional to degree^1.5 + 1.

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

The "Bag" method may generate parallel edges:

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

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"]

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]]

IGWattsStrogatzGame▴

?IGWattsStrogatzGame

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

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

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}]

IGStaticFitnessGame▴

?IGStaticFitnessGame

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 <-> 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:

• SelfLoops -> True allows the creation of self-loops.

• MultiEdges -> True allows the creation of parallel edges.

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]

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]]

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

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:

• SelfLoops -> True allows the creation of self-loops.

• MultiEdges -> True allows the creation of parallel edges.

• "FiniteSizeCorrection" -> False disables finite size correction, which is used by default.

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"}]

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

IGStaticPowerLawGame[50, 150, 3, 3]

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

• Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.

• Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys. Rev. Lett. 103:135702, 2009.

IGStochasticBlockModelGame▴

?IGStochasticBlockModelGame

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:

• DirectedEdges -> True creates a directed graph.

• SelfLoops -> True allows the creation of self-loops.

IGAdjacencyMatrixPlot[%]

IGPreferenceGame▴

?IGPreferenceGame

Experimental: This is experimental functionality that may change without notice.

IGPreferenceGame[n, w, p] first samples n vertices of different types, each having type \(i\) with probability proportional to \(w_i\). Then it connects vertices with types \(i\) and \(j\) with probability \(p_{ij}\). This is similar to a stochastic block model, but the vertex types are chosen randomly.

The available options are:

• DirectedEdges -> True creates a directed graph.

• SelfLoops -> True allows self-loops.

Generate a graph with three groups of vertices of different sizes, with intra-group connections being much more frequent than inter-group ones.

IGPreferenceGame[60, {3, 6, 10}, 0.05 + 0.5 IdentityMatrix[3]]

Generate a directed graph with low-probability intra-group connections and high probability unidirectional inter-group connections.

IGAsymmetricPreferenceGame▴

?IGAsymmetricPreferenceGame

Experimental: This is experimental functionality that may change without notice.

IGAsymmetricPreferenceGame[n, w, p] is similar to IGPreferenceGame[n, w, p], but it assigns a separate out-type and in-types to each vertex. The probability of a vertex having out-type \(i\) and in-type \(j\) is proportional to \(w_{ij}\). The probability of connecting a vertex with out-type \(i\) to another one with in-type \(j\) is \(p_{ij}\).

The available options are:

• SelfLoops -> True allows self-loops.

IGForestFireGame▴

?IGForestFireGame

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:

• Heavy-tailed in-degree and out-degree distributions.

• Community structure.

• Densification power-law. The network is densifying in time, according to a power-law rule.

• Shrinking diameter. The diameter of the network decreases in time.

The available options are:

• DirectedEdges -> False generates an undirected graph.

Generate a graph with only forward burning.

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

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

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

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}
 ]

References

• Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graph evolution: Densification and shrinking diameters.
  ACM Transactions on Knowledge Discovery from Data (TKDD), 2007. https://doi.org/10.1145/1217299.1217301

• Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD ’05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, 177–187, 2005.

IGCallawayTraitsGame▴

?IGCallawayTraitsGame

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:

• DirectedEdges -> True creates a directed graph.

IGEstablishmentGame▴

?IGEstablishmentGame

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:

• DirectedEdges -> True creates a directed graph.

IGGeometricGame▴

?IGGeometricGame

Available options:

• "Periodic" -> True assumes a toroidal topology

IGGeometricGame[50, 0.2]

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]
  ]

Graph modification

IGRewire▴

?IGRewire

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.

⟶ or ⟶

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:

• SelfLoops -> True allows the creation of self-loops.

Generate a random network with scale-free degree distribution:

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

Use SelfLoops -> True to allow creating loops.

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

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

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"] &]

IGRewireEdges▴

?IGRewireEdges

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:

• SelfLoops -> True allows the creation of self-loops.

• MultiEdges -> True allows the creation of multi-edges.

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

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

EdgeCount[%]

20

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

g = RandomGraph[{10, 30}, DirectedEdges -> True];
{VertexInDegree[g], VertexOutDegree[g]}

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

rg = IGRewireEdges[g, 1, "Out"];
{VertexInDegree[rg], VertexOutDegree[rg]}

{{2, 0, 2, 7, 3, 3, 3, 3, 2, 5}, {2, 6, 4, 2, 2, 4, 3, 2, 2, 3}}

Note that multi-edges were created.

MultigraphQ[rg]

True

IGVertexContract▴

?IGVertexContract

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:

• SelfLoops -> True keeps any self-loops created during contraction.

• MultiEdges -> True keeps any parallel edges created during contraction.

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

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

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

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

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"]

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

IGConnectNeighborhood▴

?IGConnectNeighborhood

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]]

Connect each vertex to its third order neighbourhood:

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

IGMycielskian▴

?IGMycielskian

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]

{IGChromaticNumber[g], IGTriangleFreeQ[g]}

{2, True}

mg = IGMycielskian[g]

{IGChromaticNumber[mg], IGTriangleFreeQ[mg]}

{3, True}

Construct triangle-free graphs with successively larger chromatic numbers.

NestList[IGMycielskian, IGEmptyGraph[], 5]

IGChromaticNumber /@ %

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

IGSmoothen▴

?IGSmoothen

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

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:

• DirectedEdges -> False ignores edge directions in the input graph.

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

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]]

The result may also contain multi-edges.

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

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

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}]

tm = IGSmoothen[g]

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}]

IGSmoothen[g]

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

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

An alternative and faster method uses IGVertexMap and IGVertexAssociate:

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

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

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

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.

Merge resistors in series …

reducedGrid = IGSmoothen[resistorGrid]

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

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

Repeat until a single resistor remains.

reducedGrid = IGSmoothen[reducedGrid]

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

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

IGEdgeProp[EdgeWeight][reducedGrid]

{3.}

Structural properties

Centrality measures▴

Centralities are various measures that quantify the “importance” of vertices or edges in graphs.

Betweenness▴

?IGBetweenness

?IGBetweennessCutoff

?IGEdgeBetweenness

?IGEdgeBetweennessCutoff

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\).

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

Note that as of Mathematica 13.0, the built-in BetweennessCentrality function ignores edge weights and multi-edges, which causes it to yield different results from IGBetweenness.

Available options:

• Normalized -> True will compute the normalized betweenness by dividing the result by the number of (ordered or unordered) vertex pairs used in the shortest path calculation. Thus the normalization factor is \((V-1) (V-2)\) for directed graphs and \(\frac{1}{2} (V-1) (V-2)\) for undirected graphs. The normalized value lies between 0 and 1.

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
   ]

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
  ]

Possible issues

Betweenness computation involves comparing the lengths of paths, and deciding which specific path is the shortest, and which paths have equal lengths. When non-integer edge weights are used, the path length computation is subject to roundoff errors, which may cause the path length comparison to fail. igraph mitigates this by comparing the lengths using tolerances, however, there is still a small risk that roundoff errors may affect the result. To avoid this potential problem entirely, use integer weights. For example, if the weights are rational, multiply them by the least common multiple of their denominators.

Closeness▴

?IGCloseness

?IGClosenessCutoff

?IGNeighborhoodCloseness

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

Weighted graphs are supported.

Available options:

• Normalized -> False will compute the non-normalized closeness, i.e. the inverse of the sum of shortest path lengths to all other vertices.

There is no standard definition of closeness centrality for disconnected graphs. When the graph is disconnected, IGraph/M will only consider the distances to reachable vertices. In the undirected case, this effectively computes the closeness separately for each connected component. Use IGNeighborhoodCloseness to obtain both the closeness values, as well as how many vertices were reachable from each vertex. This information allows for computing various generalizations of closeness centrality for disconnected graphs.

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"]
 ]

For isolated vertices, Indeterminate is returned.

IGCloseness@IGShorthand["1,2-3"]

{Indeterminate, 1., 1.}

Harmonic centrality▴

?IGHarmonicCentrality

?IGHarmonicCentralityCutoff

The harmonic centrality of a vertex is the average inverse shortest path length to all other vertices. The inverse shortest path length to unreachable vertices is considered to be zero.

Available options:

• Normalized -> False computes the non-normalized harmonic centrality, i.e. the sum of inverse shortest path length to all other vertices.

RandomGraph[{30, 40}, VertexSize -> Large] // 
 IGVertexMap[ColorData["Rainbow"], 
  VertexStyle -> IGHarmonicCentrality/*Rescale]

PageRank▴

?IGPageRank

?IGPersonalizedPageRank

The PageRank centrality of a vertex is the fraction of time a random walker would spend on that vertex. The walker jumps from vertex to vertex randomly, following outward edges with probabilities proportional to their weights. Additionally, after each step, with a probability \(1-d\) the walk is restarted from a random vertex. \(d\) is called the damping factor. If the walker is stuck in a sink vertex (i.e. a vertex with no outgoing edges), the walk is also restarted.

In the standard version of PageRank, when the walk is restarted, the starting vertex is chosen uniformly. In the personalized version, it is chosen with probabilities proportional to the values in the reset parameter.

Weighted graphs and multigraphs are supported, and self-loops are taken into consideration.

Note that as of Mathematica 13.0, the built-in PageRankCentrality function ignores self-loops.

The default damping factor is 0.85.

The following Method options are available:

• "Arnoldi" uses ARPACK, and solves PageRank as an eigenvalue problem.

• "PRPACK" uses PRPACK and uses the algebraic method. It is the default method, and usually much faster than "Arnoldi".

Plot the logarithmic histogram of PageRank scores of the network of webpage in the nd.edu domain.

ndWeb = ExampleData[{"NetworkGraph", "WorldWideWeb"}];

Histogram[IGPageRank[ndWeb], "Log", {"Log", "PDF"},
 Frame -> True, FrameLabel -> {"PageRank", "PDF"}]

The personalization weights may be given as a vector of the same length as the vertex list …

g = RandomGraph[{10, 20}, DirectedEdges -> True];
IGPersonalizedPageRank[g, RandomReal[1, VertexCount[g]]]

{0.0433579, 0.129471, 0.23356, 0.113496, 0.000101892, 0.12872, \
0.260584, 0.024101, 0.0324582, 0.0341504}

… or as an association from vertex names to weights, in which case the weight of non-included vertices is taken to be zero.

IGPersonalizedPageRank[g, <|1 -> 1.5, 3 -> 0.5|>]

{0.297935, 0.0717967, 0.168933, 0.290878, 0., 0.0376334, 0.132824, \
0., 0., 0.}

Personalize PageRank by always restarting the walk from one of two vertices (29 or 74) on a grid graph:

g = IGSquareLattice[{10, 10}, VertexSize -> Large];

g // IGVertexMap[ColorData["Rainbow"], 
  VertexStyle -> (IGPersonalizedPageRank[#, <|29 -> 1, 74 -> 1|>, 
       0.99] &/*Rescale)]

LinkRank▴

?IGLinkRank

?IGPersonalizedLinkRank

LinkRank is the equivalent of PageRank for edges. The LinkRank of an edge is the relative frequency of traversing that edge by a random walker. For a detailed description of the random walk process, see the PageRank section.

The LinkRank of edges can be computed from the PageRank by simply dividing the PageRank of each vertex between its outgoing edges, proportionally with their edge weights. The LinkRank scores of the out-edges of a vertex add up to the PageRank of that vertex. The LinkRank scores of all edges in the graph add up to 1.

Weighted graphs and multigraphs are supported, and self-loops are taken into consideration.

The available Method options are the same as for IGPageRank.

Visualize both the LinkRank and PageRank of a random directed graph.

maxNorm = #/Max[#] &;

g = RandomGraph[{15, 30}, DirectedEdges -> True, EdgeStyle -> Thick, 
   VertexSize -> Large, GraphStyle -> "BasicBlack"];

g // IGEdgeMap[ColorData["Rainbow"], 
   EdgeStyle -> IGLinkRank/*maxNorm] // 
 IGVertexMap[ColorData["Rainbow"], VertexStyle -> IGPageRank/*maxNorm]

Visualize the personalized version of LinkRank and PageRank, always starting the random walk from vertex 1.

pers = <|1 -> 1|>;
Graph[g, VertexLabels -> "Name"] // 
  IGEdgeMap[ColorData["Rainbow"], 
   EdgeStyle -> (IGPersonalizedLinkRank[#, pers] &)/*maxNorm] // 
 IGVertexMap[ColorData["Rainbow"], 
  VertexStyle -> (IGPersonalizedPageRank[#, pers] &)/*maxNorm]

Eigenvector centrality▴

?IGEigenvectorCentrality

Eigenvector centrality is based on the idea that the importance (centrality) of a vertex should be affected not only by how many other vertices point to it, but also by the importance of its neighbours. The eigenvector centrality of a vertex is proportional to the sum of centralities of its neighbours. Mathematically, the eigenvector centrality is the leading eigenvector of the adjacency matrix.

Eigenvector centrality is meaningful for connected graphs only. Disconnected graphs should be decomposed into their components, and the eigenvector centrality computed separately for each. The vertex centrality scores will be comparable only within components, not between separate components.

In undirected graphs, the diagonal of the adjacency matrix is assumed to contain twice the number of self-loops on each vertex. This makes the undirected result consistent with the directed one when each undirected edge is replaced by reciprocal directed ones.

For directed graphs, the left eigenvector of the adjacency matrix is calculated. In other words, the centrality of a vertex is proportional to the sum of centralities of vertices pointing to it.

Weighted and directed graphs are supported.

The available options are:

• Normaized -> True will scale the result so that the maximum centrality is 1. The default is True.

• DirectedEdges -> False ignores edge directions.

Kleinberg’s hub and authority scores▴

?IGHubScore

?IGAuthorityScore

Weighted graphs are supported.

The available options are:

• Normalized -> True scales the result so that the maximum centrality is 1. The default is True.

Burt’s constraint score▴

?IGConstraintScore

Weighted graphs are supported.

Centralization▴

?IG*Centralization

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.194343

IGClosenessCentralization[g]

0.275726

IGDegreeCentralization[g, SelfLoops -> False]

0.144919

IGEigenvectorCentralization[g]

0.820631

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.

{0.666667, 1., 1.}

Topological sorting and acyclic graphs▴

IGDirectedAcyclicGraphQ▴

?IGDirectedAcyclicGraphQ

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

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.

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.

curvedEdge[offset_][{a_, ___, b_}, ___] := 
 Arrow@BezierCurve[{a, (a + b)/2 + offset Reverse[b - a], b}]
Graph[g,
  EdgeShapeFunction -> curvedEdge[2/3] (* 
  in M12.0 or later simply use {{"CurvedEdge",
  "Curvature"->1.5}} *)
  ] // IGVertexMap[{#, 0} &, 
  VertexCoordinates -> IGTopologicalOrdering/*Ordering]

When the graph contains cycles, $Failed is returned.

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

$Failed

IGFeedbackArcSet▴

?IGFeedbackArcSet

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"]

{AcyclicGraphQ[%], IGDirectedAcyclicGraphQ[%]}

{False, False}

Find a set of edges whose removal breaks all cycles.

IGFeedbackArcSet[g]

{1 \[DirectedEdge] 9, 3 \[DirectedEdge] 8, 4 \[DirectedEdge] 8}

ag = EdgeDelete[g, %]

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]

{9, 8, 4, 5, 6, 7, 1, 10, 2, 3}

With[{am = AdjacencyMatrix[ag]},
 ArrayPlot /@ {am, am[[perm, perm]]}
 ]

References

• P. Eades, X. Lin, and W. F. Smyth, A fast and effective heuristic for the feedback arc set problem, Inf. Process. Lett. 47, 319 (1993). https://doi.org/10.1016/0020-0190(93)90079-O

Chordal graphs▴

Chordal graphs are graphs that do not contain induced cycles with more than three vertices.

IGChordalQ▴

?IGChordalQ

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"]

IGChordalQ[g]

False

Adding chords to the 4 cycles makes them chordal.

EdgeAdd[g, {1 <-> 4, 4 <-> 5}]