Class TriadicCensus
java.lang.Object
edu.uci.ics.jung.algorithms.metrics.TriadicCensus
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.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected 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 -
Method Summary
Modifier and TypeMethodDescriptionstatic <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> boolean 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 This is the core of the technique in the paper.static int
triType
(int triCode)
-
Field Details
-
TRIAD_NAMES
-
MAX_TRIADS
public static final int MAX_TRIADS -
codeToType
protected static final int[] codeToTypeFor 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
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
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
-
triType
public static int triType(int triCode) - Parameters:
triCode
- the code returned bytriCode()
- Returns:
- the string code associated with the numeric type
-
shouldCount
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
-