/usr/lib/python3/dist-packages/networkx/algorithms/triads.py is in python3-networkx 1.11-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | # triads.py - functions for analyzing triads of a graph
#
# Copyright 2015 NetworkX developers.
# 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.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Functions for analyzing triads of a graph."""
from __future__ import division
import networkx as nx
__author__ = '\n'.join(['Alex Levenson (alex@isnontinvain.com)',
'Diederik van Liere (diederik.vanliere@rotman.utoronto.ca)'])
__all__ = ['triadic_census']
#: The names of each type of triad.
TRIAD_NAMES = ('003', '012', '102', '021D', '021U', '021C', '111D', '111U',
'030T', '030C', '201', '120D', '120U', '120C', '210', '300')
#: 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)
#: A dictionary mapping triad code to triad name.
TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}
def triad_graphs():
"""Returns a dictionary mapping triad name to triad graph."""
def abc_graph():
"""Returns a directed graph on three nodes, named ``'a'``, ``'b'``, and
``'c'``.
"""
G = nx.DiGraph()
G.add_nodes_from('abc')
return G
tg = {name: abc_graph() for name in TRIAD_NAMES}
tg['012'].add_edges_from([('a', 'b')])
tg['102'].add_edges_from([('a', 'b'), ('b', 'a')])
tg['102'].add_edges_from([('a', 'b'), ('b', 'a')])
tg['021D'].add_edges_from([('b', 'a'), ('b', 'c')])
tg['021U'].add_edges_from([('a', 'b'), ('c', 'b')])
tg['021C'].add_edges_from([('a', 'b'), ('b', 'c')])
tg['111D'].add_edges_from([('a', 'c'), ('c', 'a'), ('b', 'c')])
tg['111U'].add_edges_from([('a', 'c'), ('c', 'a'), ('c', 'b')])
tg['030T'].add_edges_from([('a', 'b'), ('c', 'b'), ('a', 'c')])
tg['030C'].add_edges_from([('b', 'a'), ('c', 'b'), ('a', 'c')])
tg['201'].add_edges_from([('a', 'b'), ('b', 'a'), ('a', 'c'), ('c', 'a')])
tg['120D'].add_edges_from([('b', 'c'), ('b', 'a'), ('a', 'c'), ('c', 'a')])
tg['120C'].add_edges_from([('a', 'b'), ('b', 'c'), ('a', 'c'), ('c', 'a')])
tg['120U'].add_edges_from([('a', 'b'), ('c', 'b'), ('a', 'c'), ('c', 'a')])
tg['210'].add_edges_from([('a', 'b'), ('b', 'c'), ('c', 'b'), ('a', 'c'),
('c', 'a')])
tg['300'].add_edges_from([('a', 'b'), ('b', 'a'), ('b', 'c'), ('c', 'b'),
('a', 'c'), ('c', 'a')])
return tg
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])
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 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
----------
.. [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
"""
if not G.is_directed():
raise nx.NetworkXError('Not defined for undirected graphs.')
# 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] and 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
|