About igraph releases and other things

June 11, 2012

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 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`

.

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.

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

.

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.

- 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()`

.

- 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!