Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# See https://github.com/networkx/networkx/pull/1474
# 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>
"""Functions for analyzing triads of a graph."""

from itertools import combinations, permutations
from collections import defaultdict
from random import sample

import networkx as nx
from networkx.utils import not_implemented_for

__all__ = [
"all_triplets",
]

#: 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.
"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") def triadic_census(G): """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 type 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. See also -------- triad_graph References ---------- .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census algorithm for large sparse networks with small maximum degree, University of Ljubljana, http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf """ # 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} # Calculate dyadic triads instead of counting them. if v in G[u] and u in G[v]: census["102"] += n - len(neighbors) - 2 else: census["012"] += n - len(neighbors) - 2 # Count connected triads. 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 # null triads = total number of possible triads - all found triads # # Use integer division here, since we know this formula guarantees an # integral value. census["003"] = ((n * (n - 1) * (n - 2)) // 6) - sum(census.values()) return census
def is_triad(G): """Returns True if the graph G is a triad, else False. Parameters ---------- G : graph A NetworkX Graph Returns ------- istriad : boolean Whether G is a valid triad """ if isinstance(G, nx.Graph): if G.order() == 3 and nx.is_directed(G): if not any((n, n) in G.edges() for n in G.nodes()): return True return False
[docs]@not_implemented_for("undirected") def all_triplets(G): """Returns a generator of all possible sets of 3 nodes in a DiGraph. Parameters ---------- G : digraph A NetworkX DiGraph Returns ------- triplets : generator of 3-tuples Generator of tuples of 3 nodes """ triplets = combinations(G.nodes(), 3) return triplets
[docs]@not_implemented_for("undirected") def all_triads(G): """A generator of all possible triads in G. Parameters ---------- G : digraph A NetworkX DiGraph Returns ------- all_triads : generator of DiGraphs Generator of triads (order-3 DiGraphs) """ triplets = combinations(G.nodes(), 3) for triplet in triplets: yield G.subgraph(triplet).copy()