Repository associated to the paper "MANTRA: Temporal Betweenness Centrality Approximation through Sampling".
The input file must be a temporal edge list, one line for each temporal edge (a temporal edge is a triple (u,v,t), where u and v are two vertices and t is one time in which the edge from u to v is available). All the graph are considered directed (if a graph is undirected it must have both temporal edges (u,v,t) and (v,u,t)). Nodes can be identified by any string (not necessarily a number), while time instants must be integer valued. The three elements of a temporal edge can be separated by any string, which can be specified while using the load_temporal_graph function (see below). In the following, we assume that this string is just a white-space.
The file can include duplicate lines and self-loops, however the tool will ignore them. In case your file contains duplicate lines or self-loops lines and you want to manually remove them, you can first execute the following bash command.
awk '($1!=$2)' <in_file_name> | sort | uniq > <out_file_name>.txt
You can then use the newly generated file as input to the tool.
In order to properly run the multi-threading implementations of our approaches you need to set the number of threads that you desire to use with:
julia --threads 16
where the number indicates the number of thread to use, for more information we refer to the official documentation: Starting Julia with multiple threads
To reproduce all the experiment you need to:
(i) Compute the exact temporal betweenness values running the command julia --threads <nthreads> compute_exact_temporal_bc.jl
(ii) Compute MANTRA's approximation, running julia --threads <nthreads> compute_mantra.jl
(iii) Compute ONBRAS's approximation, running julia --threads <nthreads> compute_onbra.jl
where <nthreads> is the number of assigned threads.
All the results will be automatically saved in the scores and times folders.
Finally, to summarize the results run julia analyze_results.jl, this command will create a new folder called analysis with all the results showed in the paper.
Here we describe how to run MANTRA on a general input temporal graph.
The algorithm has the following input parameters:
(-) Temporal Graph (temporal_graph)
(-) The absolute approximation precision epsilon (Float64)
(-) The confidence value delta (Float64)
(-) Whether the BigInt data type must be used (Bool)
(-) The estimator that must be used (String - options: 1- ob:ONBRA estimator, 2-trk (default) TRK estimator, 3-rtb random temporal betweenness estimator)
(-) The temporal path optimality that must be considered while computing the temporal betweenness (String - options: 1- sh (default) Shortest, 2- sfm Shortest-foremost, 3- pfm Prefix-foremost)
(-) Whether to use the VC-Upperbound or the Variance Upperbound (Bool , False default, i.e., Variance Upperbound is used as default)
(-) The geometric sampler value (Float64, default 1.2)
(-) Diameter of the analyzed input graph (Int64, -1 as defalut value. If the value is set to -1 the algorithm approximates the diameter using the fast-sampling method described in our paper)
Open Julia Repl in the main folder (where all the .jl scripts are) using the command
julia --threads <number of threads>
Next, include MANTRA
include("src/MANTRA.jl")
Load the temporal graph that must be analyzed
tg = load_temporal_graph("graphs/00_workplace.txt"," ")
notice: the temporal graph loader has two input parameters: (i) the temporal graph file and (ii) the file separator
Run MANTRA,
resut = progressive_mantra(tg,0.07,0.1,false,"ob","pfm")
the above command will compute a (0.07,0.1)-Approximation using the ONBRA (ob) estimator for the Prefix Foremost Temporal Betweenness
Save the output to file
save_results_progressive_sampling("workplace","mantra_ob_pfm",result[1],result[2],result[4],1,0.07)