triadic_census

triadic_census(G, nodelist=None)

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. If a list of nodes is passed, then only those triads are taken into account which have elements of nodelist in them.

Parameters:

Gdigraph

A NetworkX DiGraph

nodelistlist

List of nodes for which you want to calculate triadic census

Returns:

censusdict

Dictionary with triad type as keys and number of occurrences as values.

Raises:

ValueError

If nodelist contains duplicate nodes or nodes not in G. If you want to ignore this you can preprocess with set(nodelist) & G.nodes

See also

triad_graph

Notes

This algorithm has complexity \(O(m)\) where \(m\) is the number of edges in the 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

Examples

>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
>>> triadic_census = nx.triadic_census(G)
>>> for key, value in triadic_census.items():
...     print(f"{key}: {value}")
...
003: 0
012: 0
102: 0
021D: 0
021U: 0
021C: 0
111D: 0
111U: 0
030T: 2
030C: 2
201: 0
120D: 0
120U: 0
120C: 0
210: 0
300: 0