FEPiC: Fast Estimation of Percolation Centrality. [Code]
FEPic is a progressive sampling based algorithm to approximate the percolation centrality of all nodes in a static graph. FEPiC uses Monte Carlo Empirical Rademacher Averages and variance aware bounds for the sample complexity to provide a high quality approximation of such a centrality measure. FEPiC extends the novel algorithm for the Betweenness Centrality by [Pellegrina and Vandin] to the Percolation Centrality. FEPiC is the best choice in terms of sample size, running time and quality of the approximation. The Julia library includes efficient (parallel) implementation of: (i) FEPiC (see [arXiv] for the original paper); (ii) the progressive sampling algorithm by [Lima et al.]; (iii) the fixed sample size algorithm by [Lima et al.]; and, an efficient version of the exact algorithm for the percolation centality. All the algorithms use multithreading and outperforms the already existing NetworkX implementations.
MANTRA: Temporal Betweenness Centrality Approximation through Sampling. [Code]
MANTRA is a progressive sampling based algorithm to approximate the temporal betweenness centrality of all nodes in a temporal graph. MANTRA uses Monte Carlo Empirical Rademacher Averages and variance aware results on sample complexity to provide a high quality approximation of the Shortest (Foremost) and Prefix Foremost Temporal Betweenness centralities [Buß et al.]. MANTRA is the best choice in terms of sample size, running time, and required space (linear in the size of the temproal graph) to provide high quality approximations of the temporal betweenness centrality. Furthermore, our framework can be easily extended to compute the temporal betwenness centrality of the temporal edges and thus provide fast and accurate clustering algorithms for temporal networks. In addition, our library includes a novel sampling-based approximation algorithm for the temporal (effective) diameter, average path length, and temporal connectivity rate for the temporal optimality criteria considered in our work (see [arXiv]). The Julia library includes efficient (parallel) implementations of: (i) our algorithms; (ii) a progressive sampling version of ONBRA [Santoro et al.] (extended to all the temporal path optimalities mentioned above); and, (iii) the exact algorithms in [Buß et al.]. Moreover, we fixed the issues with the original versions of the exact algorithms and ONBRA (see [arXiv]) that lead to overflows (on temporal networks with high number of temporal paths), underestimation of the centrality scores, and memory overflows. Indeed, our efficient parallel implementation of the exact algorithms can be usded to compute the exact temporal betweenness scores on huge temporal graphs.
PROPAGATE: a seed propagation framework to compute Distance-based metrics on Very Large Graphs. [Code]
PROPAGATE is a sampling based algorithm to approximate all the distance-based metrics (diameter, effective diameter, average distance, number of reachable pairs, connectivity rate, and geometric centralities (closeness, harmonic,lin). The Java library includes two efficient approximation algorithms (see [arXiv]). PROPAGATE is the best choice in terms of running time and required space (linear in the size of the graph) to provide high quality approximations of the aforementioned quantities.
The framework outperform the state of the art in approximating distance metrics.
TSBProxy:Temporal Shortest Betweenness Proxy. [Code]
TSBProxy is a suite of Proxies for the Temporal Shortest Betweennes Centrality. The suite includes efficient Julia (single thread) implementations of the Shortest Temporal and Prefix Foremost Temporal Betweenness algorithms [Buß et al.], their Ego-Temporal Betweennes versions, ONBRA algorithm (for the Shortest Temporal Betweenness) [Santoro et al.], and a novel notion of Temporal Degree that can be used as a proxy for the Shortest Temporal Betweenness rankings.
-
DREG:Dynamic Random Expander Generator. [Code]
DREG is a Python implementation of a generator that produces almost regular dynamic random graphs (or random temporal graphs) that are expander graphs at each round (time) with high probability.
|
