public class TriadicCensus
extends java.lang.Object
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.
Modifier and Type | Field and Description |
---|---|
static int |
MAX_TRIADS |
static java.lang.String[] |
TRIAD_NAMES |
Constructor and Description |
---|
TriadicCensus() |
Modifier and Type | Method and Description |
---|---|
static long[] |
getCounts(DirectedGraph 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 boolean |
link(Vertex a,
Vertex b) |
protected static boolean |
shouldCount(Indexer id,
Vertex u,
Vertex v,
Vertex w)
Make sure we have a canonical ordering: Returns true if u < w, or v < w <
u and v doesn't link to w
|
protected static int |
triCode(Vertex u,
Vertex v,
Vertex w)
This is the core of the technique in the paper.
|
protected static int |
triType(int triCode)
Simply returns the triCode.
|
public static final java.lang.String[] TRIAD_NAMES
public static final int MAX_TRIADS
public static long[] getCounts(DirectedGraph g)
g
.
(The 0th element is not meaningful; this array is effectively 1-based.)g
- protected static int triCode(Vertex u, Vertex v, Vertex w)
u
- v
- w
- protected static int triType(int triCode)
triCode
-