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

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. 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.