Class StructuralHoles<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.metrics.StructuralHoles<V,E>

public class StructuralHoles<V,E> extends 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.

See Also:
  • "Ronald Burt, Structural Holes: The Social Structure of Competition"
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected com.google.common.base.Function<E,? extends Number>
     
    protected Graph<V,E>
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    StructuralHoles(Graph<V,E> graph, com.google.common.base.Function<E,? extends Number> nev)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    double
    The aggregate constraint on v.
    double
    Burt's constraint measure (equation 2.4, page 55 of Burt, 1992).
    double
    Burt's measure of the effective size of a vertex's network.
    double
    Returns the effective size of v divided by the number of alters in v's network.
    double
    Calculates the hierarchy value for a given vertex.
    double
    localConstraint(V v1, V v2)
    Returns the local constraint on v1 from a lack of primary holes around its neighbor v2.
    protected double
    The marginal strength of v1's relation with contact v2.
    protected double
    mutualWeight(V v1, V v2)
    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.
    protected double
    Returns the proportion of v1's network time and energy invested in the relationship with v2.
    protected double
    A measure of the organization of individuals within the subgraph centered on v.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • edge_weight

      protected com.google.common.base.Function<E,? extends Number> edge_weight
    • g

      protected Graph<V,E> g
  • Constructor Details

    • StructuralHoles

      public StructuralHoles(Graph<V,E> graph, com.google.common.base.Function<E,? extends Number> nev)
      Parameters:
      graph - the graph for which the metrics are to be calculated
      nev - the edge weights
  • Method Details

    • 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 in v'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
      Parameters:
      v - the vertex whose properties are being measured
      Returns:
      the effective size of the vertex's network
      See Also:
    • efficiency

      public double efficiency(V v)
      Returns the effective size of v divided by the number of alters in v's network. (In other words, effectiveSize(v) / v.degree().) If v.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 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.
      Parameters:
      v - the vertex whose properties are being measured
      Returns:
      the constraint of the vertex
      See Also:
    • hierarchy

      public double hierarchy(V v)
      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())
      Parameters:
      v - the vertex whose properties are being measured
      Returns:
      the hierarchy value for a given vertex
      See Also:
    • localConstraint

      public double localConstraint(V v1, V v2)
      Returns the local constraint on v1 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
      Parameters:
      v1 - the first vertex whose local constraint is desired
      v2 - the second vertex whose local constraint is desired
      Returns:
      the local constraint on (v1, v2)
      See Also:
    • aggregateConstraint

      public double aggregateConstraint(V v)
      The aggregate constraint on 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)
      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 on 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.

      Parameters:
      g - the subgraph centered on v
      v - the vertex whose properties are being measured
      Returns:
      1.0 (in this implementation)
    • normalizedMutualEdgeWeight

      protected double normalizedMutualEdgeWeight(V v1, V v2)
      Returns the proportion of v1'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.
      Parameters:
      v1 - the first vertex of the pair whose property is being measured
      v2 - the second vertex of the pair whose property is being measured
      Returns:
      the normalized mutual edge weight between v1 and v2
      See Also:
    • mutualWeight

      protected double mutualWeight(V v1, V v2)
      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.
      Parameters:
      v1 - the first vertex of the pair whose property is being measured
      v2 - 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 if v1 == v2.
      Parameters:
      v1 - the first vertex of the pair whose property is being measured
      v2 - the second vertex of the pair whose property is being measured
      Returns:
      the marginal strength of v1's relation with v2
      See Also: