Class TriadicCensus

java.lang.Object
edu.uci.ics.jung.algorithms.metrics.TriadicCensus

public class TriadicCensus extends 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:

Descriptions of the different types of triads
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 final int[]
    For debugging purposes, this is copied straight out of the paper which means that they refer to triad types 1-16.
    static final int
     
    static final String[]
     
  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> long[]
    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(Graph<V,E> g, V a, V b)
     
    protected static <V, E> boolean
    shouldCount(Graph<V,E> g, List<V> id, V u, V v, V w)
    Return true iff this ordering is canonical and therefore we should build statistics for it.
    static <V, E> int
    triCode(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)
     

    Methods inherited from class java.lang.Object

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

    • TRIAD_NAMES

      public static final 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 Details

    • TriadicCensus

      public TriadicCensus()
  • Method Details

    • getCounts

      public static <V, E> long[] getCounts(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.)
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph whose properties are being measured
      Returns:
      an array encoding the number of occurrences of each triad type
    • triCode

      public static <V, E> int triCode(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 63 which encodes the presence of all possible links between u, v, and w as bit flags: WU = 32, UW = 16, WV = 8, VW = 4, UV = 2, VU = 1
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph for which the calculation is being made
      u - a vertex in g
      v - a vertex in g
      w - a vertex in g
      Returns:
      an int encoding the presence of all links between u, v, and w
    • link

      protected static <V, E> boolean link(Graph<V,E> g, V a, V b)
    • triType

      public static int triType(int triCode)
      Parameters:
      triCode - the code returned by triCode()
      Returns:
      the string code associated with the numeric type
    • shouldCount

      protected static <V, E> boolean shouldCount(Graph<V,E> g, List<V> id, V u, V v, V w)
      Return true iff this ordering is canonical and therefore we should build statistics for it.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph whose properties are being examined
      id - a list of the vertices in g; used to assign an index to each
      u - a vertex in g
      v - a vertex in g
      w - a vertex in g
      Returns:
      true if index(u) < index(w), or if index(v) < index(w) < index(u) and v doesn't link to w; false otherwise