it.unimi.dsi.webgraph.algo

## Class BetweennessCentrality

• java.lang.Object
• it.unimi.dsi.webgraph.algo.BetweennessCentrality

• ```public class BetweennessCentrality
extends java.lang.Object```
Computes the betweenness centrality using an implementation of Brandes's algorithm (Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality”, Journal of Mathematical Sociology 25(2):163−177, 2001) that uses multiple parallel breadth-first visits.

To use this class you first create an instance, and then invoke `compute()`. After that, you can peek at the field `betweenness` to discover the betweenness of each node.

For every three distinct nodes s, t and v, let σst be the number of shortest paths from s to t, and σst(v) the number of such paths on which v lies. The betweenness centrality of node v is defined to be the sum of δst(v)=σst(v) / σst over all pairs of distinct nodes s, t different from v (the summand is assumed to be zero whenever the denominator is zero).

Brandes's approach consists in performing a breadth-first visit from every node, recording the distance of the node from the current source. After each visit, nodes are considered in decreasing order of distance, and for each of them we consider the arcs (v,w) such that the distance of w is exactly one plus the distance of v: in this case we say that v is a parent of w. Such parents are used to compute the values of δ (exactly as in the original algorithm, but without any need to keep an explicit set of parents, which is important since this class is memory intensive).

Every visit is independent and is carried out by a separate thread. The only contention point is the update of the array accumulating the betweenness score, which is negligible. The downside is that running on k cores requires approximately k times the memory of the sequential algorithm, as only the graph and the betweenness array will be shared.

This class keeps carefully track of overflows in path counters, and will throw an exception in case they happen. Thanks to David Gleich for making me note this serious problem, which is often overlooked.

• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`static class ` `BetweennessCentrality.PathCountOverflowException`
An exception telling that the path count exceeded 64-bit integer arithmetic.
• ### Field Summary

Fields
Modifier and Type Field and Description
`double[]` `betweenness`
The array of betweenness value.
`protected java.util.concurrent.atomic.AtomicInteger` `nextNode`
The next node to be visited.
`protected boolean` `stop`
Whether to stop abruptly the visiting process.
• ### Constructor Summary

Constructors
Constructor and Description
`BetweennessCentrality(ImmutableGraph graph)`
Creates a new class for computing betweenness centrality, using as many threads as the number of available processors.
```BetweennessCentrality(ImmutableGraph graph, int requestedThreads)```
Creates a new class for computing betweenness centrality.
```BetweennessCentrality(ImmutableGraph graph, int requestedThreads, ProgressLogger pl)```
Creates a new class for computing betweenness centrality.
```BetweennessCentrality(ImmutableGraph graph, ProgressLogger pl)```
Creates a new class for computing betweenness centrality, using as many threads as the number of available processors.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Computes betweenness centrality.
`static void` `main(java.lang.String[] arg)`
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### nextNode

`protected final java.util.concurrent.atomic.AtomicInteger nextNode`
The next node to be visited.
• #### stop

`protected volatile boolean stop`
Whether to stop abruptly the visiting process.
• #### betweenness

`public final double[] betweenness`
The array of betweenness value.
• ### Constructor Detail

• #### BetweennessCentrality

```public BetweennessCentrality(ImmutableGraph graph,
ProgressLogger pl)```
Creates a new class for computing betweenness centrality.
Parameters:
`graph` - a graph.
`requestedThreads` - the requested number of threads (0 for `Runtime.availableProcessors()`).
`pl` - a progress logger, or `null`.
• #### BetweennessCentrality

```public BetweennessCentrality(ImmutableGraph graph,
ProgressLogger pl)```
Creates a new class for computing betweenness centrality, using as many threads as the number of available processors.
Parameters:
`graph` - a graph.
`pl` - a progress logger, or `null`.
• #### BetweennessCentrality

```public BetweennessCentrality(ImmutableGraph graph,
Creates a new class for computing betweenness centrality.
Parameters:
`graph` - a graph.
`requestedThreads` - the requested number of threads (0 for `Runtime.availableProcessors()`).
• #### BetweennessCentrality

`public BetweennessCentrality(ImmutableGraph graph)`
Creates a new class for computing betweenness centrality, using as many threads as the number of available processors.
Parameters:
`graph` - a graph.
• ### Method Detail

• #### compute

```public void compute()
throws java.lang.InterruptedException```
Computes betweenness centrality. Results can be found in `betweenness`.
Throws:
`java.lang.InterruptedException`
• #### main

```public static void main(java.lang.String[] arg)
throws java.io.IOException,
java.lang.InterruptedException,
JSAPException```
Throws:
`java.io.IOException`
`java.lang.InterruptedException`
`JSAPException`