Class TriadicCensus
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.metrics.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);
wheredg
is aDirectedGraph
. 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.
-
-
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 ing
.protected static <V,E>
booleanlink(edu.uci.ics.jung.graph.Graph<V,E> g, V a, V b)
protected static <V,E>
booleanshouldCount(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 wstatic <V,E>
inttriCode(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.
-
-
-
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 ing
. (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
-
-