Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# triads.py - functions for analyzing triads of a graph
#
# Copyright 2011 Reya Group <http://www.reyagroup.com>
# Copyright 2011 Alex Levenson <alex@isnotinvain.com>
# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca>
#
# This file is part of NetworkX.
#
# information.
"""Functions for analyzing triads of a graph."""
from __future__ import division

from networkx.utils import not_implemented_for

__author__ = '\n'.join(['Alex Levenson (alex@isnontinvain.com)',
'Diederik van Liere (diederik.vanliere@rotman.utoronto.ca)'])

#: The integer codes representing each type of triad.
#:
#: Triads that are the same up to symmetry have the same code.
TRICODES = (1, 2, 2, 3, 2, 4, 6, 8, 2, 6, 5, 7, 3, 8, 7, 11, 2, 6, 4, 8, 5, 9,
9, 13, 6, 10, 9, 14, 7, 14, 12, 15, 2, 5, 6, 7, 6, 9, 10, 14, 4, 9,
9, 12, 8, 13, 14, 15, 3, 7, 8, 11, 7, 12, 14, 15, 8, 14, 13, 15,
11, 15, 15, 16)

#: The names of each type of triad. The order of the elements is
#: important: it corresponds to the tricodes given in :data:TRICODES.
TRIAD_NAMES = ('003', '012', '102', '021D', '021U', '021C', '111D', '111U',
'030T', '030C', '201', '120D', '120U', '120C', '210', '300')

TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}

def _tricode(G, v, u, w):
"""Returns the integer code of the given triad.

This is some fancy magic that comes from Batagelj and Mrvar's paper. It
treats each edge joining a pair of v, u, and w as a bit in
the binary representation of an integer.

"""
combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16),
(w, u, 32))
return sum(x for u, v, x in combos if v in G[u])

[docs]@not_implemented_for('undirected')
"""Determines the triadic census of a directed graph.

The triadic census is a count of how many of the 16 possible types of
triads are present in a directed graph.

Parameters
----------
G : digraph
A NetworkX DiGraph

Returns
-------
census : dict
Dictionary with triad names as keys and number of occurrences as values.

Notes
-----
This algorithm has complexity $O(m)$ where $m$ is the number of edges in
the graph.

--------

References
----------
algorithm for large sparse networks with small maximum degree,
University of Ljubljana,

"""
# Initialize the count for each triad to be zero.
census = {name: 0 for name in TRIAD_NAMES}
n = len(G)
# m = dict(zip(G, range(n)))
m = {v: i for i, v in enumerate(G)}
for v in G:
vnbrs = set(G.pred[v]) | set(G.succ[v])
for u in vnbrs:
if m[u] <= m[v]:
continue
neighbors = (vnbrs | set(G.succ[u]) | set(G.pred[u])) - {u, v}
if v in G[u] and u in G[v]:
census['102'] += n - len(neighbors) - 2
else:
census['012'] += n - len(neighbors) - 2
for w in neighbors:
if m[u] < m[w] or (m[v] < m[w] < m[u] and
v not in G.pred[w] and
v not in G.succ[w]):
code = _tricode(G, v, u, w)
census[TRICODE_TO_NAME[code]] += 1