Class TriadicCensus


  • public class TriadicCensus
    extends java.lang.Object
    TriadicCensus is a standard social network tool that counts, for each of the different possible configurations of three vertices, the number of times that that configuration occurs in the given graph. This may then be compared to the set of expected counts for this particular graph or to an expected sample. This is often used in p* modeling.

    To use this class,

     long[] triad_counts = TriadicCensus(dg);
     
    where dg is a DirectedGraph. ith element of the array (for i in [1,16]) is the number of occurrences of the corresponding triad type. (The 0th element is not meaningful; this array is effectively 1-based.) To get the name of the ith triad (e.g. "003"), look at the global constant array c.TRIAD_NAMES[i]

    Triads are named as (number of pairs that are mutually tied) (number of pairs that are one-way tied) (number of non-tied pairs) in the triple. Since there are be only three pairs, there is a finite set of these possible triads.

    In fact, there are exactly 16, conventionally sorted by the number of realized edges in the triad:

    Number Configuration Notes
    1003The empty triad
    2012
    3102
    4021D"Down": the directed edges point away
    5021U"Up": the directed edges meet
    6021C"Circle": one in, one out
    7111D"Down": 021D but one edge is mutual
    8111U"Up": 021U but one edge is mutual
    9030T"Transitive": two point to the same vertex
    10030C"Circle": A->B->C->A
    11201
    12120D"Down": 021D but the third edge is mutual
    13120U"Up": 021U but the third edge is mutual
    14120C"Circle": 021C but the third edge is mutual
    15210
    16300The complete

    This implementation takes O( m ), m is the number of edges in the graph.
    It is based on A subquadratic triad census algorithm for large sparse networks with small maximum degree Vladimir Batagelj and Andrej Mrvar, University of Ljubljana Published in Social Networks.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected static int[] codeToType
      For debugging purposes, this is copied straight out of the paper which means that they refer to triad types 1-16.
      static int MAX_TRIADS  
      static java.lang.String[] TRIAD_NAMES  
    • Constructor Summary

      Constructors 
      Constructor Description
      TriadicCensus()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <V,​E>
      long[]
      getCounts​(edu.uci.ics.jung.graph.DirectedGraph<V,​E> g)
      Returns an array whose ith element (for i in [1,16]) is the number of occurrences of the corresponding triad type in g.
      protected static <V,​E>
      boolean
      link​(edu.uci.ics.jung.graph.Graph<V,​E> g, V a, V b)  
      protected static <V,​E>
      boolean
      shouldCount​(edu.uci.ics.jung.graph.Graph<V,​E> g, java.util.List<V> id, V u, V v, V w)
      Make sure we have a canonical ordering: Returns true if u < w, or v < w < u and v doesn't link to w
      static <V,​E>
      int
      triCode​(edu.uci.ics.jung.graph.Graph<V,​E> g, V u, V v, V w)
      This is the core of the technique in the paper.
      static int triType​(int triCode)
      Simply returns the triCode.
      • Methods inherited from class java.lang.Object

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

      • TRIAD_NAMES

        public static final java.lang.String[] TRIAD_NAMES
      • MAX_TRIADS

        public static final int MAX_TRIADS
      • codeToType

        protected static final int[] codeToType
        For debugging purposes, this is copied straight out of the paper which means that they refer to triad types 1-16.
    • Constructor Detail

      • TriadicCensus

        public TriadicCensus()
    • Method Detail

      • getCounts

        public static <V,​E> long[] getCounts​(edu.uci.ics.jung.graph.DirectedGraph<V,​E> g)
        Returns an array whose ith element (for i in [1,16]) is the number of occurrences of the corresponding triad type in g. (The 0th element is not meaningful; this array is effectively 1-based.)
        Parameters:
        g -
      • triCode

        public static <V,​E> int triCode​(edu.uci.ics.jung.graph.Graph<V,​E> g,
                                              V u,
                                              V v,
                                              V w)
        This is the core of the technique in the paper. Returns an int from 0 to 65 based on: WU -> 32 UW -> 16 WV -> 8 VW -> 4 UV -> 2 VU -> 1
      • link

        protected static <V,​E> boolean link​(edu.uci.ics.jung.graph.Graph<V,​E> g,
                                                  V a,
                                                  V b)
      • triType

        public static int triType​(int triCode)
        Simply returns the triCode.
        Parameters:
        triCode -
        Returns:
        the string code associated with the numeric type
      • shouldCount

        protected static <V,​E> boolean shouldCount​(edu.uci.ics.jung.graph.Graph<V,​E> g,
                                                         java.util.List<V> id,
                                                         V u,
                                                         V v,
                                                         V w)
        Make sure we have a canonical ordering: Returns true if u < w, or v < w < u and v doesn't link to w
        Parameters:
        id -
        u -
        v -
        w -
        Returns:
        true if u < w, or if v < w < u and v doesn't link to w; false otherwise