The igraph library for complex network research

Introduction

igraph is a free software package for creating and manipulating undirected and directed graphs. It includes implementations for classic graph theory problems like minimum spanning trees and network flow, and also implements algorithms for some recent network analysis methods, like community structure search.

Features

igraph contains functions for generating regular and random graphs, manipulating graphs, assigning attributes to vertices and edges. It can calculate various structural properties, includes heuristics for community structure detection, supports many file formats.

Requirements

The software you need for installing igraph depends on whether you want to use the C library, the R package or the Python extension.

Introduction

The efficient implementation of igraph allows it to handle graphs with millions of vertices and edges. The rule of thumb is that if your graph fits into the physical memory then igraph can handle it.

igraph can be installed in several forms:

igraph as a C library is useful if you want to use it in your C/C++ projects, or want to implement your own network analysis or model in C/C++ using the data structures and functions igraph provides.
igraph as an R package. You can use igraph as an extension package to The GNU R project for Statistical Computing. The flexibility of the R language and its richness in statistical methods add a great deal of productivity to igraph, with a very small speed penalty.
igraph as a Python extension module. This way you can combine igraph with the huge set of Python functions and modules available, and the ease of the Python language, with a small speed penalty.
igraph as a Ruby extension. If you like the Ruby language, then this might be the right choice for you.

Every form of igraph contain the same code at the very heart, written in ANSI C.

Please note that the ways of installing igraph depends on which its forms you actually want to use. Eg. for using igraph as an R package, you don't need to download the C library at all. See the download page for details.

Features

Here are some features of igraph, a subset of the functionality, see The igraph reference manual under Documentation for more details.

igraph contains functions for generating regular and random graphs according to many algorithms and models from the network theory literature.
igraph provides routines for manipulating graphs, adding and removing edges and vertices.
You can assign numeric or textual attribute to the vertices or edges of the graph, like edge weights or textual vertex ids.
A rich set of functions calculating various structural properties, eg. betweenness, PageRank, k-cores, network motifs, etc. are also included.
Force based layout generators for small and large graphs
The R package and the Python module can visualize graphs many ways, in 2D and 3D, interactively or non-interactively.
igraph provides data types for implementing your own algorithm in C, R, Python or Ruby.
Community structure detection algorithms using many recently developed heuristics.
igraph can read and write many file formats, e.g., GraphML, GML or Pajek.
igraph contains efficient functions for deciding graph isomorphism and subgraph isomorphism
It also contains an implementation of the push/relabel algorithm for calculating maximum network flow, and this way minimum cuts, vertex and edge connectivity.
igraph is well documented both for users and developers.
igraph is open source and distributed under GNU GPL.

Requirements

The C library

For using the igraph C library only a fairly recent C and C++ library is needed. For supporting the GraphML format you'll need the libxml2 library.

For compiling the igraph C library from source you'll need a fairly modern C and C++ compiler and some standard UNIX tools like make, chmod, touch, etc.

Most often we use the GNU Compiler Collection for compiling. Theoretically it is possible to compile igraph using the Microsoft Visual C Compiler as well, but we recommend the Cygwin or MinGW environments for compiling igraph under Windows.

The GNU R package

For using the igraph R package you obviously need GNU R, a recent version like 2.6.0 is recommended, since earlier versions contain bugs which affect igraph. If you would like to compile the R package from source (this is the usual way for Linux systems), you'll need a C and C++ compiler and optionally the libxml2 library.

For installing the igraph R package on Windows, you don't need anything else, just GNU R and the binary igraph R package of course

The Python extension module

For installing the Python extension module, you'll need Python version 2.4 or later. Binary versions of the module are available for Python 2.4 and Python 2.5 on the Windows platform, so you don't have to compile anything in this case. OS X Leopard users can download an installer as well. If you are using Linux or Mac OS X Tiger, you'll have to compile the extension by yourself. Compilation requires a recent C compiler (e.g. gcc, which is usually available as a separate package in Linux and as part of XCode on Mac OS X. You'll also need the compiled form of the igraph C core, as the Python interface will link to that during compilation.

If you have the EasyInstall Python script installed, you can simply type easy_install igraph to download, compile and install igraph as a Python Egg. This method assumes that you installed the C core somewhere in the default include and library path of your system.

The Ruby extension

For installing the Ruby extension please consult the homepage of this extension.

Compiling the development version

For compiling the development version of igraph, you'll need quite a large set of tools: autoconf, automake, GNU bison version 1.35 or newer, GNU make, maybe more. For compiling the documentation you'll need even more tools: Python, Docbook schemas and tools, xmlto, makeinfo, patch, docbook2x, maybe more. We're sure you know how to get these if you want to compile the development version :)