Skip to content

Repository for the code of "ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks" (Santoro and Sarpe -TheWebConf 2022)

Notifications You must be signed in to change notification settings

iliesarpe/ONBRA

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 

Repository files navigation

ONBRA Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks (Santoro and Sarpe, TheWebConf 2022)

How to build

  • mkdir build.build
  • cd build.build
  • cmake ../src
  • make

How to use

  • Build (see How to build above)
  • Use the ./onbra executable by supplying a graph in the proper format (described below)
  • Use ./onbra -h to see a list of available flags and options
  • Note: option -E selects if you need to compute the Temporal Betweenness for shortest paths (set it to 1) or for shortest $\delta$-restless walks (set it to 3 and in such case you will also need the parameter -D)

Example to use ONBRA for shortest paths with a sample size of 1000 pairs of nodes over 10 executions and appending all the results in "result.txt": ./onbra -f <filename> -d -s -E 1 -S 1000 -I 10 &> result.txt

Example to use ONBRA for restless walks with a sample size of 1000 pairs of nodes, delta 3200, over 10 executions and appending all the results in "result.txt": ./onbra -f <filename> -d -s -E 3 -S 1000 -I 10 -D 3200 &> result.txt

Output of ONBRA

A sample of the output that you may obtain by running ONBRA is the following (we comment each line by adding an arrow (→)):

Samples used: $S$$S$: is the sample size you provided in input.
Bound epsilon, max with $S$ samples is: $\varepsilon$$\varepsilon$: is a bound on the supremum deviation in current iteration using the empirical Bernstein bound (see paper).
Time to initizialize structures: $t_1$$t_1$: time needed to initialize internal structures to ONBRA
Time to compute forward paths: $t_2$$t_2$: time to compute paths for sampled pairs of nodes
Time to compute betweenness values: $t_3$$t_3$: time used to process identified paths to update node values
Paths to s-z found: $P$$P$: number of pairs of nodes $(s,z)$ sampled for which there exists at least a path from $s$ to $z$.
Time needed to read and run sampling alg: $t_{tot}$$t_{tot}$: total time to run an iteration of ONBRA (is at least $t_1+t_2+t_3$)
Node 0: $[b(0)_1' \cdots b(0)_I']$ -> each $b(0)_i'$ is the estimate obtained by ONBRA in $i$-th iteration ($i \in [1,I]$) for node 0
$\cdots$
Node $n-1$: $[b(n-1)_1' \cdots b(n-1)_I']$ -> each $b(n-1)_i'$ is the estimate obtained by ONBRA in $i$-th iteration ($i \in [1,I]$) for node $n-1$

Graph format for input into the ONBRA

Temporal graphs which are read by the benchmark suite need to have the following form:

  • A graph is represented by a sequence of lines, with each corresponding to a temporal edge in the graph
  • Node IDs should be non negative integers (starting from 0 included), such as 42 or 302 are valid node IDs.
  • Timestamps must be positive integers (strictly greater than 0) but such that they fit inside 64-bit signed integer
  • Each line of the input must start with the following description of an edge: ID of the origin (tail) node, ID of the destination (head) node, timestamp, all separated by (non-newline) whitespace.
  • We assume the input network is pre-processed such that edges appear time-ordered, and nodes appear sequentially, i.e., node id $i$ cannot appear on one edge before $i-1$ has not been seen on some other edge. We provide a script to preprocess a dataset in the folder utils.
  • Self-loops and duplicate edges are allowed, however they will be ignored Example of a valid temporal network:
    0 1 1
    1 2 1
    1 2 2
    2 3 3

About

Repository for the code of "ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks" (Santoro and Sarpe -TheWebConf 2022)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published