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:
Descriptions of the different types of triads 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
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(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(Graph<V,E> g, V a, V b)
protected static <V,E>
booleanshouldCount(Graph<V,E> g, java.util.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>
inttriCode(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)
-
-
-
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 ing
. (The 0th element is not meaningful; this array is effectively 1-based.)- Type Parameters:
V
- the vertex typeE
- 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 typeE
- the edge type- Parameters:
g
- the graph for which the calculation is being madeu
- a vertex in gv
- a vertex in gw
- 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 bytriCode()
- Returns:
- the string code associated with the numeric type
-
shouldCount
protected static <V,E> boolean shouldCount(Graph<V,E> g, java.util.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 typeE
- the edge type- Parameters:
g
- the graph whose properties are being examinedid
- a list of the vertices in g; used to assign an index to eachu
- a vertex in gv
- a vertex in gw
- 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
-
-