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

   1 /*
   2  * Created on Sep 19, 2005
   3  *
   4  * Copyright (c) 2005, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.metrics;
  13
  14 import org.apache.commons.collections15.Transformer;
  15
  16 import edu.uci.ics.jung.graph.Graph;
  17
  18 /**
  19  * Calculates some of the measures from Burt's text "Structural Holes:
  20  * The Social Structure of Competition".
  21  *
  22  * <p><b>Notes</b>:
  23  * <ul>
  24  * <li/>Each of these measures assumes that each edge has an associated
  25  * non-null weight whose value is accessed through the specified
  26  * <code>Transformer</code> instance.
  27  * <li/>Nonexistent edges are treated as edges with weight 0 for purposes
  28  * of edge weight calculations.
  29  * </ul>
  30  *
  31  * <p>Based on code donated by Jasper Voskuilen and
  32  * Diederik van Liere of the Department of Information and Decision Sciences
  33  * at Erasmus University.</p>
  34  *
  35  * @author Joshua O'Madadhain
  36  * @author Jasper Voskuilen
  37  * @see "Ronald Burt, Structural Holes: The Social Structure of Competition"
  38  * @author Tom Nelson - converted to jung2
  39  */
  40 public class StructuralHoles<V,E> {
  41
  42     protected Transformer<E, ? extends Number> edge_weight;
  43     protected Graph<V,E> g;
  44
  45     /**
  46      * Creates a <code>StructuralHoles</code> instance based on the
  47      * edge weights specified by <code>nev</code>.
  48      */
  49     public StructuralHoles(Graph<V,E> graph, Transformer<E, ? extends Number> nev)
  50     {
  51         this.g = graph;
  52         this.edge_weight = nev;
  53     }
  54
  55     /**
  56      * Burt's measure of the effective size of a vertex's network.  Essentially, the
  57      * number of neighbors minus the average degree of those in <code>v</code>'s neighbor set,
  58      * not counting ties to <code>v</code>.  Formally:
  59      * <pre>
  60      * effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w))
  61      * </pre>
  62      * where
  63      * <ul>
  64      * <li/><code>N(a) = a.getNeighbors()</code>
  65      * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
  66      * <li/><code>m(u,w)</code> = maximum-scaled mutual edge weight of u and w
  67      * </ul>
  68      * @see #normalizedMutualEdgeWeight(Object, Object)
  69      * @see #maxScaledMutualEdgeWeight(Object, Object)
  70      */
  71     public double effectiveSize(V v)
  72     {
  73         double result = g.degree(v);
  74         for(V u : g.getNeighbors(v)) {
  75
  76             for(V w : g.getNeighbors(u)) {
  77
  78                 if (w != v && w != u)
  79                     result -= normalizedMutualEdgeWeight(v,w) *
  80                               maxScaledMutualEdgeWeight(u,w);
  81             }
  82         }
  83         return result;
  84     }
  85
  86     /**
  87      * Returns the effective size of <code>v</code> divided by the number of
  88      * alters in <code>v</code>'s network.  (In other words,
  89      * <code>effectiveSize(v) / v.degree()</code>.)
  90      * If <code>v.degree() == 0</code>, returns 0.
  91      */
  92     public double efficiency(V v) {
  93         double degree = g.degree(v);
  94
  95         if (degree == 0)
  96             return 0;
  97         else
  98             return effectiveSize(v) / degree;
  99     }
 100
 101     /**
 102      * Burt's constraint measure (equation 2.4, page 55 of Burt, 1992). Essentially a
 103      * measure of the extent to which <code>v</code> is invested in people who are invested in
 104      * other of <code>v</code>'s alters (neighbors).  The "constraint" is characterized
 105      * by a lack of primary holes around each neighbor.  Formally:
 106      * <pre>
 107      * constraint(v) = sum_{w in MP(v), w != v} localConstraint(v,w)
 108      * </pre>
 109      * where MP(v) is the subset of v's neighbors that are both predecessors and successors of v.
 110      * @see #localConstraint(Object, Object)
 111      */
 112     public double constraint(V v) {
 113         double result = 0;
 114         for(V w : g.getSuccessors(v)) {
 115
 116             if (v != w && g.isPredecessor(v,w))
 117             {
 118                 result += localConstraint(v, w);
 119             }
 120         }
 121
 122         return result;
 123     }
 124
 125
 126     /**
 127      * Calculates the hierarchy value for a given vertex.  Returns <code>NaN</code> when
 128      * <code>v</code>'s degree is 0, and 1 when <code>v</code>'s degree is 1.
 129      * Formally:
 130      * <pre>
 131      * hierarchy(v) = (sum_{v in N(v), w != v} s(v,w) * log(s(v,w))}) / (v.degree() * Math.log(v.degree())
 132      * </pre>
 133      * where
 134      * <ul>
 135      * <li/><code>N(v) = v.getNeighbors()</code>
 136      * <li/><code>s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())</code>
 137      * </ul>
 138      * @see #localConstraint(Object, Object)
 139      * @see #aggregateConstraint(Object)
 140      */
 141     public double hierarchy(V v)
 142     {
 143         double v_degree = g.degree(v);
 144
 145         if (v_degree == 0)
 146             return Double.NaN;
 147         if (v_degree == 1)
 148             return 1;
 149
 150         double v_constraint = aggregateConstraint(v);
 151
 152         double numerator = 0;
 153         for (V w : g.getNeighbors(v)) {
 154
 155             if (v != w)
 156             {
 157                 double sl_constraint = localConstraint(v, w) / (v_constraint / v_degree);
 158                 numerator += sl_constraint * Math.log(sl_constraint);
 159             }
 160         }
 161
 162         return numerator / (v_degree * Math.log(v_degree));
 163     }
 164
 165     /**
 166      * Returns the local constraint on <code>v</code> from a lack of primary holes
 167      * around its neighbor <code>v2</code>.
 168      * Based on Burt's equation 2.4.  Formally:
 169      * <pre>
 170      * localConstraint(v1, v2) = ( p(v1,v2) + ( sum_{w in N(v)} p(v1,w) * p(w, v2) ) )^2
 171      * </pre>
 172      * where
 173      * <ul>
 174      * <li/><code>N(v) = v.getNeighbors()</code>
 175      * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
 176      * </ul>
 177      * @see #normalizedMutualEdgeWeight(Object, Object)
 178      */
 179     public double localConstraint(V v1, V v2)
 180     {
 181         double nmew_vw = normalizedMutualEdgeWeight(v1, v2);
 182         double inner_result = 0;
 183         for (V w : g.getNeighbors(v1)) {
 184
 185             inner_result += normalizedMutualEdgeWeight(v1,w) *
 186                 normalizedMutualEdgeWeight(w,v2);
 187         }
 188         return (nmew_vw + inner_result) * (nmew_vw + inner_result);
 189     }
 190
 191     /**
 192      * The aggregate constraint on <code>v</code>.  Based on Burt's equation 2.7.
 193      * Formally:
 194      * <pre>
 195      * aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w)
 196      * </pre>
 197      * where
 198      * <ul>
 199      * <li/><code>N(v) = v.getNeighbors()</code>
 200      * <li/><code>O(w) = organizationalMeasure(w)</code>
 201      * </ul>
 202      */
 203     public double aggregateConstraint(V v)
 204     {
 205         double result = 0;
 206         for (V w : g.getNeighbors(v)) {
 207
 208             result += localConstraint(v, w) * organizationalMeasure(g, w);
 209         }
 210         return result;
 211     }
 212
 213     /**
 214      * A measure of the organization of individuals within the subgraph
 215      * centered on <code>v</code>.  Burt's text suggests that this is
 216      * in some sense a measure of how "replaceable" <code>v</code> is by
 217      * some other element of this subgraph.  Should be a number in the
 218      * closed interval [0,1].
 219      *
 220      * <p>This implementation returns 1.  Users may wish to override this
 221      * method in order to define their own behavior.</p>
 222      */
 223     protected double organizationalMeasure(Graph<V,E> g, V v) {
 224         return 1.0;
 225     }
 226
 227
 228     /**
 229      * Returns the proportion of <code>v1</code>'s network time and energy invested
 230      * in the relationship with <code>v2</code>.  Formally:
 231      * <pre>
 232      * normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c))
 233      * </pre>
 234      * Returns 0 if either numerator or denominator = 0, or if <code>v1 == v2</code>.
 235      * @see #mutualWeight(Object, Object)
 236      */
 237     protected double normalizedMutualEdgeWeight(V v1, V v2)
 238     {
 239         if (v1 == v2)
 240             return 0;
 241
 242         double numerator = mutualWeight(v1, v2);
 243
 244         if (numerator == 0)
 245             return 0;
 246
 247         double denominator = 0;
 248         for (V v : g.getNeighbors(v1)) {
 249             denominator += mutualWeight(v1, v);
 250         }
 251         if (denominator == 0)
 252             return 0;
 253
 254         return numerator / denominator;
 255     }
 256
 257     /**
 258      * Returns the weight of the edge from <code>v1</code> to <code>v2</code>
 259      * plus the weight of the edge from <code>v2</code> to <code>v1</code>;
 260      * if either edge does not exist, it is treated as an edge with weight 0.
 261      * Undirected edges are treated as two antiparallel directed edges (that
 262      * is, if there is one undirected edge with weight <i>w</i> connecting
 263      * <code>v1</code> to <code>v2</code>, the value returned is 2<i>w</i>).
 264      * Ignores parallel edges; if there are any such, one is chosen at random.
 265      * Throws <code>NullPointerException</code> if either edge is
 266      * present but not assigned a weight by the constructor-specified
 267      * <code>NumberEdgeValue</code>.
 268      */
 269     protected double mutualWeight(V v1, V v2)
 270     {
 271         E e12 = g.findEdge(v1,v2);
 272         E e21 = g.findEdge(v2,v1);
 273         double w12 = (e12 != null ? edge_weight.transform(e12).doubleValue() : 0);
 274         double w21 = (e21 != null ? edge_weight.transform(e21).doubleValue() : 0);
 275
 276         return w12 + w21;
 277     }
 278
 279     /**
 280      * The marginal strength of v1's relation with contact vertex2.
 281      * Formally:
 282      * <pre>
 283      * normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c))
 284      * </pre>
 285      * Returns 0 if either numerator or denominator is 0, or if <code>v1 == v2</code>.
 286      * @see #mutualWeight(Object, Object)
 287      */
 288     protected double maxScaledMutualEdgeWeight(V v1, V v2)
 289     {
 290         if (v1 == v2)
 291             return 0;
 292
 293         double numerator = mutualWeight(v1, v2);
 294
 295         if (numerator == 0)
 296             return 0;
 297
 298         double denominator = 0;
 299         for (V w : g.getNeighbors(v1)) {
 300
 301             if (v2 != w)
 302                 denominator = Math.max(numerator, mutualWeight(v1, w));
 303         }
 304
 305         if (denominator == 0)
 306             return 0;
 307
 308         return numerator / denominator;
 309     }
 310 }