edu.uci.ics.jung.algorithms.metrics
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:

Number	Configuration	Notes
1	003	The empty triad
2	012
3	102
4	021D	"Down": the directed edges point away
5	021U	"Up": the directed edges meet
6	021C	"Circle": one in, one out
7	111D	"Down": 021D but one edge is mutual
8	111U	"Up": 021U but one edge is mutual
9	030T	"Transitive": two point to the same vertex
10	030C	"Circle": A->B->C->A
11	201
12	120D	"Down": 021D but the third edge is mutual
13	120U	"Up": 021U but the third edge is mutual
14	120C	"Circle": 021C but the third edge is mutual
15	210
16	300	The 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.

Author:

Danyel Fisher, Tom Nelson - converted to jung2

Field Summary

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 String[]	TRIAD_NAMES

Constructor Summary

TriadicCensus()

Method Summary

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.
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) 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(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 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(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(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(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(Graph<V,E> g,
                                           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