Class StructuralHoles<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.metrics.StructuralHoles<V,E>
-
public class StructuralHoles<V,E> extends java.lang.Object
Calculates some of the measures from Burt's text "Structural Holes: The Social Structure of Competition".Notes:
- Each of these measures assumes that each edge has an associated
non-null weight whose value is accessed through the specified
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, Jasper Voskuilen, Tom Nelson - converted to jung2
- See Also:
- "Ronald Burt, Structural Holes: The Social Structure of Competition"
- Each of these measures assumes that each edge has an associated
non-null weight whose value is accessed through the specified
-
-
Constructor Summary
Constructors Constructor Description StructuralHoles(Graph<V,E> graph, com.google.common.base.Function<E,? extends java.lang.Number> nev)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
aggregateConstraint(V v)
The aggregate constraint onv
.double
constraint(V v)
Burt's constraint measure (equation 2.4, page 55 of Burt, 1992).double
effectiveSize(V v)
Burt's measure of the effective size of a vertex's network.double
efficiency(V v)
Returns the effective size ofv
divided by the number of alters inv
's network.double
hierarchy(V v)
Calculates the hierarchy value for a given vertex.double
localConstraint(V v1, V v2)
Returns the local constraint onv1
from a lack of primary holes around its neighborv2
.protected double
maxScaledMutualEdgeWeight(V v1, V v2)
The marginal strength of v1's relation with contact v2.protected double
mutualWeight(V v1, V v2)
Returns the weight of the edge fromv1
tov2
plus the weight of the edge fromv2
tov1
; if either edge does not exist, it is treated as an edge with weight 0.protected double
normalizedMutualEdgeWeight(V v1, V v2)
Returns the proportion ofv1
's network time and energy invested in the relationship withv2
.protected double
organizationalMeasure(Graph<V,E> g, V v)
A measure of the organization of individuals within the subgraph centered onv
.
-
-
-
Method Detail
-
effectiveSize
public double effectiveSize(V v)
Burt's measure of the effective size of a vertex's network. Essentially, the number of neighbors minus the average degree of those inv
's neighbor set, not counting ties tov
. Formally:effectiveSize(v) = v.degree() - (sum_{u in N(v)} sum_{w in N(u), w !=u,v} p(v,w)*m(u,w))
whereN(a) = a.getNeighbors()
p(v,w) =
normalized mutual edge weight of v and wm(u,w)
= maximum-scaled mutual edge weight of u and w
- Parameters:
v
- the vertex whose properties are being measured- Returns:
- the effective size of the vertex's network
- See Also:
normalizedMutualEdgeWeight(Object, Object)
,maxScaledMutualEdgeWeight(Object, Object)
-
efficiency
public double efficiency(V v)
Returns the effective size ofv
divided by the number of alters inv
's network. (In other words,effectiveSize(v) / v.degree()
.) Ifv.degree() == 0
, returns 0.- Parameters:
v
- the vertex whose properties are being measured- Returns:
- the effective size of the vertex divided by its degree
-
constraint
public double constraint(V v)
Burt's constraint measure (equation 2.4, page 55 of Burt, 1992). Essentially a measure of the extent to whichv
is invested in people who are invested in other ofv
'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.- Parameters:
v
- the vertex whose properties are being measured- Returns:
- the constraint of the vertex
- See Also:
localConstraint(Object, Object)
-
hierarchy
public double hierarchy(V v)
Calculates the hierarchy value for a given vertex. ReturnsNaN
whenv
's degree is 0, and 1 whenv
'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())
whereN(v) = v.getNeighbors()
s(v,w) = localConstraint(v,w) / (aggregateConstraint(v) / v.degree())
- Parameters:
v
- the vertex whose properties are being measured- Returns:
- the hierarchy value for a given vertex
- See Also:
localConstraint(Object, Object)
,aggregateConstraint(Object)
-
localConstraint
public double localConstraint(V v1, V v2)
Returns the local constraint onv1
from a lack of primary holes around its neighborv2
. 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
whereN(v) = v.getNeighbors()
p(v,w) =
normalized mutual edge weight of v and w
- Parameters:
v1
- the first vertex whose local constraint is desiredv2
- the second vertex whose local constraint is desired- Returns:
- the local constraint on (v1, v2)
- See Also:
normalizedMutualEdgeWeight(Object, Object)
-
aggregateConstraint
public double aggregateConstraint(V v)
The aggregate constraint onv
. Based on Burt's equation 2.7. Formally:aggregateConstraint(v) = sum_{w in N(v)} localConstraint(v,w) * O(w)
whereN(v) = v.getNeighbors()
O(w) = organizationalMeasure(w)
- Parameters:
v
- the vertex whose properties are being measured- Returns:
- the aggregate constraint on v
-
organizationalMeasure
protected double organizationalMeasure(Graph<V,E> g, V v)
A measure of the organization of individuals within the subgraph centered onv
. 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.
- Parameters:
g
- the subgraph centered on vv
- the vertex whose properties are being measured- Returns:
- 1.0 (in this implementation)
-
normalizedMutualEdgeWeight
protected double normalizedMutualEdgeWeight(V v1, V v2)
Returns the proportion ofv1
's network time and energy invested in the relationship withv2
. Formally:normalizedMutualEdgeWeight(a,b) = mutual_weight(a,b) / (sum_c mutual_weight(a,c))
Returns 0 if either numerator or denominator = 0, or ifv1 == v2
.- Parameters:
v1
- the first vertex of the pair whose property is being measuredv2
- the second vertex of the pair whose property is being measured- Returns:
- the normalized mutual edge weight between v1 and v2
- See Also:
mutualWeight(Object, Object)
-
mutualWeight
protected double mutualWeight(V v1, V v2)
Returns the weight of the edge fromv1
tov2
plus the weight of the edge fromv2
tov1
; 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 connectingv1
tov2
, the value returned is 2w). Ignores parallel edges; if there are any such, one is chosen at random. ThrowsNullPointerException
if either edge is present but not assigned a weight by the constructor-specifiedNumberEdgeValue
.- Parameters:
v1
- the first vertex of the pair whose property is being measuredv2
- the second vertex of the pair whose property is being measured- Returns:
- the weights of the edges
<v1, v2>
and<v2, v1>
-
maxScaledMutualEdgeWeight
protected double maxScaledMutualEdgeWeight(V v1, V v2)
The marginal strength of v1's relation with contact v2. Formally:normalized_mutual_weight = mutual_weight(a,b) / (max_c mutual_weight(a,c))
Returns 0 if either numerator or denominator is 0, or ifv1 == v2
.- Parameters:
v1
- the first vertex of the pair whose property is being measuredv2
- the second vertex of the pair whose property is being measured- Returns:
- the marginal strength of v1's relation with v2
- See Also:
mutualWeight(Object, Object)
-
-