/* * Created on Sep 19, 2005 * * Copyright (c) 2005, the JUNG Project and the Regents of the University * of California * All rights reserved. * * This software is open-source under the BSD license; see either * "license.txt" or * http://jung.sourceforge.net/license.txt for a description. */ package edu.uci.ics.jung.algorithms.metrics; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.graph.Graph; /** * Calculates some of the measures from Burt's text "Structural Holes: * The Social Structure of Competition". * *
Notes: *
Transformer
instance.
* Nonexistent edges are treated as edges with weight 0 for purposes
* of edge weight calculations.
* Based on code donated by Jasper Voskuilen and * Diederik van Liere of the Department of Information and Decision Sciences * at Erasmus University.
* * @author Joshua O'Madadhain * @author Jasper Voskuilen * @see "Ronald Burt, Structural Holes: The Social Structure of Competition" * @author Tom Nelson - converted to jung2 */ public class StructuralHolesStructuralHoles
instance based on the
* edge weights specified by nev
.
*/
public StructuralHoles(Graphv
's neighbor set,
* not counting ties to v
. Formally:
* * effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w)) ** where *
N(a) = a.getNeighbors()
* p(v,w) =
normalized mutual edge weight of v and w
* m(u,w)
= maximum-scaled mutual edge weight of u and w
* v
divided by the number of
* alters in v
's network. (In other words,
* effectiveSize(v) / v.degree()
.)
* If v.degree() == 0
, returns 0.
*/
public double efficiency(V v) {
double degree = g.degree(v);
if (degree == 0)
return 0;
else
return effectiveSize(v) / degree;
}
/**
* Burt's constraint measure (equation 2.4, page 55 of Burt, 1992). Essentially a
* measure of the extent to which v
is invested in people who are invested in
* other of v
's alters (neighbors). The "constraint" is characterized
* by a lack of primary holes around each neighbor. Formally:
* * constraint(v) = sum_{w in MP(v), w != v} localConstraint(v,w) ** where MP(v) is the subset of v's neighbors that are both predecessors and successors of v. * @see #localConstraint(Object, Object) */ public double constraint(V v) { double result = 0; for(V w : g.getSuccessors(v)) { if (v != w && g.isPredecessor(v,w)) { result += localConstraint(v, w); } } return result; } /** * Calculates the hierarchy value for a given vertex. Returns
NaN
when
* v
's degree is 0, and 1 when v
's degree is 1.
* Formally:
* * hierarchy(v) = (sum_{v in N(v), w != v} s(v,w) * log(s(v,w))}) / (v.degree() * Math.log(v.degree()) ** where *
N(v) = v.getNeighbors()
* s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())
* v
from a lack of primary holes
* around its neighbor v2
.
* Based on Burt's equation 2.4. Formally:
* * localConstraint(v1, v2) = ( p(v1,v2) + ( sum_{w in N(v)} p(v1,w) * p(w, v2) ) )^2 ** where *
N(v) = v.getNeighbors()
* p(v,w) =
normalized mutual edge weight of v and w
* v
. Based on Burt's equation 2.7.
* Formally:
* * aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w) ** where *
N(v) = v.getNeighbors()
* O(w) = organizationalMeasure(w)
* v
. Burt's text suggests that this is
* in some sense a measure of how "replaceable" v
is by
* some other element of this subgraph. Should be a number in the
* closed interval [0,1].
*
* This implementation returns 1. Users may wish to override this * method in order to define their own behavior.
*/ protected double organizationalMeasure(Graphv1
's network time and energy invested
* in the relationship with v2
. Formally:
* * normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c)) ** Returns 0 if either numerator or denominator = 0, or if
v1 == v2
.
* @see #mutualWeight(Object, Object)
*/
protected double normalizedMutualEdgeWeight(V v1, V v2)
{
if (v1 == v2)
return 0;
double numerator = mutualWeight(v1, v2);
if (numerator == 0)
return 0;
double denominator = 0;
for (V v : g.getNeighbors(v1)) {
denominator += mutualWeight(v1, v);
}
if (denominator == 0)
return 0;
return numerator / denominator;
}
/**
* Returns the weight of the edge from v1
to v2
* plus the weight of the edge from v2
to v1
;
* if either edge does not exist, it is treated as an edge with weight 0.
* Undirected edges are treated as two antiparallel directed edges (that
* is, if there is one undirected edge with weight w connecting
* v1
to v2
, the value returned is 2w).
* Ignores parallel edges; if there are any such, one is chosen at random.
* Throws NullPointerException
if either edge is
* present but not assigned a weight by the constructor-specified
* NumberEdgeValue
.
*/
protected double mutualWeight(V v1, V v2)
{
E e12 = g.findEdge(v1,v2);
E e21 = g.findEdge(v2,v1);
double w12 = (e12 != null ? edge_weight.transform(e12).doubleValue() : 0);
double w21 = (e21 != null ? edge_weight.transform(e21).doubleValue() : 0);
return w12 + w21;
}
/**
* The marginal strength of v1's relation with contact vertex2.
* Formally:
* * normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c)) ** Returns 0 if either numerator or denominator is 0, or if
v1 == v2
.
* @see #mutualWeight(Object, Object)
*/
protected double maxScaledMutualEdgeWeight(V v1, V v2)
{
if (v1 == v2)
return 0;
double numerator = mutualWeight(v1, v2);
if (numerator == 0)
return 0;
double denominator = 0;
for (V w : g.getNeighbors(v1)) {
if (v2 != w)
denominator = Math.max(numerator, mutualWeight(v1, w));
}
if (denominator == 0)
return 0;
return numerator / denominator;
}
}