networkx.algorithms.cluster.generalized_degree

generalized_degree(G, nodes=None)[source]

Compute the generalized degree for nodes.

For each node, the generalized degree shows how many edges of given triangle multiplicity the node is connected to. The triangle multiplicity of an edge is the number of triangles an edge participates in. The generalized degree of node \(i\) can be written as a vector \(\mathbf{k}_i=(k_i^{(0)}, \dotsc, k_i^{(N-2)})\) where \(k_i^{(j)}\) is the number of edges attached to node \(i\) that participate in \(j\) triangles.

Parameters

  • G (graph)

  • nodes (container of nodes, optional (default=all nodes in G)) – Compute the generalized degree for nodes in this container.

Returns

out – Generalized degree of specified nodes. The Counter is keyed by edge triangle multiplicity.

Return type

Counter, or dictionary of Counters

Examples

>>> G = nx.complete_graph(5)
>>> print(nx.generalized_degree(G, 0))
Counter({3: 4})
>>> print(nx.generalized_degree(G))
{0: Counter({3: 4}), 1: Counter({3: 4}), 2: Counter({3: 4}), 3: Counter({3: 4}), 4: Counter({3: 4})}

To recover the number of triangles attached to a node:

>>> k1 = nx.generalized_degree(G, 0)
>>> sum([k * v for k, v in k1.items()]) / 2 == nx.triangles(G, 0)
True

Notes

In a network of N nodes, the highest triangle multiplicty an edge can have is N-2.

The return value does not include a zero entry if no edges of a particular triangle multiplicity are present.

The number of triangles node \(i\) is attached to can be recovered from the generalized degree \(\mathbf{k}_i=(k_i^{(0)}, \dotsc, k_i^{(N-2)})\) by \((k_i^{(1)}+2k_i^{(2)}+\dotsc +(N-2)k_i^{(N-2)})/2\).

References

1

Networks with arbitrary edge multiplicities by V. Zlatić, D. Garlaschelli and G. Caldarelli, EPL (Europhysics Letters), Volume 97, Number 2 (2012). https://iopscience.iop.org/article/10.1209/0295-5075/97/28005