/**
 * Copyright (c) 2008, The JUNG Authors 
 *
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * https://github.com/jrtom/jung/blob/master/LICENSE for a description.
 * Created on Jun 7, 2008
 * 
 */
package edu.uci.ics.jung.algorithms.metrics;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

import edu.uci.ics.jung.graph.Graph;

/**
 * A class consisting of static methods for calculating graph metrics.
 */
public class Metrics 
{
    /**
     * Returns a Map of vertices to their clustering coefficients.
     * The clustering coefficient cc(v) of a vertex v is defined as follows:
     * 
     * 

Note: This algorithm treats its argument as an undirected graph; * edge direction is ignored. * @param graph the graph whose clustering coefficients are to be calculated * @param the vertex type * @param the edge type * @return the clustering coefficient for each vertex * @see "The structure and function of complex networks, M.E.J. Newman, aps.arxiv.org/abs/cond-mat/0303516" */ public static Map clusteringCoefficients(Graph graph) { Map coefficients = new HashMap(); for (V v : graph.getVertices()) { int n = graph.getNeighborCount(v); if (n < 2) coefficients.put(v, new Double(0)); else { // how many of v's neighbors are connected to each other? ArrayList neighbors = new ArrayList(graph.getNeighbors(v)); double edge_count = 0; for (int i = 0; i < n; i++) { V w = neighbors.get(i); for (int j = i+1; j < n; j++ ) { V x = neighbors.get(j); edge_count += graph.isNeighbor(w, x) ? 1 : 0; } } double possible_edges = (n * (n - 1))/2.0; coefficients.put(v, new Double(edge_count / possible_edges)); } } return coefficients; } }

Ads help maintain this website.