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 in R, Python, and C are all listed here.

See at the end for a (more) complete list of changes.

Community detection improvements

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

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

Hierarchical random graphs and community finding, based on the code from Aaron Clauset. See In the manual for details.

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

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

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

Igraph now implements the Spectral Coarse Graining method, by David Morton, our implementation is based on his code. See the manual.

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

Centrality-related functions

Centralization scores for degree, closeness, betweenness and eigenvector centrality. See the manual.

Personalized PageRank scores. See the manual.

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

Sugiyama layout

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

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 manual.

New in the C layer

• Maximum cardinality search: igraph_maximum_cardinality_search() and chordality test: igraph_is_chordal().
• Support the DL file format, igraph_read_graph_dl(). See http://www.analytictech.com/networks/dataentry.htm.
• Added generic breadth-first and depth-first search implementations with many callbacks (igraph_bfs(), igraph_dfs()).
• Centralization scores for degree, closeness, betweenness and eigenvector centrality, see igraph_centralization().
• Added igraph_sparsemat_t, a type that implements sparse matrices based on the CXSparse library by Tim Davis. See http://www.cise.ufl.edu/research/sparse/CXSparse/.
• Personalized Page-Rank scores, igraph_personalized_pagerank() and igraph_personalized_pagerank_vs().
• Assortativity coefficient, igraph_assortativity(), igraph_assortativity_nominal(), and igraph_assortativity_degree().
• The multi-level modularity optimization community structure detection algorithm by Blondel et al. was added, see igraph_community_multilevel().
• Added the igraph_version() function.
• Star layout: igraph_layout_star().
• Function to calculate a non-induced subraph: igraph_subgraph_edges().
• Distance between two community structures: igraph_compare_communities().
• Community structure via exact modularity optimization, igraph_community_optimal_community().
• More comprehensive maximum flow and minimum cut calculation, see functions igraph_maxflow(), igraph_mincut(), igraph_all_st_cuts(), igraph_all_st_mincuts().
• Layout based on multidimensional scaling, igraph_layout_mds().
• It is now possible to access the random number generator(s) via an API. Multiple RNGs can be used, from external sources as well. The default RNG is MT19937.
• Added igraph_get_all_shortest_paths_dijkstra, for calculating all non-negatively weighted shortest paths.
• Check whether a directed graph is a DAG, igraph_is_dag().
• Cohesive blocking, a’la Moody & White, igraph_cohesive_blocks().
• Igraph functions can now print status messages, see igraph_status() and related functions.
• Support writing the LEDA file format, igraph_write_graph_leda().
• Contract vertices, igraph_contract_vertices().
• The C reference manual has now a lot of example programs.
• Hierarchical random graphs and community finding, porting the code from Aaron Clauset. See igraph_hrg_game(), igraph_hrg_fit(), etc.
• igraph_has_multiple() to decide whether a graph has multiple edges.
• New layouts igraph_layout_grid() and igraph_layout_grid_3d().
• igraph_integer_t is really an integer now, it used to be a double.
• igraph_minimum_spanning_tree(), calls either the weighted or the unweighted implementation.
• Eccentricity (igraph_eccentricity()), and radius (igraph_radius()) calculations.
• Several game theory update rules, written by Minh Van Nguyen. See igraph_deterministic_optimal_imitation(), igraph_stochastic_imitation(), igraph_roulette_wheel_imitation(), igraph_moran_process(),
• Sugiyama layout algorithm for layered directed acyclic graphs, igraph_layout_sugiyama().
• New graph generators: igraph_static_fitness_game(), igraph_static_power_law_game().
• Added the InfoMAP community finding method, thanks to Emmanuel Navarro for the code. See igraph_community_infomap().
• Added the Spectral Coarse Graining algorithm, see igraph_scg().
• Added a function to calculate a diversity score for the vertices, igraph_diversity().

Major changes in the C layer

• Authority (igraph_authority_score()) and hub (igraph_hub_score()) scores support edge weights now.
• Graph Laplacian calculation (igraph_laplacian()) supports edge weights now.
• Support edge weights in betweenness (igraph_betweenness()) and closeness (igraph_closeness()) calculations.
• Support vertex and edge coloring in the VF2 graph isomorphism algorithm (igraph_isomorphic_vf2(), igraph_count_isomorphisms_vf2(), igraph_get_isomorphisms_vf2(), igraph_subisomorphic_vf2(), igraph_count_subisomorphisms_vf2(), igraph_get_subisomorphisms_vf2()).
• Added print operations for the igraph_vector*_t, igraph_matrix*_t and igraph_strvector_t types.
• Biconnected component calculation (igraph_biconnected_components()) can now return the components themselves.
• Eigenvector centrality calculation, igraph_eigenvector_centrality() now works for directed graphs.
• Shortest path calculations with get_shortest_paths() and get_shortest_paths_dijkstra() can now return the edges along the paths.
• Betweenness calculation can now use arbitrarily large integers, this is required for some lattice-like graphs to avoid overflow.
• igraph_bipartite_projection() calculates multiplicity of edges.
• igraph_barabasi_game() was rewritten and it supports three algorithms now, the default algorithm does not generate multiple or loop edges.
• The Watts-Strogatz graph generator, igraph_watts_strogatz() can now create graphs without loop edges.
• igraph should be now thread-safe, on architectures that support thread-local storage (Linux and Windows: yes, Mac OSX: no).

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!