BetweennessCentrality

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

bcds.phison.gm
Class BetweennessCentrality<V,E>

java.lang.Object
  bcds.phison.ra.RoutingAlgBase<V,E>
      bcds.phison.gm.BetweennessCentrality<V,E>

public class BetweennessCentrality<V,E>
extends RoutingAlgBase<V,E>
extends RoutingAlgBase<V,E>

WARNING: This class will disappear as such (the Brandes' part will be folded into BrandesBC, and the rest...probably taken to the attic. BetweennessCentrality computes the betweenness centrality (BC) of nodes and links in a directed graph.

Two implementations are provided here:

A "slow" one: Based mostly word-by-word on the definition of BC. It is slow because Dijkstra is run blindly for every pair of nodes, that is, given a source s and destinations d1, d2,..., dn, we simply call DijkstraAll(s, d1), DijkstraAll(s, d2), even though we already computed the mincost to d2 in the first run. See nodeBC_slow() and edgeBC_slow().
Brandes': An almost literal translation from a source found in the Internet called centrality.py (Python) by Aric Hagberg and others. That source is, in turn, a literal transcription of the algorith given in:

"On Variants of Shortest-Paths Betweenness Centrality and their Generic Computation", Ulrik Brandes, Social Networks, 2007.
There are several redundant code in this (Python) source but I prefer not to change it. See brandesNodeBC() and brandesEdgeBC().

The Python's source was adapted for making optional:

the discovery of "equal cost minimum paths" (enabled by default in Brandes'). See the flag BRANDES_NO_ECMP.
the inclusion of end points (Brandes' does not include them by default). See flag INCLUDE_END_POINTS.

These two implementations are not equivalent, i.e., they do not always produce the same values. The first (Juan Segovia's) implementation is "reasonable" (it is possible to follow it). Debugging messages can be actividated by setting the environment variable DL_Level:

 $ export DL_Level=0

Available options (Flags): The following options/flags are available. None of them are set (on) by default.

NORMALIZE: the BC produced is in the range [0..1). The specific normalization factor employed depends on the version of the altorighm.
INCLUDE_END_POINTS:
BRANDES_NO_ECMP:
WEIGHTED: Uses either hop count or "cost" to discover shortest paths.
AS_UNDIRECTED: Not used.

Nested Class Summary
`static class`	`BetweennessCentrality.Flags`

Constructor Summary
`BetweennessCentrality(TED<V,E> ted)`

Method Summary
`void`	`addFlag(BetweennessCentrality.Flags f)`
`void`	`brandesEdgeBC()`
`void`	`brandesNodeBC()`
`void`	`edgeBC_faster()`
`void`	`edgeBC_slow()`
`java.util.Map<E,java.lang.Double>`	`getEdgeBC()`
`java.util.Set<BetweennessCentrality.Flags>`	`getFlags()`
`java.util.Map<V,java.lang.Double>`	`getNodeBC()`
`void`	`nodeBC_slow()` nodeBC_slow() is not really "slow", only slightly slower than brandesNodeBC().
`void`	`removeFlag(BetweennessCentrality.Flags f)`
`void`	`setIngressEgressSet(java.util.Set<V> ingress_set, java.util.Set<V> egress_set)`
`void`	`setTrafficMatrix(java.util.Map<SimplePair<V,V>,java.lang.Double> trf)`

Methods inherited from class bcds.phison.ra.RoutingAlgBase
`buildPathFromParentNodes, commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getEnviron, getEnvParams, getName, getTED, getWorkingPath, offersProtection, setBackupPath, setRequest, setup, setWorkingPath, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail