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