Package es.uam.eps.ir.relison.sna.metrics.distance

Class CompleteDistanceCalculator<U>

java.lang.Object
es.uam.eps.ir.relison.sna.metrics.distance.CompleteDistanceCalculator<U>
Type Parameters:
U - Type of the users.
All Implemented Interfaces:
DistanceCalculator<U>
public class CompleteDistanceCalculator<U>
extends java.lang.Object
implements DistanceCalculator<U>
Computes some of the distance based metrics: distances, number of geodesic paths between two nodes, betweenness.

References:

  1. M.E.J. Newman. Networks: an introduction (2010)
  2. M.E.J. Newman, M. Girvan. Finding and Evaluating Community Structure in Networks. Physical Review E 69(2): 026113 (2004)

  • Field Summary

    Fields 
    Modifier and Type Field Description
    private double asl
    Average shortest path length.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesFrom
    Distances map from u to v.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesTo
    Distances map towards the key user.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> edgeBetweenness
    Edge betweenness map.
    private boolean flag
    Flag for detecting whether the algorithm should or should not stop.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> geodesics
    Number of minimum distance paths between two nodes.
    private Graph<U> graph
    Graph the betweenness metrics are built for.
    private double infiniteDistances
    Number of pairs at infinite distance to each other.
    private java.util.Map<U,​java.lang.Double> nodeBetweenness
    Nodes betweenness map.
    private Communities<U> scc
    Strongly connected components.

  • Constructor Summary

    Constructors 
    Constructor Description
    CompleteDistanceCalculator()
    Constructor.

  • Method Summary

    Modifier and Type Method Description
    boolean computeDistances​(Graph<U> graph)
    Computes the distances between nodes in a network.
    double getASL()
    Obtains the average shortest path length, averaged over all the finite distance paths.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getDistances()
    Returns all the distances between different pairs.
    double getDistances​(U orig, U dest)
    Returns the distance between two nodes.
    java.util.Map<U,​java.lang.Double> getDistancesFrom​(U node)
    Return the distances between a node and the rest of nodes in the network.
    java.util.Map<U,​java.lang.Double> getDistancesTo​(U node)
    Returns the distance between the network and an specific node.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getEdgeBetweenness()
    Gets all the values of the edge betweenness.
    java.util.Map<U,​java.lang.Double> getEdgeBetweenness​(U node)
    Returns the edge betweenness of all the adjacent edges to a given node.
    double getEdgeBetweenness​(U orig, U dest)
    Returns the edge betweenness of a single edge.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getGeodesics()
    Returns the number of geodesic paths between different pairs.
    java.util.Map<U,​java.lang.Double> getGeodesics​(U node)
    Return the number of geodesic paths between a node and the rest of nodes in the network.
    double getGeodesics​(U orig, U dest)
    Returns the number of geodesic paths between two nodes.
    double getInfiniteDistances()
    Obtains the number of infinite length pairs.
    java.util.Map<U,​java.lang.Double> getNodeBetweenness()
    Returns the node betweenness for each node in the network.
    double getNodeBetweenness​(U node)
    Gets the value of node betweenness for a single node.
    Communities<U> getSCC()
    Obtains the strongly connected components of the graph.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • graph

      private Graph<U> graph
      Graph the betweenness metrics are built for.

    • nodeBetweenness

      private java.util.Map<U,​java.lang.Double> nodeBetweenness
      Nodes betweenness map.

    • edgeBetweenness

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> edgeBetweenness
      Edge betweenness map.

    • distancesFrom

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesFrom
      Distances map from u to v.

    • distancesTo

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesTo
      Distances map towards the key user.

    • geodesics

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> geodesics
      Number of minimum distance paths between two nodes.

    • scc

      private Communities<U> scc
      Strongly connected components.

    • flag

      private boolean flag
      Flag for detecting whether the algorithm should or should not stop.

    • asl

      private double asl
      Average shortest path length.

    • infiniteDistances

      private double infiniteDistances
      Number of pairs at infinite distance to each other.

  • Constructor Details

  • Method Details

    • computeDistances

      public boolean computeDistances​(Graph<U> graph)
      Description copied from interface: DistanceCalculator
      Computes the distances between nodes in a network.
      Specified by:
      computeDistances in interface DistanceCalculator<U>
      Parameters:
      graph - the graph.
      Returns:
      true if everything went OK, false otherwise.

    • getNodeBetweenness

      public java.util.Map<U,​java.lang.Double> getNodeBetweenness()
      Description copied from interface: DistanceCalculator
      Returns the node betweenness for each node in the network.
      Specified by:
      getNodeBetweenness in interface DistanceCalculator<U>
      Returns:
      a map containing the node betweenness for each node.

    • getNodeBetweenness

      public double getNodeBetweenness​(U node)
      Description copied from interface: DistanceCalculator
      Gets the value of node betweenness for a single node.
      Specified by:
      getNodeBetweenness in interface DistanceCalculator<U>
      Parameters:
      node - the value for the node.
      Returns:
      the node betweenness for that node.

    • getEdgeBetweenness

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getEdgeBetweenness()
      Description copied from interface: DistanceCalculator
      Gets all the values of the edge betweenness.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Returns:
      the edge betweenness value for each edge.

    • getEdgeBetweenness

      public java.util.Map<U,​java.lang.Double> getEdgeBetweenness​(U node)
      Description copied from interface: DistanceCalculator
      Returns the edge betweenness of all the adjacent edges to a given node.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Parameters:
      node - The node.
      Returns:
      a map containing the values of edge betweenness for all the adjacent links to the given node.

    • getEdgeBetweenness

      public double getEdgeBetweenness​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the edge betweenness of a single edge.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Parameters:
      orig - origin node of the edge.
      dest - destination node of the edge.
      Returns:
      the betweenness if the edge exists, -1.0 if not.

    • getDistances

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getDistances()
      Description copied from interface: DistanceCalculator
      Returns all the distances between different pairs.
      Specified by:
      getDistances in interface DistanceCalculator<U>
      Returns:
      the distances between pairs.

    • getDistancesFrom

      public java.util.Map<U,​java.lang.Double> getDistancesFrom​(U node)
      Description copied from interface: DistanceCalculator
      Return the distances between a node and the rest of nodes in the network.
      Specified by:
      getDistancesFrom in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing all the distances from the node to the rest of the network.

    • getDistancesTo

      public java.util.Map<U,​java.lang.Double> getDistancesTo​(U node)
      Description copied from interface: DistanceCalculator
      Returns the distance between the network and an specific node.
      Specified by:
      getDistancesTo in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing all the distances from each vertex in the network to the node.

    • getDistances

      public double getDistances​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the distance between two nodes.
      Specified by:
      getDistances in interface DistanceCalculator<U>
      Parameters:
      orig - origin node.
      dest - destination node.
      Returns:
      the distance between both nodes. if there is a path between them, +Infinity if not.

    • getGeodesics

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getGeodesics()
      Description copied from interface: DistanceCalculator
      Returns the number of geodesic paths between different pairs.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Returns:
      the distances between pairs.

    • getGeodesics

      public java.util.Map<U,​java.lang.Double> getGeodesics​(U node)
      Description copied from interface: DistanceCalculator
      Return the number of geodesic paths between a node and the rest of nodes in the network.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing the number of geodesic paths from the node to the rest of the network.

    • getGeodesics

      public double getGeodesics​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the number of geodesic paths between two nodes.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Parameters:
      orig - origin node.
      dest - destination node.
      Returns:
      the number of geodesic paths between both nodes if there is a path between them, 0.0 if not.

    • getSCC

      public Communities<U> getSCC()
      Description copied from interface: DistanceCalculator
      Obtains the strongly connected components of the graph.
      Specified by:
      getSCC in interface DistanceCalculator<U>
      Returns:
      the strongly connected components of the graph.

    • getASL

      public double getASL()
      Description copied from interface: DistanceCalculator
      Obtains the average shortest path length, averaged over all the finite distance paths.
      Specified by:
      getASL in interface DistanceCalculator<U>
      Returns:
      the average shortest path length.

    • getInfiniteDistances

      public double getInfiniteDistances()
      Description copied from interface: DistanceCalculator
      Obtains the number of infinite length pairs.
      Specified by:
      getInfiniteDistances in interface DistanceCalculator<U>
      Returns:
      the number of infinite length pairs.