Graph computation

December 17, 2014 — September 20, 2020

compsci
networks

Engines for calculating things on or about graphs. Which is everything, in a trivial case, but usually when we talk about graph computation we mean things that are more simply or more elegantly represented as graphs, which usually implies having some kind of sparsity in edges.

For specific applications of such computations, see e.g. graphical models or complex networks, inference on social graphs etc. Sometimes we use a linear algebra representation of a graph connectivity pattern, e.g. a graph Laplacian, and in that context some graph algorithms can be represented as matrix factorisation or similar problems.

A prime example of such a thing is Laplacians.jl (Julia):

Laplacians is a package containing graph algorithms, with an emphasis on tasks related to spectral and algebraic graph theory. It contains (and will contain more) code for solving systems of linear equations in graph Laplacians, low stretch spanning trees, sparsifiation, clustering, local clustering, and optimization on graphs.

All graphs are represented by sparse adjacency matrices. This is both for speed, and because our main concerns are algebraic tasks. It does not handle dynamic graphs. It would be very slow to implement dynamic graphs this way.

The other options that follow are more general creatures than this.

1 References

Bonald, de Lara, Lutz, et al. 2020. Scikit-Network: Graph Analysis in Python.” Journal of Machine Learning Research.
Otasek, Morris, Bouças, et al. 2019. Cytoscape Automation: Empowering Workflow-Based Network Analysis.” Genome Biology.
Shannon, Markiel, Ozier, et al. 2003. Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks.” Genome Research.