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