This C++ library is intended for large-scale network analysis and computation. It can be used in two ways:
teexgraph
pyteexgraph
Several explicit design choices were made in in this library:
g++
compiler and the C++ standard library.Fast computation of the diameter of real-world networks, implementing the BoundingDiameters algorithm presented in:
F.W. Takes and W.A. Kosters, Determining the Diameter of Small World Networks, in Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 1191-1196, 2011. doi: 10.1145/2063576.2063748
Fast computation of extreme distance metrics: the radius, diameter, center size, periphery size and eccentricity distribution of large real-world networks, based on the algorithms presented in:
F.W. Takes and W.A. Kosters, Computing the Eccentricity Distribution of Large Graphs, Algorithms 6(1): 100-118, 2013. doi: 10.3390/a6010100
Computation of closeness centrality in parallel, exact or approximated using the method discussed in:
D. Eppstein and J. Wang, Fast Approximation of Centrality, Journal of Graph Algorithms and Applications 8(1): 39--45, 2004. doi: 10.7155/jgaa.00081
Computation of betweenness centrality in parallel, exact or an adapted approximate version of the method introduced in:
U. Brandes, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology 25(2): 163-177, 2001.
Of course, all credit goes to the original authors of these algorithms.
Optional: if you want the Python library you will need PyBind11. You can install it with:
sudo apt install pybind11-dev
Compile with the standard cmake sequence:
mkdir build
cd build
cmake ..
make
or make a debugging build with
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
make
Note: you may need gcc 4.7 or newer for all OpenMP functionality to work.
long
. This can be changed to for example string
in Graph.h at the cost of a factor 2 or more in loading speed. Friendly input files are expected; although comments (lines that do not start with a character in [a-zA-Z0-9]) at the beginning of the input file are allowed. After the first line with an edge, only edges are expected.If PyBind11 is installed and the programme is compiled as above, a file with a name similar to
build/pyteexgraph.cpython-39-x86_64-linux-gnu.so
will be generated. Make sure this is accessible from your Python working directory and use
import pyteexgraph
from within Python to load it. See python_example.py for some examples.
If your project uses cmake, then incorporating this package is easy!
Just add the following lines to your CMakeLists.txt
file:
add_subdirectory(path/to/teexgraph EXCLUDE_FROM_ALL)
target_link_libraries(your_executable_target PRIVATE teexgraphlib)
And everything should work.
This code was written for research-purposes only, and is and should in no way be seen as an attempt at creating a good piece of code with respect to any programming- or software-engineering standards whatsoever. It comes without any warranty of merchantability or suitability for a particular purpose. The software has exclusively been tested under the UNIX/Linux operating system, in particular Ubuntu LTS and CentOS.