The Large Sparse Graph library is a C++ library for working with large sparse graphs (on disk, without loading them in memory). In particular, it includes methods used for computing related nodes in a graph, as discussed in a AAAI 2007 paper.
GNU make, a reasonably recent C++ compiler. The library has only been tested on i386-linux, x86_64-linux, and sun4u-sunos9 architectures, but should work with other architectures, possibly with minor changes.
"make" should be enough to compile the graph library lsg/lsg.a, as well as the executables.
./RunTests run all test units. Every test should pass. Note that the compilation of RunTests uses libtut, the Test Unit Framework (provided).
Build a PackedGraph from a file containing edges of the graph and a file with node labels (one per line). The edge file must be in either of the following format:
3
no values
0 1 2
1 2
2 0
or:
3
with values
0 1,1 2,3
1 2,3
2 0,1
(the second format allows weighted edges)
Each line after the first two is the adjacence list of a given source node (without or with weights). Each target node must appear exactly once, and target nodes must appear in order.
Compute the equilibrium measure of a strongly connected stochastic graph.
Test program for dumping XML graphs of the different steps of each "Related Nodes" method.
Extract the main strongly component of a graph.
Modify a graph by amplifying transition probabilities by log(1/nu_i), where nu is the equilibrium measure.
Stochastify a graph.
Compute PageRank over a graph.
Computed "Related Nodes" over a graph, through various different methods.
Compute the reversed Markov chain (with respect to a measure).
Give some basic statistics about a graph.
Compute the symmetrized Markov chain (with respect to a measure).
Convert between the two different representations of a (Row)Vector.
Print the number of ancestors of a node
ProvSQL is provided as open-source software under the MIT License. See LICENSE.
https://github.com/PierreSenellart/lsg
Pierre Senellart pierre@senellart.com
This is joint work with Yann Ollivier
Bug reports and feature requests are preferably sent through the Issues feature of GitHub.