-/*
- * Created on Sep 19, 2005
- *
- * Copyright (c) 2005, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.metrics;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Calculates some of the measures from Burt's text "Structural Holes:
- * The Social Structure of Competition".
- *
- * <p><b>Notes</b>:
- * <ul>
- * <li/>Each of these measures assumes that each edge has an associated
- * non-null weight whose value is accessed through the specified
- * <code>Transformer</code> instance.
- * <li/>Nonexistent edges are treated as edges with weight 0 for purposes
- * of edge weight calculations.
- * </ul>
- *
- * <p>Based on code donated by Jasper Voskuilen and
- * Diederik van Liere of the Department of Information and Decision Sciences
- * at Erasmus University.</p>
- *
- * @author Joshua O'Madadhain
- * @author Jasper Voskuilen
- * @see "Ronald Burt, Structural Holes: The Social Structure of Competition"
- * @author Tom Nelson - converted to jung2
- */
-public class StructuralHoles<V,E> {
-
- protected Transformer<E, ? extends Number> edge_weight;
- protected Graph<V,E> g;
-
- /**
- * Creates a <code>StructuralHoles</code> instance based on the
- * edge weights specified by <code>nev</code>.
- */
- public StructuralHoles(Graph<V,E> graph, Transformer<E, ? extends Number> nev)
- {
- this.g = graph;
- this.edge_weight = nev;
- }
-
- /**
- * Burt's measure of the effective size of a vertex's network. Essentially, the
- * number of neighbors minus the average degree of those in <code>v</code>'s neighbor set,
- * not counting ties to <code>v</code>. Formally:
- * <pre>
- * effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w))
- * </pre>
- * where
- * <ul>
- * <li/><code>N(a) = a.getNeighbors()</code>
- * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
- * <li/><code>m(u,w)</code> = maximum-scaled mutual edge weight of u and w
- * </ul>
- * @see #normalizedMutualEdgeWeight(Object, Object)
- * @see #maxScaledMutualEdgeWeight(Object, Object)
- */
- public double effectiveSize(V v)
- {
- double result = g.degree(v);
- for(V u : g.getNeighbors(v)) {
-
- for(V w : g.getNeighbors(u)) {
-
- if (w != v && w != u)
- result -= normalizedMutualEdgeWeight(v,w) *
- maxScaledMutualEdgeWeight(u,w);
- }
- }
- return result;
- }
-
- /**
- * Returns the effective size of <code>v</code> divided by the number of
- * alters in <code>v</code>'s network. (In other words,
- * <code>effectiveSize(v) / v.degree()</code>.)
- * If <code>v.degree() == 0</code>, returns 0.
- */
- public double efficiency(V v) {
- double degree = g.degree(v);
-
- if (degree == 0)
- return 0;
- else
- return effectiveSize(v) / degree;
- }
-
- /**
- * Burt's constraint measure (equation 2.4, page 55 of Burt, 1992). Essentially a
- * measure of the extent to which <code>v</code> is invested in people who are invested in
- * other of <code>v</code>'s alters (neighbors). The "constraint" is characterized
- * by a lack of primary holes around each neighbor. Formally:
- * <pre>
- * constraint(v) = sum_{w in MP(v), w != v} localConstraint(v,w)
- * </pre>
- * where MP(v) is the subset of v's neighbors that are both predecessors and successors of v.
- * @see #localConstraint(Object, Object)
- */
- public double constraint(V v) {
- double result = 0;
- for(V w : g.getSuccessors(v)) {
-
- if (v != w && g.isPredecessor(v,w))
- {
- result += localConstraint(v, w);
- }
- }
-
- return result;
- }
-
-
- /**
- * Calculates the hierarchy value for a given vertex. Returns <code>NaN</code> when
- * <code>v</code>'s degree is 0, and 1 when <code>v</code>'s degree is 1.
- * Formally:
- * <pre>
- * hierarchy(v) = (sum_{v in N(v), w != v} s(v,w) * log(s(v,w))}) / (v.degree() * Math.log(v.degree())
- * </pre>
- * where
- * <ul>
- * <li/><code>N(v) = v.getNeighbors()</code>
- * <li/><code>s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())</code>
- * </ul>
- * @see #localConstraint(Object, Object)
- * @see #aggregateConstraint(Object)
- */
- public double hierarchy(V v)
- {
- double v_degree = g.degree(v);
-
- if (v_degree == 0)
- return Double.NaN;
- if (v_degree == 1)
- return 1;
-
- double v_constraint = aggregateConstraint(v);
-
- double numerator = 0;
- for (V w : g.getNeighbors(v)) {
-
- if (v != w)
- {
- double sl_constraint = localConstraint(v, w) / (v_constraint / v_degree);
- numerator += sl_constraint * Math.log(sl_constraint);
- }
- }
-
- return numerator / (v_degree * Math.log(v_degree));
- }
-
- /**
- * Returns the local constraint on <code>v</code> from a lack of primary holes
- * around its neighbor <code>v2</code>.
- * Based on Burt's equation 2.4. Formally:
- * <pre>
- * localConstraint(v1, v2) = ( p(v1,v2) + ( sum_{w in N(v)} p(v1,w) * p(w, v2) ) )^2
- * </pre>
- * where
- * <ul>
- * <li/><code>N(v) = v.getNeighbors()</code>
- * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
- * </ul>
- * @see #normalizedMutualEdgeWeight(Object, Object)
- */
- public double localConstraint(V v1, V v2)
- {
- double nmew_vw = normalizedMutualEdgeWeight(v1, v2);
- double inner_result = 0;
- for (V w : g.getNeighbors(v1)) {
-
- inner_result += normalizedMutualEdgeWeight(v1,w) *
- normalizedMutualEdgeWeight(w,v2);
- }
- return (nmew_vw + inner_result) * (nmew_vw + inner_result);
- }
-
- /**
- * The aggregate constraint on <code>v</code>. Based on Burt's equation 2.7.
- * Formally:
- * <pre>
- * aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w)
- * </pre>
- * where
- * <ul>
- * <li/><code>N(v) = v.getNeighbors()</code>
- * <li/><code>O(w) = organizationalMeasure(w)</code>
- * </ul>
- */
- public double aggregateConstraint(V v)
- {
- double result = 0;
- for (V w : g.getNeighbors(v)) {
-
- result += localConstraint(v, w) * organizationalMeasure(g, w);
- }
- return result;
- }
-
- /**
- * A measure of the organization of individuals within the subgraph
- * centered on <code>v</code>. Burt's text suggests that this is
- * in some sense a measure of how "replaceable" <code>v</code> is by
- * some other element of this subgraph. Should be a number in the
- * closed interval [0,1].
- *
- * <p>This implementation returns 1. Users may wish to override this
- * method in order to define their own behavior.</p>
- */
- protected double organizationalMeasure(Graph<V,E> g, V v) {
- return 1.0;
- }
-
-
- /**
- * Returns the proportion of <code>v1</code>'s network time and energy invested
- * in the relationship with <code>v2</code>. Formally:
- * <pre>
- * normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c))
- * </pre>
- * Returns 0 if either numerator or denominator = 0, or if <code>v1 == v2</code>.
- * @see #mutualWeight(Object, Object)
- */
- protected double normalizedMutualEdgeWeight(V v1, V v2)
- {
- if (v1 == v2)
- return 0;
-
- double numerator = mutualWeight(v1, v2);
-
- if (numerator == 0)
- return 0;
-
- double denominator = 0;
- for (V v : g.getNeighbors(v1)) {
- denominator += mutualWeight(v1, v);
- }
- if (denominator == 0)
- return 0;
-
- return numerator / denominator;
- }
-
- /**
- * Returns the weight of the edge from <code>v1</code> to <code>v2</code>
- * plus the weight of the edge from <code>v2</code> to <code>v1</code>;
- * if either edge does not exist, it is treated as an edge with weight 0.
- * Undirected edges are treated as two antiparallel directed edges (that
- * is, if there is one undirected edge with weight <i>w</i> connecting
- * <code>v1</code> to <code>v2</code>, the value returned is 2<i>w</i>).
- * Ignores parallel edges; if there are any such, one is chosen at random.
- * Throws <code>NullPointerException</code> if either edge is
- * present but not assigned a weight by the constructor-specified
- * <code>NumberEdgeValue</code>.
- */
- protected double mutualWeight(V v1, V v2)
- {
- E e12 = g.findEdge(v1,v2);
- E e21 = g.findEdge(v2,v1);
- double w12 = (e12 != null ? edge_weight.transform(e12).doubleValue() : 0);
- double w21 = (e21 != null ? edge_weight.transform(e21).doubleValue() : 0);
-
- return w12 + w21;
- }
-
- /**
- * The marginal strength of v1's relation with contact vertex2.
- * Formally:
- * <pre>
- * normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c))
- * </pre>
- * Returns 0 if either numerator or denominator is 0, or if <code>v1 == v2</code>.
- * @see #mutualWeight(Object, Object)
- */
- protected double maxScaledMutualEdgeWeight(V v1, V v2)
- {
- if (v1 == v2)
- return 0;
-
- double numerator = mutualWeight(v1, v2);
-
- if (numerator == 0)
- return 0;
-
- double denominator = 0;
- for (V w : g.getNeighbors(v1)) {
-
- if (v2 != w)
- denominator = Math.max(numerator, mutualWeight(v1, w));
- }
-
- if (denominator == 0)
- return 0;
-
- return numerator / denominator;
- }
-}
Code Review / controller.git / blobdiff