IGraph/M

Visit package website
Edit

IGraph/M is a Mathematica package for use in complex networks and graph theory research. It started out as a well-integrated Mathematica interface to igraph, one of the most popular open source network analysis packages available. In addition to exposing igraph functionality to Mathematica, the current version of IGraph/M contains many other functions for working with graphs.

Functionality highlights:

  • Interruption support: using Evaluate → Abort Evaluation in Mathematica works with most IGraph/M functions.
  • Network analysis
    • Weighted centrality measures; fast centrality estimation in large graphs; centralization.
    • Community detection algorithms.
    • Count graph motifs (3- and 4-motifs); find triangles.
    • Randomly rewire graphs while keeping their density or degree sequence.
    • Many random graph models (including uniform random tree and random spanning tree sampling).
    • Fast shortest path finding and histogramming (weighted and unweighted).
    • Additional layout algorithms: most work with weighted graphs and can continue the layout optimization starting from a given set of vertex positions.
    • Random walks on graphs.
    • Many other functions ...
  • Graph theory
    • Many graph generators.
    • Isomorphism
      • Several algorithms: Bliss, VF and LAD; faster than the builtin for hard problems.
      • Multigraph isomorphism.
      • Isomorphism of simple graphs with coloured vertices and edges.
      • Subgraph isomorphism, including induced subgraphs with LAD.
      • Homeomorphism.
    • Vertex and edge colouring, including minimum colouring and computation of the chromatic number; Mycielski construction.
    • Planar graphs and combinatorial embeddings.
    • Minimum feedback arc set (weighted and unweighted).
    • Degree sequences: check graphicality; realize degree sequences (optionally as a connected graph); multiple methods for random sampling with given degree sequence; rewire while keeping degre sequence.
    • Find all cliques (not just maximal ones); count cliques of different sizes without storing them; work with weighted cliques.
    • Biconnected components, articulation points, bridges, find all minimum vertex cuts.
    • Replacement for much of the Combinatorica functionality not yet available as Mathematica built-ins.
  • Geometrical computation
    • Convert between geometric meshes and graphs
    • Proximity graphs (Delaunay graph, Gabriel graph, β-skeleton, etc.)
  • Utility functions for working with graphs in Mathematica:
    • Quick and easy graph styling based on computed properties.
    • Property handling and transformations, also useful for quick visualization.
    • Bipartite incidence matrices.
    • Fast functions for handling weighted graphs.
    • Adjacency matrix visualization.
  • Many other specialized functions not mentioned here ...

Load the package with

<<IGraphM`

The documentation can be opened using

IGDocumentation[]

and contains lots of examples.

All functions provided by the package have the prefix IG in their name to distinguish them from similar or equivalent functions built into Mathematica or provided by Combinatorica. See all available functions by evaluating

?IGraphM`*

The IGraph/M functions work directly on Mathematica's built-in Graph datatype.

g = IGBarabasiAlbertGame[50, 3]

Preferential attachment graph

Let's randomly rewire edges 1000 times while keeping the degree sequence:

g = IGRewire[g, 1000]

Rewired graph

Then we find the edges that we need to remove to make the graph acyclic:

feedback = IGFeedbackArcSet[g]
(* {2 -> 5, 3 -> 8, 5 -> 7, 10 -> 29, 17 -> 20} *)

AcyclicGraphQ@EdgeDelete[g, feedback]
(* True *)

Finally, we compute a minimum vertex colouring of the graph and visualize it.

 UndirectedGraph[g,
   GraphStyle -> "BasicBlack",
   VertexSize -> 0.7
 ] // IGVertexMap[ColorData[97], VertexStyle -> IGMinimumVertexColoring]

Minimum vertex colouring

The chromatic number, i.e. the minimum number of colours needed, is 4.

 IGChromaticNumber[g]
 (* 4 *)