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 all listed here.

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

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

The biggest change in the R interface is that starting from this version vertices and edges are numbered from one. This change might be painful for many people, because it makes already existing code incompatible with igraph 0.6. To make the switch easier, there is now an igraph0 package on CRAN; igraph0 uses 0-based vertex and edge ids, and it can be used to run old code. Note, however, that igraph0 will not be developed in the future. Please use the igraph package for current and future work.

(Also note that in Python and C vertices and edges are still numbered from zero, as these languages traditionally use zero-based indexing.)

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

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

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

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

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

Igraph now implements the Spectral Coarse Graining method, by David Morton, our implementation is based on his code. 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.

All community detection functions return a
`communities`

object now. We have defined various
operations for these objects, see the
R manual for more.

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

Personalized PageRank scores. See the documentation.

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

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

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.

If you type in the name of an igraph object, the edges of the graph are not dumped to the screen any more, only a short summary of the graph is printed:

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

To see the graph structure, you can use the `str()`

function.
See more in the R
documentation.

There are now new and easier ways to add new vertices/edges to a graph, or remove existing ones. See the details in the R documentation. In Python, you can treat the graph as a virtual adjacency matrix. See the details in the Python documentation.

`igraphdata`

packageThe new R package igraphdata contains some example graph data sets.

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 `plot.igraph()`

function.

We have included some demos in the igraph R package, to get a list of the demos, type this at your R prompt:

```
> demo(package="igraph")
Demos in package ‘igraph’:
centrality Classic and other vertex centrality indices
cohesive Cohesive blocking, the Moody & White method
community Community structure detection
crashR A crash-course into R
smallworld Small-world networks
```

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

- Vertices and edges are numbered from 1 instead of 0.
Note that this makes most of the old R igraph code incompatible
with igraph 0.6. If you want to use your old code, please use
the
`igraph0`

package. - The
`[`

and`[[`

operators can now be used on igraph graphs, for`[`

the graph behaves as an adjacency matrix, for`[[`

is is treated as an adjacency list. It is also much simpler to manipulate the graph structure, i.e. add/remove edges and vertices, with some new operators. See more at`?graph.structure`

. - In all functions that take a vector or list of vertices or edges, vertex/edge names can be given instead of the numeric ids.
- New package
`igraphdata`

, contains a number of data sets that can be used directly in igraph. - Igraph now supports loading graphs from the Nexus online data
repository, see
`nexus.get()`

,`nexus.info()`

,`nexus.list()`

and`nexus.search()`

. - All the community structure finding algorithm return a
`communities`

object now, which has a bunch of useful operations, see`?communities`

for details. - Vertex and edge attributes are handled much better now. They
are kept whenever possible, and can be combined via a flexible API.
See
`?attribute.combination`

. - R now prints igraph graphs to the screen in a more structured and
informative way. The output of
`summary()`

was also updated accordingly.

- It is possible to mark vertex groups on plots, via shading. Communities and cohesive blocks are plotted using this by default.
- Some igraph demos are now available, see a list via
`demo(package="igraph")`

. - igraph now tries to select the optimal layout algorithm, when plotting a graph.
- Added a simple console, using Tcl/Tk. It contains a text area
for status messages and also a status bar. See
`igraph.console()`

. - Reimplemented igraph options support, see
`igraph.options()`

and`getIgraphOpt()`

. - Igraph functions can now print status messages.

- The multi-level modularity optimization community structure detection
algorithm by Blondel et al. was added, see
`multilevel.community()`

. - Distance between two community structures:
`compare.communities()`

. - Community structure via exact modularity optimization,
`optimal.community()`

. - Hierarchical random graphs and community finding, porting the code
from Aaron Clauset. See
`hrg.game()`

,`hrg.fit()`

, etc. - Added the InfoMAP community finding method, thanks to Emmanuel
Navarro for the code. See
`infomap.community()`

.

- Eccentricity (
`eccentricity()`

), and radius (`radius()`

) calculations. - Shortest path calculations with
`get.shortest.paths()`

can now return the edges along the shortest paths. `get.all.shortest.paths()`

now supports edge weights.

- Centralization scores for degree, closeness, betweenness and
eigenvector centrality. See
`centralization.scores()`

. - Personalized Page-Rank scores, see
`page.rank()`

. - Subgraph centrality,
`subgraph.centrality()`

. - Authority (
`authority.score()`

) and hub (`hub.score()`

) scores support edge weights now. - Support edge weights in betweenness and closeness calculations.
`bonpow()`

, Bonacich's power centrality and`alpha.centrality()`

, Alpha centrality calculations now use sparse matrices by default.- Eigenvector centrality calculation,
`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.

- Support the DL file format in
`graph.read()`

. See http://www.analytictech.com/networks/dataentry.htm. - Support writing the LEDA file format in
`write.graph()`

.

- Star layout:
`layout.star()`

. - Layout based on multidimensional scaling,
`layout.mds()`

. - New layouts
`layout.grid()`

and`layout.grid.3d()`

. - Sugiyama layout algorithm for layered directed acyclic graphs,
`layout.sugiyama()`

.

- New graph generators:
`static.fitness.game()`

,`static.power.law.game()`

. `barabasi.game()`

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

can now create graphs without loop edges.

- Added the Spectral Coarse Graining algorithm, see
`scg()`

. - The
`cohesive.blocks()`

function was rewritten in C, it is much faster now. It has a nicer API, too. See`demo("cohesive")`

. - Added generic breadth-first and depth-first search implementations
with many callbacks,
`graph.bfs()`

and`graph_dfs()`

. - 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,
`assortativity()`

,`assortativity.nominal()`

and`assortativity.degree()`

. - Vertex operators that work by vertex names:
`graph.intersection.by.name()`

,`graph.union.by.name()`

,`graph.difference.by.name()`

. Thanks to Magnus Torfason for contributing his code! - Function to calculate a non-induced subraph:
`subgraph.edges()`

. - More comprehensive maximum flow and minimum cut calculation,
see functions
`graph.maxflow()`

,`graph.mincut()`

,`stCuts()`

,`stMincuts()`

. - Check whether a directed graph is a DAG,
`is.dag()`

. `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. - Biconnected component calculation,
`biconnected.components()`

now returns the components themselves. `bipartite.projection()`

calculates multiplicity of edges.- Maximum cardinality search:
`maximum.cardinality.search()`

and chordality test:`is.chordal()`

- Convex hull computation,
`convex.hull()`

. - Contract vertices,
`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!