Message Boards Message Boards

IGraph/M: graph theory and network analysis with Mathematica

Posted 9 years ago

WOLFRAM MATERIALS for the ARTICLE:

Szabolcs Horvát, Jakub Podkalicki, Gábor Csárdi, Tamás Nepusz, Vincent Traag, Fabio Zanini, Daniel Noom, (2022).

IGraph/M: graph theory and network analysis for Mathematica.

arXiv:2209.09145 [physics.soc-ph].

https://doi.org/10.48550/arXiv.2209.09145

Discourse topics GitHub (pre-)release Contributions welcome DOI


Article abstract

IGraph/M is an efficient general purpose graph theory and network analysis package for Mathematica. IGraph/M serves as the Wolfram Language interfaces to the igraph C library, and also provides several unique pieces of functionality not yet present in igraph, but made possible by combining its capabilities with Mathematica's. The package is designed to support both graph theoretical research as well as the analysis of large-scale empirical networks.


Introduction

The post below was written for the original release of IGraph/M. The package has come a long way since then and now contains ~300 functions. See http://szhorvat.net/mathematica/IGraphM for more details on the current release.

Compatibility: 64-it Windows/macOS/Linux or Raspberry Pi; Mathematica 10.0 11.0 or later.


I would like to announce IGraph/M, a new igraph interface for Mathematica: http://szhorvat.net/mathematica/IGraphM

igraph is a graph manipulation and analysis package. IGraph/M makes its functionality available from Mathematica.

This initial release, version 0.1, covers only some igraph functions, as I focused on the things that I need personally. However the main framework is complete, and new functions can be added quickly. If anyone would like to contribute, please contact me.

Binary packages for OS X (10.9 or later) and Linux can be downloaded from GitHub. Unfortunately, I was unable to compile the development version of igraph for Windows, so I cannot provide a Windows version. If you can help with compiling igraph itself (not IGraph/M) on Windows, please let me know!

Functionality in this release that is not built into Mathematica:

  • Vertex betweenness centrality for weighted graphs
  • Estimates of vertex betweenness, edge betweenness and closeness centrality; for large graphs
  • Minimum feedback arc set for weighted and unweighted graphs
  • Find all cliques (not just maximal ones)
  • Count 3- and 4-motifs
  • Rewire edges, keeping either the density or the degree sequence
  • Alternative algorithms for isomorphism testing: Bliss, VF2
  • Subgraph isomorphism
  • Test if a degree sequence is graphical
  • Alternative algorithms for generating random graphs with given degree sequence
  • Layout algorithms that take weights into account

Note that IGraph/M is not a replacement for Mathematica's graphs and networks functionality. It is meant to complement what is already available in Mathematica, thus it primarily focuses on adding functionality that is not already present.

Why did I release the package before covering most of the igraph functionality? I do not have time to work on things I do not personally need or use, so I am unlikely to extend it further unless the need comes up. I do think that the functions that are included in v0.1 can already be useful to others too. I would also like to give the opportunity for people to contribute to the project if they wish to. The groundwork has been laid, so further extensions should be quick and relatively easy.

Also check out a related project, IGraphR, which makes igraph available for Mathematica users through RLink. I wrote IGraph/M because I needed higher performance and greater reliability (especially for parallel computing) than what RLink could provide.


A request: If any of you have used IGraphR in the past to access igraph from Mathematica, please post a response to this thread and let me know which specific functions you were using.

POSTED BY: Szabolcs Horvát
30 Replies

IGraph/M 0.6 is now released, with the much-requested support for Apple Silicon based Macs. The changelog is on GitHub: https://github.com/szhorvat/IGraphM/releases/tag/v0.6.0

This release contains new features, as well as many internal robustness improvements. Please use only this release with Mathematica 12.2 or later.

A highlight of this release is the included interactive graph editor, thanks to Kuba Podkalicki! All feedback regarding this or other features is very welcome.

enter image description here

POSTED BY: Szabolcs Horvát

Version 0.1.1 is now available.

Changes:

  • Windows 64 bit binaries are now included
  • New functions, polish and fixes
  • Basic documentation notebook with some examples. Evaluate IGDocumentation[] to open.

Try it and let me know if something doesn't work, especially on Windows!

https://github.com/szhorvat/IGraphM/releases

POSTED BY: Szabolcs Horvát

Version 0.6.5 is now released, just in time for Christmas! :-) Please upgrade to this release, especially if you are using Mathematica 13.2.

POSTED BY: Szabolcs Horvát

IGraph/M 0.4 is, finally, released!

Please use only this version (or later) with Mathematica 12.1, as it brings many compatibility fixes.

Note that IGraph/M 0.4 is the last version to offer compatibility with Mathematica 10.0. Starting with version 0.5, IGraph/M will only work with Mathematica versions supported by Wolfram Research. This means that the minimum required version will be Mathematica 11.0 or 11.1 (to be determined).

A web-based preview of the documentation is now available.

As usual, all feedback about the package is welcome.

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.0 is now available.

This release fixes compatibility with Mathematica 11.1.

It also introduces new functions, performance improvements, bug fixes and polish. Upgrading is recommended for all users.

POSTED BY: Szabolcs Horvát

Pre-release 0.3.90, leading up to 0.4, is now available:

Let me know if you find any problems, or have any suggestions.

This release has several utility functions for working with graph properties and weighted graphs.

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.94 is now available! Please upgrade to this version if you are still using 0.3.0.

Notable improvements since the previous prerelease: functions for working with bipartite incidence matrices, converting geometrical meshes to graphs (thank you to Henrik Schumacher!), improvements to community detection, improvements to isomorphism functions, improvements to random walk functionality, and of course bug fixes. A full list of changes since v0.3.0 is in the README.

If you are just mildly curious about the package, you can check out the PDF version of the documentation (and the many examples within) here:

If you happen to be using Mathematica 11.2.0 on Windows, and are annoyed that the graph isomorphism functionality is broken in that version, note that IGraph/M provides a full replacement of (and many extensions to) that functionality area. ;-)

Update: 0.3.95 is out now with performance improvements and a few new functions.

Update: 0.3.96.1 is out now. Please upgrade.

Update: 0.3.97.2 is out now. Please upgrade. You can use the upgrade script on the project's GitHub page. This release introduces more functions for working with weighted graphs.

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.109 is now released. Please upgrade to this version if you have Mathematica 12.0! (And upgrade even if you don't, to get all the bug fixes.)

https://github.com/szhorvat/IGraphM

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.113 is released, with many bug fixes, and some new functionality. http://szhorvat.net/mathematica/IGraphM

There is now an inline version of the documentation: http://szhorvat.net/mathematica/IGDocumentation/ Please let me know about any problems you notice.

Prerelease testers are requested to try this version with Mathematica 12.1 and email me about any problems.

POSTED BY: Szabolcs Horvát

IGraph/M 0.6.1, fixing some issues that unexpectedly crept into 0.6.0. Please use this version, especially on Linux.

Update: 0.6.2 is out, please upgrade. This is another bugfix-only release.

Update: 0.6.3 is released now!

POSTED BY: Szabolcs Horvát

IGraph/M 0.2.1 is now released. This is a bugfix release. It can be downloaded from https://github.com/szhorvat/IGraphM/releases as usual.

Two bugs which could cause wrong results to be returned are fixed. If you use any of the affected functions, please upgrade.

The following changes require special mention:

  • IGFeedbackArcSet could return wrong results for some graphs. This is now fixed.
  • The "RemovedEdges" property returned by IGCommunitiesEdgeBetweenness could be incorrect for some graphs. This is now fixed. Other properties were not affected.
  • The Hierarchical Clustering package is no longer auto-loaded by IGraph/M to avoid shadowing DistanceMatrix, a new builtin added in Mathematica 10.3. Load this package manually (<<HierarchicalClustering`) to work with the "HierarchicalClusters" property of IGClusterData objects.

A number of other small bugs were also fixed.

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.99 is now released, with a simplified installation procedure. Now it only takes a single line of Mathematica code to automatically download and install the package (please click through to the website so I can keep the installation instructions in a central location).

This release brings many features developed specifically for IGraph/M, and not previously available in the core igraph library. It also includes several new features exclusive to IGraph/M (not available in other igraph interfaces). At this point, IGraph/M also provides alternatives for most Combinatorica feature that do not yet have built-in equivalents in Mathematica.

Some highlights:

Efficient minimum graph colouring and chromatic number computation (implemented in almost pure WL code!). Here's a little demo:

We apply a Mycelski construction to a cycle graph twice, then compute a minimum colouring, and finally visualize this colouring.

Nest[IGMycielskian, CycleGraph[4], 2] // 
  Graph[#, GraphStyle -> "BasicBlack", VertexSize -> Large] & //
  IGVertexMap[ColorData[101], VertexStyle -> IGMinimumVertexColoring]

Mathematica graphics

Computing the chromatic number would have been as easy as

IGChromaticNumber[%]
(* 4 *)

Also check that it's triangle free:

IGTriangleFreeQ[%%]
(* True *)

We now have easy and flexible lattice generation:

IGLatticeMesh["CairoPentagonal"]

Mathematica graphics

Improved mesh-graph conversion. Let's compute the face-face adjacency graph (i.e. the dual lattice) while keeping vertex coordinates.

IGMeshCellAdjacencyGraph[%, 2, VertexCoordinates -> Automatic]

Mathematica graphics

Let's take that graph and find a random spanning tree to generate a nice maze.

IGRandomSpanningTree[%, GraphStyle -> "Web", 
 VertexCoordinates -> GraphEmbedding[%]]

Mathematica graphics

Now take the degree sequence of that tree and generate another tree (i.e. connected graph) with the same degree sequence.

IGRealizeDegreeSequence[VertexDegree[%]] // TreeGraphQ
(* True *)

Compute a minimum colouring of a pinwheel tiling.

mesh = IGLatticeMesh["Pinwheel", {3, 3}, MeshCellStyle -> {1 -> White}];
SetProperty[{mesh, {2, All}}, MeshCellStyle -> ColorData[11] /@ IGMinimumVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2]]

Mathematica graphics

Compute the chromatic index (edge chromatic number) of a large graph.

IGChromaticIndex@RandomGraph[{100, 200}] // Timing
(* {0.040686, 10} *)

There are many more examples in the documentation, and many more new functions. Here I chose to show a few visually interesting ones.

As always, all feedback is welcome, and any help with the package is appreciated: testing, editing the documentation, contributing examples, or if you're feeling up to it, adding new functions.

POSTED BY: Szabolcs Horvát

New version released with a critical fix for IGBlissIsomorphicQ for coloured graphs. Please update.

See the release page for a list of changes:

UPDATE: There's a new release that improves compatibility with various Linux distributions, and also has other fixes. Please upgrade! Remember that it's always easy with the auto-upgrade script.

POSTED BY: Szabolcs Horvát

IGraph/M 0.3.112 is now released with some critical bug fixes and new functions. Please upgrade.

There are new functions for testing graph symmetry and regularity. Here's a demonstration:

Graph symmetry and regularity table

Needs["IGraphM`"]

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 -> 60] & /@ graphs, Keys[functions]}, 
  TableDirections -> Row
]
POSTED BY: Szabolcs Horvát

Great work!

POSTED BY: Anton Antonov

IGraph/M 0.5 is now released. It brings both new features and bugfixes. Please upgrade.

If you use this software in your work, please cite it.

POSTED BY: Szabolcs Horvát

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial columns Staff Picks http://wolfr.am/StaffPicks and Publication Materials https://wolfr.am/PubMat and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team

Hi Szabolcs, your package is very interesting, congrats. I am new in Mathematica and was wondering if is it possible to build with it (or Mathematica build in functions) what NetGraph does but not restricted to layers. Something like Slots and Signals from QT or Unreal engine blueprints where the graph is the processing flow of a complex collection of arbitrary or customized deterministic functions. When we use FunctionLayer or ThreadingLayer, to map such arbitrary function on a vertex it not works properly and has the overhead of the learning engine. For example mapping Outer will works but with severe restrictions. Something likes the idea in the graph below. Any thoughts? Thanks.

Graph[{1 -> 3, 2 -> 3, 3 -> 5, 4 -> 5}, 
 VertexLabels -> {1 -> "Array A", 2 -> "Array B", 
   3 -> "Array D = Plus[A,B]", 4 -> "Array C", 
   5 -> "Array E = Times[C,D]"}]
POSTED BY: Flavio Castilho

Hello Flavio,

And sorry about the slow response. I was on holidays when you originally wrote.

IGraph/M provides many new operations to work with Mathematica's built-in Graph expressions. Most IGraph/M functions are concerned with analysing networks, or with building new networks.

Graph expressions can represent any kind of graph, including the ones you mention. However, they don't really do anything, they just represent a structure. This distinguishes them from things like NetGraph where the primary purpose is not just to represent, but perform a function: you give it some inputs and it computes the output.

If I understand your question, you may be looking for a system to propagate a signal through a network, or perhaps to perform some computation with it. Graph can provide an underlying structure for this, but if you have a specific way to propagate signals through it, you would need to implement that yourself. There are some functions in IGraph/M which can be though of as "signal propagation", but they are all for specific purposes, so I am not sure this is what you are looking for. For example, there is IGRandomWalk which simulates a random walker on the network. There is IGSIRProcess, which models epidemic spread through a network. There are many classic network metrics that IGraph/M can compute (in more flexible ways than Mathematica's builtins) which can tell us something about how various signals would propagate: PageRank is based on the idea of a random walker (a rando web-surfer clicking through pages) that occasionally jumps to an arbitrary node. Betweenness centrality tells us something about which nodes the signal will pass through most often if it takes a shortest path. And so on.

I hope this helps a bit.

POSTED BY: Szabolcs Horvát

Hi Szabolcs, Thank you for your reply. You understood correctly, I am looking for a kind of "signal propagation" feature on IGraph/M or Mathematica build in. But your explanation really helps to clarify what I can do and what I cannot do with them. For the moment, I can use the graph to visualization and analysis purposes and just compute the functions on regular algorithmic way. To perform analysis on complex network IGraph/M will be very handle, which is quite cool. Thank you again.

POSTED BY: Flavio Castilho

Hello, I did give it a spin on windows 7 64 and 10.1 kernel. All functions work in your documentation (manually opened) The only error appears when I use IGDocument[] to open the documentation.

FileNameJoin::optx: Unknown option Saveable in FileNameJoin[{E:\WolframApps\igraphmtest\IGraphM-0.1.1\IGraphM-0.1.1\IGraphM\,Documentation,IGDocumentation.nb},Saveable->False]. >>

nice work!

Thank you for letting me know! This is now fixed in version 0.1.2. There are few changes in this version; its main purpose was to fix a bug on Windows where some functions were not working at all.

POSTED BY: Szabolcs Horvát

IGraph/M version 0.1.3 is released now, with expanded coverage for igraph functions and a lot of polish for the already covered ones.

Highlights for this release:

  • Community detection algorithms
  • Automorphism group for vertex coloured graphs; multigraph isomorphism
  • Additional centrality measures with support for weighted graphs
POSTED BY: Szabolcs Horvát

IGraph/M 0.2.0 is released now with many improvements.

Highlights for this release:

  • Significant performance improvements for many functions
  • New and extended functions for shortest path calculations (extended IGDistanceMatrix, IGDistanceCounts, IGDistanceHistogram, IGDiameter, IGFindDiameter)
  • Support for weighted clique calculations (IGWeightedCliques, IGMaximalWeightedCliques, IGLargestWeightedCliques, IGWeightedCliqueNumber)
  • Additional new functions
  • Syntax highlighting for functions
  • Raspberry Pi support
  • Compatibility with Mathematica 10.4 on OS X.
  • Bug fixes

I would appreciate any testing people can do on platforms I didn't have access to (priorities in decreasing order: Linux, Windows, OS X, pre-10.3 Mathematica versions).

POSTED BY: Szabolcs Horvát

IGraph/M 0.2.0 is released now with many improvements. It can be downloaded from https://github.com/szhorvat/IGraphM/releases as usual.

Highlights for this release:

  • Significant performance improvements for many functions
  • New and extended functions for shortest path calculations (extended IGDistanceMatrix, IGDistanceCounts, IGDistanceHistogram, IGDiameter, IGFindDiameter)
  • Support for weighted clique calculations (IGWeightedCliques, IGMaximalWeightedCliques, IGLargestWeightedCliques, IGWeightedCliqueNumber)
  • Additional new functions
  • Syntax highlighting for functions
  • Raspberry Pi support
  • Compatibility with Mathematica 10.4 on OS X.
  • Bug fixes

I would appreciate any testing people can do on platforms I didn't have access to (priorities in decreasing order: Linux, Windows, OS X, pre-10.3 Mathematica versions).

POSTED BY: Szabolcs Horvát

Hi Szabolcs, Your package looks really awesome! I just installed the latest on my Windows 10 with MM11.1.1.0 and it runs fine. The documentation is also very nice. What an effort and work! The warnings are all correct and documented (I ran the whole documentation). The only unexpected "red" was:

DendrogramPlot[cl1["HierarchicalClusters"], 
 LeafLabels -> (Rotate[#, Pi/2] &), ImageSize -> 750, 
 AspectRatio -> 1/2]

enter image description here

Can't wait to play with this Package!

POSTED BY: l van Veen

Don't worry about the red colouring here. This is only because the builtin HierarchicalClustering package hasn't been updated to make use of SyntaxInformation. These options work correctly. The highlighting can be safely ignored.

POSTED BY: Szabolcs Horvát

Prerelease 0.3.91 is now available. If you tried the previous prerelease, please upgrade.

This release includes bug fixes, documentation improvements, and a few new functions.

Let me know if you find any problems, or have any suggestions.

POSTED BY: Szabolcs Horvát

Prerelease 0.3.92 is now available. If you are using Mathematica 11.2, please do upgrade! The previous prerelease may cause problems with the M11.2 documentation centre.

Download it from GitHub:

This release is still marked as a "prerelease" because not all features I planned are ready. However, at this point, I strongly recommend using it instead of the older 0.3.0.

POSTED BY: Szabolcs Horvát

Bravo!

POSTED BY: Michael Sollami
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract