Release Notes

igraph 0.6 is a major new release of igraph. It contains many new features and major changes, a lot of bug fixes and improvements. As always, we are grateful to the people who sent comments, bug reports, questions, and specially to people who contributed code.

See below a list of major changes, with links to the relevant sections of the documentation. New features are all listed here.

The Nexus repository

igraph supports the Nexus network repository from R and from Python. Nexus is an online database of network data sets. You can search Nexus and download network from it directly from R and Python. See the documentation for details.

Support for Python 3.x

The Python interface of igraph now supports Python 3. The current release was tested with Python 3.2 on Windows, Linux and Mac OS X. Please report any bugs you encounter when using igraph in Python 3.x through the usual channels.

Community detection improvements

Community structure detection via exact modularity optimization. As modularity optimization in an NP-complete problem, this works only for small graphs, Python manual.

The multi-level modularity optimization algorithm by Blondel et al. was added. See documentation.

We support now the InfoMAP community finding method, thanks to Emmanuel Navarro for the code. More.

The edge betweenness community detection method of Newman and Girvan now also works on weighted graphs. See the documentation.

We have added some functions to compare various community structures. See the documentation.

The cohesive block finding functions were rewritten from scratch in C. They are much faster now, and they have a nicer API, too. See the documentation.

Centrality-related functions

Personalized PageRank scores. See the documentation.

Authority and hub scores, betweenness and closeness calculations all support edge weights now. See the documentation.

Sugiyama layout

Igraph now implements the Sugiyama layout algorithm for layered directed acyclic graphs. See the documentation.

Maximum matchings in bipartite graphs

Igraph now implements the push-relabel algorithm and the Kuhn-Munkres algorithm (also known as the Hungarian method) to find maximum matchings in unweighted and weighted bipartite graphs. See the documentation.

Named graph vertices

The Python interface now treats the name attributes in a special way. The values of the attribute are indexed in the background, allowing the retrieval of a vertex with a given name in amortized constant time. Furthermore, most of the graph query methods accept vertex names as well as vertex indices. See the documentation for more information.

Pretty-printed graph summaries

The same graph summary format used by R is now also adopted by Python. Printing a graph with the print statement now prints the summary and the edge list in a concise format:

>>> print karate
IGRAPH UNW- 34 78 -- Zachary's karate club network
+ attr: Author (g), Citation (g), name (g), Faction (v), id (v), name(v),
  weight (e)
+ edges (vertex names):
    Mr Hi -- Actor 2, Actor 3, Actor 4, Actor 5, ...
  Actor 2 -- Mr Hi, Actor 3, Actor 4, ...
...

Printing a graph with the summary() function (in the igraph namespace) prints the short summary only, without the edge list:

>>> summary(karate)
IGRAPH UNW- 34 78 -- Zachary's karate club network
+ attr: Author (g), Citation (g), name (g), Faction (v), id (v), name(v),
  weight (e)

Printing a graph with summary(graph, full=True) prints the summary, the edge list, the vertex and the edge attributes as well.

Easier manipulation of graphs

You can treat the graph as a virtual adjacency matrix. See the details in the documentation.

Mark groups of vertices in R and Python plots

You can mark vertex groups on graph plots, using shaded areas. Communities and cohesive blocks are plotted using technique by default. See the mark_groups argument of the Graph.__plot__ function.

Refactored graph drawers in the Python interface

Graphs in the Python interface are plotted by graph drawer classes now instead of a monolithic plotting function. This allows one to replace the default graph drawer with custom graph drawers; for instance, a drawer that sends an igraph graph to an UbiGraph display or to Cytoscape. The default graph drawer also allows the partial customization of the plot with pluggable vertex shapes and edge drawers.

Better handling of attributes in R and Python

In R and Python, many igraph functions keep the vertex, edge and graph attributes now, when one manipulates the graph. The attributes can also be combined using a flexible API. See the combine_edges and combine_attrs arguments of many graph methods in the Python documentation for more.

New in the Python interface

General updates

• Python 3.x is now supported by the Python interface.
• Graphs can now be treated as adjacency matrices by indexing the graph object using a pair of vertex ids or vertex names.
• Methods accepting a vertex id or a list of vertex ids should now also accept vertex names instead. Names should be given in the name vertex attribute.
• Igraph now supports loading graphs from the Nexus online data repository, see Nexus.get(), Nexus.info(), Nexus.list() and Nexus.search().

Community detection

• The multi-level modularity optimization community structure detection algorithm by Blondel et al. was added, see Graph.community_multilevel().
• Distance between two community structures: compare_communities().
• Community structure via exact modularity optimization, Graph.community_optimal_modularity().
• Added the InfoMAP community finding method, thanks to Emmanuel Navarro for the code. See Graph.community_infomap().
• Edge betweenness community detection now supports weighted graphs; see Graph.community_edge_betweenness().

Shortest paths

• Eccentricity (Graph.eccentricity()), and radius (Graph.radius()) calculations.
• Shortest path calculations with Graph.get_shortest_paths() can now return the vertex or edge ids along the shortest paths.
• Graph.get_all_shortest_paths() now supports edge weights.
• Neighborhood of a vertex can now be retrieved with Graph.neighborhood()

Centrality

• Personalized Page-Rank scores, see Graph.pagerank().
• Authority (Graph.authority_score()) and hub (Graph.hub_score()) scores support edge weights now.
• Support edge weights in betweenness and closeness calculations.
• Eigenvector centrality calculation, Graph.evcent() now works for directed graphs.
• Betweenness calculation can now use arbitrarily large integers, this is required for some lattice-like graphs to avoid overflow.

Input/output and file formats

• Support the DL file format in Graph.read(). See http://www.analytictech.com/networks/dataentry.htm.
• Support writing the LEDA file format in Graph.write().

Plotting and layouts

• Star layout: Graph.layout_star().
• Layout based on multidimensional scaling, Graph.layout_mds()
• Grid layouts: Graph.layout_grid(), Graph.layout_grid_3d()
• Sugiyama layout algorithm for layered directed acyclic graphs: Graph.layout_sugiyama().
• It is possible to mark vertex groups on plots using the mark_groups keyword argument of Graph.__plot__(). Communities and cohesive blocks are plotted using this by default. Note that the same keyword argument is also accepted by plot() of course.
• Redesigned graph plotting framework: graph drawers are now derived from AbstractGraphDrawer. The framework allows the implementation of custom graph drawers such as UbiGraphDrawer or CytoscapeDrawer. Edges are drawn by edge drawer classes (derived from AbstractEdgeDrawer), custom vertex shapes are now possible by ShapeDrawers.
• Multiple edges are now drawn curved to make them visible. See the autocurve and edge_curved keyword arguments of Graph.__plot__(). Note that these are also accepted by plot() of course.
• Better label placement algorithm supports multi-line labels and the specification of the distance and angle of the label relative to the center of the node.
• Added rescale() function to rescale a list of numeric values to a different range, suitable for plotting.

Graph generators

• New graph generators: Graph.Static_Fitness(), Graph.Static_Power_Law().
• Graph.Barabasi() was rewritten and it supports three algorithms now, the default algorithm does not generate multiple or loop edges. The graph generation process can now start from a supplied graph.
• The Watts-Strogatz graph generator, Graph.Watts_Strogatz() can now create graphs without loop edges.

Others

• Vertex and edge attributes are handled much better now. They are kept whenever possible, and can be combined via the combine_edges and combine_attrs keyword arguments of Graph.simplify(), Graph.contract_vertices() and Graph.to_undirected().
• Graphs are now printed in a more concise and informative way. print() prints a short information header and the edge list, while summary() prints the heder only. summary() also understands keyword arguments that control which parts of the output should be added; see the GraphSummary class.
• Motif search can now call a callback function for every motif found, see Graph.motifs_randesu()
• Transitivity calculations now support weights, see Graph.transitivity_local_undirected()
• Added cohesive block calculation, see Graph.cohesive_blocks()
• Added feedback arc sets, see Graph.feedback_arc_set()
• It is now possible to ask for the Jaccard or Dice similarities of pairs of vertices only, see Graph.similarity_jaccard_pairs() and similar functions.
• Support vertex and edge coloring in the VF2 (sub)graph isomorphism functions (Graph.isomorphic_vf2(), Graph.count_isomorphisms.vf2(), Graph.get_isomorphisms_vf2(), Graph.subisomorphic_vf2(), Graph.count_subisomorphisms_vf2(), Graph.get_subisomorphisms_vf2()).
• Assortativity coefficient, Graph.assortativity(), Graph.assortativity_nominal() and Graph.assortativity_degree().
• Function to calculate a non-induced subraph: Graph.subgraph_edges().
• Graph.has_multiple() to decide whether a graph has multiple edges.
• Added a function to calculate a diversity score for the vertices, Graph.diversity().
• Graph Laplacian calculation (Graph.laplacian()) supports edge weights now.
• Graph.bipartite_projection() calculates multiplicity of edges.
• Vertex contraction, Graph.contract_vertices().

We also fixed numerous bugs, too many to include them here, sorry. You may look at our bug tracker at https://bugs.launchpad.net/igraph to check whether a bug was fixed or not. Thanks for all the people reporting bugs. Special thanks to Minh Van Nguyen for a lot of bug reports, documentation fixes and contributed code!