public class TriadicCensus extends 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 |
---|---|
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 and Description |
---|
TriadicCensus() |
Modifier and Type | Method and 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 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)
Return true iff this ordering is canonical and therefore we should build statistics for it.
|
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) |
public static final String[] TRIAD_NAMES
public static final int MAX_TRIADS
protected static final int[] codeToType
public static <V,E> long[] getCounts(DirectedGraph<V,E> g)
g
.
(The 0th element is not meaningful; this array is effectively 1-based.)V
- the vertex typeE
- the edge typeg
- the graph whose properties are being measuredpublic static <V,E> int triCode(Graph<V,E> g, V u, V v, V w)
V
- the vertex typeE
- the edge typeg
- the graph for which the calculation is being madeu
- a vertex in gv
- a vertex in gw
- a vertex in gprotected static <V,E> boolean link(Graph<V,E> g, V a, V b)
public static int triType(int triCode)
triCode
- the code returned by triCode()
protected static <V,E> boolean shouldCount(Graph<V,E> g, List<V> id, V u, V v, V w)
V
- the vertex typeE
- the edge typeg
- 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 gCopyright © 2015. All rights reserved.