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

java.lang.Object
  bcds.phison.gm.GraphMetricBase<V,E>
      bcds.phison.gm.BrandesBC<V,E>

All Implemented Interfaces:

GraphMetric<V,E>, WithEnvParams

Direct Known Subclasses:

AverageEdgeBC, AverageNodeBC

public class BrandesBC<V,E>
extends GraphMetricBase<V,E>
implements GraphMetric<V,E>

Computes the betweenness centrality of nodes and links in a directed graph. This is a wrapper on BetweennessCentrality but only the Brandes' version is exposed. Also, this class is stricter in checking that the parameters passed to BetweennessCentrality make sense.

Example of use:

    ...
    // With default parameters:
    GraphMetric<V, E> m = new BrandesBC<V, E>(g, null);

    // or with specific parameters:
    GraphMetric<V, E> m = new BrandesBC<V, E>(g, 
                             new Environ("BrandesBC.normalized", true,
                                         "BrandesBC.use_ecmp", false));
    Map<V, Double> nbc = m.getNodeMetric();
    ...
 

Author:

Juan Segovia S.

Constructor Summary

BrandesBC()
Default constructor.

BrandesBC(SimGraph<V,E> g, Environ env)
Creates a new instance and calls setup to complete the initialization.

Method Summary

java.lang.String	getDescription() Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.
java.util.Map<E,java.lang.Double>	getEdgeMetric() Returns the edge betweenness centrality of each node.
java.lang.Object[]	getEnvParams() Returns the environment parameters used by this class.
java.lang.String	getLabel() Returns "Betweenness centrality".
java.util.Map<V,java.lang.Double>	getNodeMetric() Returns the node betweenness centrality of each node.
boolean	isApplicableTo(MetricTarget m) Returns true if m is MetricTarget.NODE or EDGE.
void	run() Computes the betweenness centrality.
void	setup(SimGraph<V,E> g, Environ env) Reinitializes this instance.

Methods inherited from class bcds.phison.gm.GraphMetricBase

dump, getEnviron, getGraph, getGraphMetric, getGraphMetricStdev, getName

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface bcds.phison.gm.GraphMetric

dump, getGraphMetric, getGraphMetricStdev

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getName

Constructor Detail

BrandesBC

public BrandesBC()

Default constructor.

BrandesBC

public BrandesBC(SimGraph<V,E> g,
                 Environ env)

Creates a new instance and calls setup to complete the initialization.

Method Detail

isApplicableTo

public boolean isApplicableTo(MetricTarget m)

Returns true if m is MetricTarget.NODE or EDGE.

Specified by:

isApplicableTo in interface GraphMetric<V,E>

Overrides:

isApplicableTo in class GraphMetricBase<V,E>

setup

public void setup(SimGraph<V,E> g,
                  Environ env)

Reinitializes this instance. Performs the following verification of the environment parameters (see getEnvParams()).

Specified by:

setup in interface GraphMetric<V,E>

Overrides:

setup in class GraphMetricBase<V,E>

Throws:

java.lang.IllegalArgumentException - if environment parameters appear in unsupported combinations.

java.lang.RuntimeException - if "weighted" is true and the key "cost_map" does not exist, points to null or its value is not a Map of Numbers.

run

public void run()

Computes the betweenness centrality. If the environment parameter GraphMetric.target is MetricTarget.NODE or not present or its value is null, computes the node betweenness centrality; if it is MetricTarget.EDGE, computes the edge betweenness centrality.

Specified by:

run in interface GraphMetric<V,E>

Overrides:

run in class GraphMetricBase<V,E>

Throws:

java.lang.UnsupportedOperationException - if the computation target cannot be determined (either nodes or links).

getNodeMetric

public java.util.Map<V,java.lang.Double> getNodeMetric()

Returns the node betweenness centrality of each node. If this was not the metric computed in run, it is computed here before returning.

Specified by:

getNodeMetric in interface GraphMetric<V,E>

Overrides:

getNodeMetric in class GraphMetricBase<V,E>

getEdgeMetric

public java.util.Map<E,java.lang.Double> getEdgeMetric()

Returns the edge betweenness centrality of each node. If this was not the metric computed in run, it is computed here before returning.

Specified by:

getEdgeMetric in interface GraphMetric<V,E>

Overrides:

getEdgeMetric in class GraphMetricBase<V,E>

getLabel

public java.lang.String getLabel()

Returns "Betweenness centrality".

Specified by:

getLabel in interface GraphMetric<V,E>

getDescription

public java.lang.String getDescription()

Description copied from interface: GraphMetric

Returns a string describing the metric, for example, article where it has been published, URL where to find reference implementation, etc.

Specified by:

getDescription in interface GraphMetric<V,E>

getEnvParams

public java.lang.Object[] getEnvParams()

Returns the environment parameters used by this class. The parameters are prefixed with "BrandesBC." and are:

• normalized (default: true): normalize the the centrality values.
• weighted (default: false): use edge costs during the computation of shortest paths. If false, the cost is hop. If true, the parameter cost_map is required.
• use_ecmp (default: true): enables the discovery of equal cost multiple paths.
• include_end_points (default: false): whether to exclude the end points of a path when assesing the node importance. Only applicable to node betweenness centrality (it is ignored if the target is edge betweenness). It is incompatible with use_ecmp=true.
• cost_map (default: null): a non-null map suitable for use as link cost map with TED.

Additionally, it accepts GraphMetric.target as a hint. See GraphMetric.run().

Specified by:

getEnvParams in interface WithEnvParams

Overrides:

getEnvParams in class GraphMetricBase<V,E>