Class 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"
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected com.google.common.base.Function<E,​? extends java.lang.Number> edge_weight  
      protected Graph<V,​E> g  
    • 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 on v.
      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 of v divided by the number of alters in v's network.
      double hierarchy​(V v)
      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 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 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 normalizedMutualEdgeWeight​(V v1, V v2)
      Returns the proportion of v1's network time and energy invested in the relationship with v2.
      protected double organizationalMeasure​(Graph<V,​E> g, V v)
      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 Detail

      • edge_weight

        protected com.google.common.base.Function<E,​? extends java.lang.Number> edge_weight
    • Constructor Detail

      • StructuralHoles

        public StructuralHoles​(Graph<V,​E> graph,
                               com.google.common.base.Function<E,​? extends java.lang.Number> nev)
        Parameters:
        graph - the graph for which the metrics are to be calculated
        nev - the edge weights
    • 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 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:
        normalizedMutualEdgeWeight(Object, Object), maxScaledMutualEdgeWeight(Object, Object)
      • 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:
        localConstraint(Object, Object)
      • 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(Object, Object), aggregateConstraint(Object)
      • 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:
        normalizedMutualEdgeWeight(Object, Object)
      • 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(Object, Object)
      • 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:
        mutualWeight(Object, Object)