third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/Metrics.java

   1 /**
   2  * Copyright (c) 2008, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  * Created on Jun 7, 2008
  10  *
  11  */
  12 package edu.uci.ics.jung.algorithms.metrics;
  13
  14 import java.util.ArrayList;
  15 import java.util.HashMap;
  16 import java.util.Map;
  17
  18 import edu.uci.ics.jung.graph.Graph;
  19
  20 /**
  21  * A class consisting of static methods for calculating graph metrics.
  22  */
  23 public class Metrics
  24 {
  25     /**
  26      * Returns a <code>Map</code> of vertices to their clustering coefficients.
  27      * The clustering coefficient cc(v) of a vertex v is defined as follows:
  28      * <ul>
  29      * <li/><code>degree(v) == {0,1}</code>: 0
  30      * <li/><code>degree(v) == n, n &gt;= 2</code>: given S, the set of neighbors
  31      * of <code>v</code>: cc(v) = (the sum over all w in S of the number of
  32      * other elements of w that are neighbors of w) / ((|S| * (|S| - 1) / 2).
  33      * Less formally, the fraction of <code>v</code>'s neighbors that are also
  34      * neighbors of each other.
  35      * <p><b>Note</b>: This algorithm treats its argument as an undirected graph;
  36      * edge direction is ignored.
  37      * @param graph the graph whose clustering coefficients are to be calculated
  38      * @see "The structure and function of complex networks, M.E.J. Newman, aps.arxiv.org/abs/cond-mat/0303516"
  39      */
  40     public static <V,E> Map<V, Double> clusteringCoefficients(Graph<V,E> graph)
  41     {
  42         Map<V,Double> coefficients = new HashMap<V,Double>();
  43
  44         for (V v : graph.getVertices())
  45         {
  46             int n = graph.getNeighborCount(v);
  47             if (n < 2)
  48                 coefficients.put(v, new Double(0));
  49             else
  50             {
  51                 // how many of v's neighbors are connected to each other?
  52                 ArrayList<V> neighbors = new ArrayList<V>(graph.getNeighbors(v));
  53                 double edge_count = 0;
  54                 for (int i = 0; i < n; i++)
  55                 {
  56                     V w = neighbors.get(i);
  57                     for (int j = i+1; j < n; j++ )
  58                     {
  59                         V x = neighbors.get(j);
  60                         edge_count += graph.isNeighbor(w, x) ? 1 : 0;
  61                     }
  62                 }
  63                 double possible_edges = (n * (n - 1))/2.0;
  64                 coefficients.put(v, new Double(edge_count / possible_edges));
  65             }
  66         }
  67
  68         return coefficients;
  69     }
  70 }