--- /dev/null
+/*
+ * 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