Coverage details for edu.uci.ics.jung.algorithms.metrics.StructuralHoles

LineHitsSource
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)
480    {
490        this.nev = nev;
500    }
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     {
700        double result = v.degree();
710        for (Iterator v_iter = v.getNeighbors().iterator(); v_iter.hasNext(); )
72         {
730            Vertex u = (Vertex)v_iter.next();
740            for (Iterator u_iter = u.getNeighbors().iterator(); u_iter.hasNext(); )
75             {
760                Vertex w = (Vertex)u_iter.next();
770                if (w != v && w != u)
780                    result -= normalizedMutualEdgeWeight(v,w)*maxScaledMutualEdgeWeight(u,w);
79             }
80         }
810        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     {
920        double degree = v.degree();
93         
940        if (degree == 0)
950            return 0;
96         else
970            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     {
1130        double result = 0;
1140        for (Iterator v_iter = v.getSuccessors().iterator(); v_iter.hasNext(); )
115         {
1160            Vertex w = (Vertex)v_iter.next();
1170            if (v != w && w.isPredecessorOf(v))
118             {
1190                result += localConstraint(v, w);
120             }
121         }
122  
1230        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     {
1440        double v_degree = v.degree();
145         
1460        if (v_degree == 0)
1470            return Double.NaN;
1480        if (v_degree == 1)
1490            return 1;
150         
1510        double v_constraint = aggregateConstraint(v);
152  
1530        double numerator = 0;
1540        for (Iterator iter = v.getNeighbors().iterator(); iter.hasNext(); )
155         {
1560            Vertex w = (Vertex)iter.next();
1570            if (v != w)
158             {
1590                double sl_constraint = localConstraint(v, w) / (v_constraint / v_degree);
1600                numerator += sl_constraint * Math.log(sl_constraint);
161             }
162         }
163  
1640        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     {
1830        double nmew_vw = normalizedMutualEdgeWeight(v1, v2);
1840        double inner_result = 0;
1850        for (Iterator v_iter = v1.getNeighbors().iterator(); v_iter.hasNext(); )
186         {
1870            Vertex w = (Vertex)v_iter.next();
1880            inner_result += normalizedMutualEdgeWeight(v1,w) *
189                 normalizedMutualEdgeWeight(w,v2);
190         }
1910        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     {
2080        double result = 0;
2090        for (Iterator v_iter = v.getNeighbors().iterator(); v_iter.hasNext(); )
210         {
2110            Vertex w = (Vertex)v_iter.next();
2120            result += localConstraint(v, w) * organizationalMeasure(w);
213         }
2140        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     {
2290        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     {
2440        if (v1 == v2)
2450            return 0;
246         
2470        double numerator = mutualWeight(v1, v2);
248         
2490        if (numerator == 0)
2500            return 0;
251         
2520        double denominator = 0;
2530        for (Iterator iter = v1.getNeighbors().iterator(); iter.hasNext(); )
2540            denominator += mutualWeight(v1, (Vertex)iter.next());
255  
2560        if (denominator == 0)
2570            return 0;
258         
2590        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     {
2760        ArchetypeEdge e12 = v1.findEdge(v2);
2770        ArchetypeEdge e21 = v2.findEdge(v1);
2780        double w12 = (e12 != null ? nev.getNumber(e12).doubleValue() : 0);
2790        double w21 = (e21 != null ? nev.getNumber(e21).doubleValue() : 0);
280         
2810        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     {
2950        if (v1 == v2)
2960            return 0;
297  
2980        double numerator = mutualWeight(v1, v2);
299  
3000        if (numerator == 0)
3010            return 0;
302         
3030        double denominator = 0;
3040        for (Iterator iter = v1.getNeighbors().iterator(); iter.hasNext(); )
305         {
3060            Vertex w = (Vertex)iter.next();
3070            if (v2 != w)
3080                denominator = Math.max(numerator, mutualWeight(v1, w));
309         }
310         
3110        if (denominator == 0)
3120            return 0;
313         
3140        return numerator / denominator;
315     }
316 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.