2 * Created on Sep 19, 2005
4 * Copyright (c) 2005, the JUNG Project and the Regents of the University
8 * This software is open-source under the BSD license; see either
10 * http://jung.sourceforge.net/license.txt for a description.
12 package edu.uci.ics.jung.algorithms.metrics;
14 import org.apache.commons.collections15.Transformer;
16 import edu.uci.ics.jung.graph.Graph;
19 * Calculates some of the measures from Burt's text "Structural Holes:
20 * The Social Structure of Competition".
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.
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>
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
40 public class StructuralHoles<V,E> {
42 protected Transformer<E, ? extends Number> edge_weight;
43 protected Graph<V,E> g;
46 * Creates a <code>StructuralHoles</code> instance based on the
47 * edge weights specified by <code>nev</code>.
49 public StructuralHoles(Graph<V,E> graph, Transformer<E, ? extends Number> nev)
52 this.edge_weight = nev;
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:
60 * effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w))
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
68 * @see #normalizedMutualEdgeWeight(Object, Object)
69 * @see #maxScaledMutualEdgeWeight(Object, Object)
71 public double effectiveSize(V v)
73 double result = g.degree(v);
74 for(V u : g.getNeighbors(v)) {
76 for(V w : g.getNeighbors(u)) {
79 result -= normalizedMutualEdgeWeight(v,w) *
80 maxScaledMutualEdgeWeight(u,w);
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.
92 public double efficiency(V v) {
93 double degree = g.degree(v);
98 return effectiveSize(v) / degree;
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:
107 * constraint(v) = sum_{w in MP(v), w != v} localConstraint(v,w)
109 * where MP(v) is the subset of v's neighbors that are both predecessors and successors of v.
110 * @see #localConstraint(Object, Object)
112 public double constraint(V v) {
114 for(V w : g.getSuccessors(v)) {
116 if (v != w && g.isPredecessor(v,w))
118 result += localConstraint(v, w);
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.
131 * hierarchy(v) = (sum_{v in N(v), w != v} s(v,w) * log(s(v,w))}) / (v.degree() * Math.log(v.degree())
135 * <li/><code>N(v) = v.getNeighbors()</code>
136 * <li/><code>s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())</code>
138 * @see #localConstraint(Object, Object)
139 * @see #aggregateConstraint(Object)
141 public double hierarchy(V v)
143 double v_degree = g.degree(v);
150 double v_constraint = aggregateConstraint(v);
152 double numerator = 0;
153 for (V w : g.getNeighbors(v)) {
157 double sl_constraint = localConstraint(v, w) / (v_constraint / v_degree);
158 numerator += sl_constraint * Math.log(sl_constraint);
162 return numerator / (v_degree * Math.log(v_degree));
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:
170 * localConstraint(v1, v2) = ( p(v1,v2) + ( sum_{w in N(v)} p(v1,w) * p(w, v2) ) )^2
174 * <li/><code>N(v) = v.getNeighbors()</code>
175 * <li/><code>p(v,w) =</code> normalized mutual edge weight of v and w
177 * @see #normalizedMutualEdgeWeight(Object, Object)
179 public double localConstraint(V v1, V v2)
181 double nmew_vw = normalizedMutualEdgeWeight(v1, v2);
182 double inner_result = 0;
183 for (V w : g.getNeighbors(v1)) {
185 inner_result += normalizedMutualEdgeWeight(v1,w) *
186 normalizedMutualEdgeWeight(w,v2);
188 return (nmew_vw + inner_result) * (nmew_vw + inner_result);
192 * The aggregate constraint on <code>v</code>. Based on Burt's equation 2.7.
195 * aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w)
199 * <li/><code>N(v) = v.getNeighbors()</code>
200 * <li/><code>O(w) = organizationalMeasure(w)</code>
203 public double aggregateConstraint(V v)
206 for (V w : g.getNeighbors(v)) {
208 result += localConstraint(v, w) * organizationalMeasure(g, w);
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].
220 * <p>This implementation returns 1. Users may wish to override this
221 * method in order to define their own behavior.</p>
223 protected double organizationalMeasure(Graph<V,E> g, V v) {
229 * Returns the proportion of <code>v1</code>'s network time and energy invested
230 * in the relationship with <code>v2</code>. Formally:
232 * normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c))
234 * Returns 0 if either numerator or denominator = 0, or if <code>v1 == v2</code>.
235 * @see #mutualWeight(Object, Object)
237 protected double normalizedMutualEdgeWeight(V v1, V v2)
242 double numerator = mutualWeight(v1, v2);
247 double denominator = 0;
248 for (V v : g.getNeighbors(v1)) {
249 denominator += mutualWeight(v1, v);
251 if (denominator == 0)
254 return numerator / denominator;
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>.
269 protected double mutualWeight(V v1, V v2)
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);
280 * The marginal strength of v1's relation with contact vertex2.
283 * normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c))
285 * Returns 0 if either numerator or denominator is 0, or if <code>v1 == v2</code>.
286 * @see #mutualWeight(Object, Object)
288 protected double maxScaledMutualEdgeWeight(V v1, V v2)
293 double numerator = mutualWeight(v1, v2);
298 double denominator = 0;
299 for (V w : g.getNeighbors(v1)) {
302 denominator = Math.max(numerator, mutualWeight(v1, w));
305 if (denominator == 0)
308 return numerator / denominator;