Selected Software of the Research Group

Parallel Network Analysis: NetworKit

NetworKit, aimed at large-scale network analysis, has been initiated and is maintained by our group. Contributions are welcome. More details and the source code can be found at the project website.

Subquadratic Generator of Random Hyperbolic Graphs

Random hyperbolic graphs are a promising family of synthetic networks. For the version using unit-disk neighborhoods in the hyperbolic plane, we provide a first generator within time complexity \(O((n^{3/2}+m) \log n)\) with high probability. Details can be found at the website and the preprint.

Probabilistic Range Queries

Range queries in spatial datasets are a well-established problem with applications in image processing, computer vision and numerous physical simulations. In some cases, the neighborhood of a given query point is probabilistic: The chance that a connection between two wireless nodes can be established depends on their distance, as does the probability that an infectious disease spreads between an infectious and a susceptible person. To handle these random fluctuations, we define a probabilistic neighborhood \(N(q,f)\) for a query point \(q\) and a connectivity decay function \(f\). Given some reasonable restrictions on the probability distribution of point locations and \(f\), we provide a fast query algorithm for the planar case with a time complexity of \(O((|N(q,f)| + \sqrt{n})\log n)\) with high probability. Details can be found at the website and the preprint.

Combinatorial Laplacian Solver with Nearly-linear Running Time

This is Daniel Hoske's implementation of the SimpleSolver proposed by Kelner et al. in their fascinating STOC 2013 paper. It turns out that we can confirm the theoretical results in that the running time is nearly linear in practice as well. However, the constants are very high. Therefore, we publish the code for people interested in the topic of nearly-linear solvers, but recommend more traditional approaches such as preconditioned CG for practical applications.
  • Reference:
    D. Hoske, D. Lukarski, H. Meyerhenke, M. Wegner: Is Nearly-linear the same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver. In Proc. 14th Intl. Symp. on Experimental Algorithms (SEA 2015), pp. 205-218. LNCS 9125, Springer-Verlag, 2015.
    [PDF at SpringerLink], (c) Springer-Verlag, [arXiv preprint]
  • Code:
    The code is available in this Mercurial repository.
  • Build instructions:
    For basic information on how to build the source code, we refer to the NetworKit documentation.
    In order to use the solver, you have to switch to the sdd branch by typing the command „hg up sdd“. For reproducing our results, you will need PAPI for hardware counters as well as the tested competitors Eigen and Paralution in addition to this source code. If you just want to test the solver itself, you can do that by adding the options „—eigen=no —paralution=no —vectorize=no —papi=no“ to the normal scons build command.

Parallel Sequence Assembly Techniques: PASQUAL (project led by Georgia Institute of Technology)

PASQUAL has been developed at the HPC lab of Georgia Institute of Technology. Henning Meyerhenke is a project member and contributed to the development since his time at the lab. Currently ports of PASQUAL to other platforms are being developed by external groups.

Graph Partitioning: Diffusion-based Partitioning (DibaP and PDibaP)

The project website is outdated but will be hosted at KIT and updated soon.

Tools

A crawler for extracting collaboration networks from arxiv.org is hosted on algohub.iti.kit.edu