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:

Ggraph
nodescontainer of nodes, optional (default=all nodes in G): Compute the generalized degree for nodes in this container.

Returns:

outCounter, or dictionary of Counters: Generalized degree of specified nodes. The Counter is keyed by edge triangle multiplicity.

Notes

Self loops are ignored.

In a network of N nodes, the highest triangle multiplicity 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

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
----

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.