Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.metrics
Class TriadicCensus

    java.lang.Object
      edu.uci.ics.jung.algorithms.metrics.TriadicCensus

public class TriadicCensus
extends 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);

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.

Author:
  Danyel Fisher

Field Summary
`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 Summary
`TriadicCensus()`

Method Summary
`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
`static int` | `triCode(Vertex u, Vertex v, Vertex w)` This is the core of the technique in the paper.
`static int` | `triType(int triCode)` Simply returns the triCode.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### TRIAD_NAMES

    public static final String[] TRIAD_NAMES

### MAX_TRIADS

    public static final int MAX_TRIADS

### codeToType

    protected static final int[] codeToType

  For debugging purposes, this is copied straight out of the paper which means that they refer to triad types 1-16.

Constructor Detail

### TriadicCensus

    public TriadicCensus()

Method Detail

### getCounts

    public 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`. (The 0th element is not meaningful; this array is effectively 1-based.)

  Parameters:
    `g` -

### triCode

    public static int triCode(Vertex u,
                              Vertex v,
                              Vertex 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 boolean link(Vertex a,
                                  Vertex b)

### triType

    public static int triType(int triCode)

  Simply returns the triCode.

  Parameters:
    `triCode` -
  Returns:

### shouldCount

    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

  Parameters:
    `id` -
    `u` -
    `v` -
    `w` -
  Returns:

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD