by Joseph Rickert

The igraph package has become a fundamental tool for the study of graphs and their properties, the manipulation and visualization of graphs and the statistical analysis of networks. To get an idea of just how firmly igraph has become embedded into the R package ecosystem consider that currently igraph lists 72 reverse depends, 59 reverse imports and 24 reverse suggests. The following plot, which was made with functions from the igraph and miniCRAN packages, indicates the complexity of this network.

library(miniCRAN) library(igraph) pk <- c("igraph","agop","bc3net","BDgraph","c3net","camel", "cccd", "CDVine", "CePa", "CINOEDV", "cooptrees","corclass", "cvxclustr", "dcGOR", "ddepn","dils", "dnet", "dpa", "ebdbNet", "editrules", "fanovaGraph", "fastclime", "FisHiCal", "flare", "G1DBN", "gdistance", "GeneNet", "GeneReg", "genlasso", "ggm", "gRapfa", "hglasso", "huge", "igraphtosonia", "InteractiveIGraph", "iRefR", "JGL", "lcd", "linkcomm", "locits", "loe", "micropan", "mlDNA", "mRMRe", "nets", "netweavers", "optrees", "packdep", "PAGI", "pathClass", "PBC", "phyloTop", "picasso", "PoMoS", "popgraph", "PROFANCY", "qtlnet", "RCA", "ReliabilityTheory", "rEMM", "restlos", "rgexf", "RNetLogo", "ror", "RWBP", "sand", "SEMID", "shp2graph", "SINGLE", "spacejam", "TDA", "timeordered", "tnet") dg <- makeDepGraph(pk) plot(dg,main="Network of reverse depends for igraph",cex=.4,vertex.size=8)

The igraph package itself is a tour de force with over 200 functions. Learning the package can be a formidable task especially if you are trying to learn graph theory and network analysis at the same time. To help myself through this process, I sorted the functions in the igraph package into seven rough categories:

- Create Graph
- Describe Graph
- Environment
- Find Communities
- Operate on a Graph
- Plot
- Statistics

The following shows a portion of the table for the first 10 functions related to creating graphs.

Function | Description | Category of Function | |

1 | aging.prefatt.game | Generate an evolving random graph with preferential attachment and aging | Create Graph |

2 | barabasi.game | generate scale-free graphs according to the Barabasi-Albert model | Create Graph |

3 | bipartite.random.game | Generate bipartite graphs using the Erdos-Renyi model | Create Graph |

4 | degree.sequence.game | Generate a random graph with a given degree degree sequence | Create Graph |

5 | erdos.renyi.game | Generate random graphs according to the Erdos-Renyi model | Create Graph |

6 | forest.fire.game | Grow a network that simulates how a fire spreads by igniting trees | Create Graph |

7 | graph.adjacency | Create an igraph from an adjacency matrix | Create Graph |

8 | graph.bipartite | Create a bipartite graph | Create Graph |

9 | graph.complementer | Create the complementary graph for a given graph | Create Graph |

10 | graph.empty | Create an empty graph | Create Graph |

The entire table may be downloaded here: Download Igraph_functions.

infomap.community() is an intriguing function listed under the Finding Communities category that looks for structure in a network by minimizing the expected description length of a random walker trajectory. The abstract to the paper by Rosvall and Bergstrom that introduced this method states:

To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships.

I am not willing to claim that the 37 communities found by the algorithm represent meaningful structure, however, the idea of partitioning the network based on information flow does seem relevant to the package building process. Anybody looking for a research project?

imc <- infomap.community(dg) imc # Graph community structure calculated with the infomap algorithm # Number of communities: 37 # Modularity: 0.5139813 # Membership vector:

Some additional resources for working with igraph are:

- The igraph home page
- A presentation by Gábor Csrádi, igraph's principle author
- An old post with some pointers to additional resources
- A nice couple of nice tutorials: here and here.
- The new book: Statistical Analysis of Network Data with R by Eric D. Kolaczyk and Gábor Csrádi is a very good read.