Release notes

There are a lot of improvements and corrections in this version. We would like to thank all the people who sent comments, bug reports, patches, or just questions. Without their contribution igraph would be definitely much less and worse than it is now. Please keep sending your comments and ideas!

Here is a list of major changes, with links to the relevant sections of the documentation. See below for the complete list of changes.

Graph isomorphism

igraph includes the BLISS graph isomorphism algorithm and implementation now. This and the improved VF2 implementation, which can now calculate subgraph isomorphism, make igraph support the bleeding edge of graph isomorphism algorithms. Many thanks to the authors of BLISS. See the details in the Python documentation.

ARPACK for eigenvalue problems

ARPACK is a library for solving large scale sparse eigenvalue problems. In igraph it is very handy, as many centrality problems are in fact eigenvalue problems: Kleinberg’s hub and authority scores, PageRank, the leading eigenvector community detection algorithm are some examples. Many thanks to the authors of ARPACK and James Fowler, who suggested to include it in igraph.

See the details in the evcent, pagerank, hub_score, etc. functions in the Python documentation.

Plotting

Plotting functionality based on the Cairo graphics library (so you need to install python-cairo if you want to use it). Currently the following objects can be plotted: graphs, adjacency matrices and dendrograms. Some crude support for plotting histograms is also implemented. Plots can be saved in PNG, SVG and PDF formats.

See the details in the documentation.

Other bits

Shell interface

igraph can now be invoked by calling the script called igraph from the command line. The script launches the Python interpreter and automatically imports igraph functions into the main namespace.

Create famous graphs easily

Some classic graphs can be created by giving their name. This is very handy if one needs a test graph quickly. See Famous. (The idea is based on Combinatorica, a Mathematica extension.)

Improvements for weighted graphs

Many functions were updated to handle weighted graphs: fast greedy community detection, Page Rank, modularity calculation, the Fruchterman-Reingold layout algorithm.

Non-simple graphs

Some functions were added and improved to handle non-simple graphs (i.e. graphs with loop and/or multiple edges) better: testing that a graph is simple, testing for loop edges, testing for multiple edges) and counting the multiplicity of edges.

Pickling support in Python

igraph Graph objects can be serialized (pickled) in Python.

The graphopt layout algorithm

This is a nice force-based layout algorithm. See the documentation of details.

Support for the DOT file format

igraph can now write graphs to files in the DOT format, used by GraphViz. See documentation.

Dyad and triad census

Classic social network analysis tools for classifying the dyads and triads of a network.

Biconnected components and articulation points

igraph is now able to calculate biconnected components and articulation points.

Estimating closeness and betweenness

These measures can be quickly estimated by specifying an upper bound for path lengths to be considered. This is useful for larger graphs, for which the calculation takes a long time. See documentation for closeness, betweenness and edge betweenness.

Functions for vertex similarity measures

Two vertex similarity measures based on the number of common neighbors are introduced, the Jaccard Jaccard and the Dice similarities.

New features

• Added shell interface: igraph can now be invoked by calling the script called igraph from the command line. The script launches the Python interpreter and automatically imports igraph functions into the main namespace
• Pickling (serialization) support for Graph objects
• Plotting functionality based on the Cairo graphics library (so you need to install python-cairo if you want to use it). Currently the following objects can be plotted: graphs, adjacency matrices and dendrograms. Some crude support for plotting histograms is also implemented. Plots can be saved in PNG, SVG and PDF formats.
• Unified Graph.layout method for accessing layout algorithms
• Added interfaces to walktrap community detection and the BLISS isomorphism algorithm
• Added dyad and triad census functionality and motif counting
• VertexSeq and EdgeSeq objects can now be restricted to subsets of the whole network (e.g., you can select vertices/edges based on attributes, degree, centrality and so on)

New in the C library

• Many types (stack, matrix, dqueue, etc.) are templates now They were also rewritten to provide a better organized interface
• VF2 graph isomorphism routines can check subgraph isomorphism now, and they are able to return matching(s)
• The BLISS graph isomorphism algorithm is included in igraph now. See igraph_canonical_permutation, igraph_isomorphic_bliss
• We use ARPACK for eigenvalue/eigenvector calculation. This means that the following functions were rewritten: igraph_pagerank, igraph_community_leading_eigenvector_*. New functions based on ARPACK: igraph_eigenvector_centrality, igraph_hub_score, igraph_authority_score, igraph_arpack_rssolve, igraph_arpack_rnsolve

• Experimental C attribute interface added. I.e. it is possible to use graph/vertex/edge attributes from C code now.

• Edge weights for Fruchterman-Reingold layout.
• Line graph calculation.
• Kautz and de Bruijn graph generators
• Support for writing graphs in DOT format
• Jaccard and Dice similarity coefficients added
• igraph_count_multiple added
• igraph_is_loop and igraph_is_multiple “return” boolean vectors
• The graphopt layout algorithm was added, igraph_layout_graphopt
• Generation of “famous” graphs, igraph_famous
• Create graphs from LCF notation, igraph_lcf, igraph_lcf_vector
• igraph_add_edge adds a single edge to the graph
• Dyad census and triad cencus functions added
• igraph_is_simple added
• progress handlers are allowed to stop calculation
• igraph_full_citation to create full citation networks
• igraph_path_length_hist, create a histogram of path lengths
• forest fire model added
• DIMACS reader can handle different file types now
• Adjacency list types made public now (igraph_adjlist_t, igraph_adjedgelist_t)
• Biconnected components and articulation points can be computed
• Eigenvector centrality computation
• Kleinberg’s hub and authority scores
• igraph_to_undirected handles attributes now
• Geometric random graph generator can return the coordinates of the vertices
• Function added to convert leading eigenvector community structure result to a membership vector (igraph_le_community_to_membership)
• Weighted fast greedy community detection
• Weighted page rank calculation
• Functions for estimating closeness, betweenness, edge betweenness by introducing a cutoff for path lengths
• Weighted modularity calculation
• igraph_permute_vertices added
• Betweenness ans closeness calculations are speeded up
• Startup positions can be supplied to the Kamada-Kawai layout algorithms
• igraph_read_graph_* functions can handle all possible line terminators now (\r, \n, \r\n, \n\r)
• Error handling was rewritten for walktrap community detection, the calculation can be interrupted now
• The maxflow/mincut functions allow to supply a null pointer for edge capacities, implying unit capacities for all edges

Bugs corrected in the C library

• Memory leak fixed in adjacency list handling
• Memory leak fixed in maximal independent vertex set calculation
• Fixed a bug when rewiring undirected graphs with igraph_rewire
• Fixed edge betweenness community structure detection for unconnected graphs
• Make igraph compile with Sun Studio
• Betweenness bug fixed, when not computing for all vertices
• memory usage of clique finding reduced
• Corrected bugs for motif counts when not all motifs were counted, but a cut vector was used
• Bugs fixed in trait games and cited type game
• Accept underscore as letter in GML files
• GML file directedness notation reversed, more logical this way