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

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.

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

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.

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.

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.

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

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.

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.

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.

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

.

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

.

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

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

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

.

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

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

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