Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Algorithms to characterize the number of triangles in a graph."""
3from collections import Counter
4from itertools import chain, combinations
6import networkx as nx
7from networkx.utils import not_implemented_for
9__all__ = [
10 "triangles",
11 "all_triangles",
12 "average_clustering",
13 "clustering",
14 "transitivity",
15 "square_clustering",
16 "generalized_degree",
17]
20@not_implemented_for("directed")
21@nx._dispatchable
22def triangles(G, nodes=None):
23 """Compute the number of triangles.
25 Finds the number of triangles that include a node as one vertex.
27 Parameters
28 ----------
29 G : graph
30 A networkx graph
32 nodes : node, iterable of nodes, or None (default=None)
33 If a singleton node, return the number of triangles for that node.
34 If an iterable, compute the number of triangles for each of those nodes.
35 If `None` (the default) compute the number of triangles for all nodes in `G`.
37 Returns
38 -------
39 out : dict or int
40 If `nodes` is a container of nodes, returns number of triangles keyed by node (dict).
41 If `nodes` is a specific node, returns number of triangles for the node (int).
43 Examples
44 --------
45 >>> G = nx.complete_graph(5)
46 >>> print(nx.triangles(G, 0))
47 6
48 >>> print(nx.triangles(G))
49 {0: 6, 1: 6, 2: 6, 3: 6, 4: 6}
50 >>> print(list(nx.triangles(G, [0, 1]).values()))
51 [6, 6]
53 The total number of unique triangles in `G` can be determined by summing
54 the number of triangles for each node and dividing by 3 (because a given
55 triangle gets counted three times, once for each of its nodes).
57 >>> sum(nx.triangles(G).values()) // 3
58 10
60 Notes
61 -----
62 Self loops are ignored.
64 """
65 if nodes is not None:
66 # If `nodes` represents a single node, return only its number of triangles
67 if nodes in G:
68 return next(_triangles_and_degree_iter(G, nodes))[2] // 2
70 # if `nodes` is a container of nodes, then return a
71 # dictionary mapping node to number of triangles.
72 return {v: t // 2 for v, d, t, _ in _triangles_and_degree_iter(G, nodes)}
74 # if nodes is None, then compute triangles for the complete graph
76 # dict used to avoid visiting the same nodes twice
77 # this allows calculating/counting each triangle only once
78 later_nbrs = {}
80 # iterate over the nodes in a graph
81 for node, neighbors in G.adjacency():
82 later_nbrs[node] = {n for n in neighbors if n not in later_nbrs and n != node}
84 # instantiate Counter for each node to include isolated nodes
85 # add 1 to the count if a nodes neighbor's neighbor is also a neighbor
86 triangle_counts = Counter(dict.fromkeys(G, 0))
87 for node1, neighbors in later_nbrs.items():
88 for node2 in neighbors:
89 third_nodes = neighbors & later_nbrs[node2]
90 m = len(third_nodes)
91 triangle_counts[node1] += m
92 triangle_counts[node2] += m
93 triangle_counts.update(third_nodes)
95 return dict(triangle_counts)
98@not_implemented_for("multigraph")
99def _triangles_and_degree_iter(G, nodes=None):
100 """Return an iterator of (node, degree, triangles, generalized degree).
102 This double counts triangles so you may want to divide by 2.
103 See degree(), triangles() and generalized_degree() for definitions
104 and details.
106 """
107 if nodes is None:
108 nodes_nbrs = G.adj.items()
109 else:
110 nodes_nbrs = ((n, G[n]) for n in G.nbunch_iter(nodes))
112 for v, v_nbrs in nodes_nbrs:
113 vs = set(v_nbrs) - {v}
114 gen_degree = Counter(len(vs & (set(G[w]) - {w})) for w in vs)
115 ntriangles = sum(k * val for k, val in gen_degree.items())
116 yield (v, len(vs), ntriangles, gen_degree)
119@not_implemented_for("multigraph")
120def _weighted_triangles_and_degree_iter(G, nodes=None, weight="weight"):
121 """Return an iterator of (node, degree, weighted_triangles).
123 Used for weighted clustering.
124 Note: this returns the geometric average weight of edges in the triangle.
125 Also, each triangle is counted twice (each direction).
126 So you may want to divide by 2.
128 """
129 import numpy as np
131 if weight is None or G.number_of_edges() == 0:
132 max_weight = 1
133 else:
134 max_weight = max(d.get(weight, 1) for u, v, d in G.edges(data=True))
135 if nodes is None:
136 nodes_nbrs = G.adj.items()
137 else:
138 nodes_nbrs = ((n, G[n]) for n in G.nbunch_iter(nodes))
140 def wt(u, v):
141 return G[u][v].get(weight, 1) / max_weight
143 for i, nbrs in nodes_nbrs:
144 inbrs = set(nbrs) - {i}
145 weighted_triangles = 0
146 seen = set()
147 for j in inbrs:
148 seen.add(j)
149 # This avoids counting twice -- we double at the end.
150 jnbrs = set(G[j]) - seen
151 # Only compute the edge weight once, before the inner inner
152 # loop.
153 wij = wt(i, j)
154 weighted_triangles += np.cbrt(
155 [(wij * wt(j, k) * wt(k, i)) for k in inbrs & jnbrs]
156 ).sum()
157 yield (i, len(inbrs), 2 * float(weighted_triangles))
160@not_implemented_for("multigraph")
161def _directed_triangles_and_degree_iter(G, nodes=None):
162 """Return an iterator of
163 (node, total_degree, reciprocal_degree, directed_triangles).
165 Used for directed clustering.
166 Note that unlike `_triangles_and_degree_iter()`, this function counts
167 directed triangles so does not count triangles twice.
169 """
170 nodes_nbrs = ((n, G._pred[n], G._succ[n]) for n in G.nbunch_iter(nodes))
172 for i, preds, succs in nodes_nbrs:
173 ipreds = set(preds) - {i}
174 isuccs = set(succs) - {i}
176 directed_triangles = 0
177 for j in chain(ipreds, isuccs):
178 jpreds = set(G._pred[j]) - {j}
179 jsuccs = set(G._succ[j]) - {j}
180 directed_triangles += sum(
181 1
182 for k in chain(
183 (ipreds & jpreds),
184 (ipreds & jsuccs),
185 (isuccs & jpreds),
186 (isuccs & jsuccs),
187 )
188 )
189 dtotal = len(ipreds) + len(isuccs)
190 dbidirectional = len(ipreds & isuccs)
191 yield (i, dtotal, dbidirectional, directed_triangles)
194@not_implemented_for("multigraph")
195def _directed_weighted_triangles_and_degree_iter(G, nodes=None, weight="weight"):
196 """Return an iterator of
197 (node, total_degree, reciprocal_degree, directed_weighted_triangles).
199 Used for directed weighted clustering.
200 Note that unlike `_weighted_triangles_and_degree_iter()`, this function counts
201 directed triangles so does not count triangles twice.
203 """
204 import numpy as np
206 if weight is None or G.number_of_edges() == 0:
207 max_weight = 1
208 else:
209 max_weight = max(d.get(weight, 1) for u, v, d in G.edges(data=True))
211 nodes_nbrs = ((n, G._pred[n], G._succ[n]) for n in G.nbunch_iter(nodes))
213 def wt(u, v):
214 return G[u][v].get(weight, 1) / max_weight
216 for i, preds, succs in nodes_nbrs:
217 ipreds = set(preds) - {i}
218 isuccs = set(succs) - {i}
220 directed_triangles = 0
221 for j in ipreds:
222 jpreds = set(G._pred[j]) - {j}
223 jsuccs = set(G._succ[j]) - {j}
224 directed_triangles += np.cbrt(
225 [(wt(j, i) * wt(k, i) * wt(k, j)) for k in ipreds & jpreds]
226 ).sum()
227 directed_triangles += np.cbrt(
228 [(wt(j, i) * wt(k, i) * wt(j, k)) for k in ipreds & jsuccs]
229 ).sum()
230 directed_triangles += np.cbrt(
231 [(wt(j, i) * wt(i, k) * wt(k, j)) for k in isuccs & jpreds]
232 ).sum()
233 directed_triangles += np.cbrt(
234 [(wt(j, i) * wt(i, k) * wt(j, k)) for k in isuccs & jsuccs]
235 ).sum()
237 for j in isuccs:
238 jpreds = set(G._pred[j]) - {j}
239 jsuccs = set(G._succ[j]) - {j}
240 directed_triangles += np.cbrt(
241 [(wt(i, j) * wt(k, i) * wt(k, j)) for k in ipreds & jpreds]
242 ).sum()
243 directed_triangles += np.cbrt(
244 [(wt(i, j) * wt(k, i) * wt(j, k)) for k in ipreds & jsuccs]
245 ).sum()
246 directed_triangles += np.cbrt(
247 [(wt(i, j) * wt(i, k) * wt(k, j)) for k in isuccs & jpreds]
248 ).sum()
249 directed_triangles += np.cbrt(
250 [(wt(i, j) * wt(i, k) * wt(j, k)) for k in isuccs & jsuccs]
251 ).sum()
253 dtotal = len(ipreds) + len(isuccs)
254 dbidirectional = len(ipreds & isuccs)
255 yield (i, dtotal, dbidirectional, float(directed_triangles))
258@not_implemented_for("directed")
259@nx._dispatchable
260def all_triangles(G, nbunch=None):
261 """
262 Yields all unique triangles in an undirected graph.
264 A triangle is a set of three distinct nodes where each node is connected to
265 the other two.
267 Parameters
268 ----------
269 G : NetworkX graph
270 An undirected graph.
272 nbunch : node, iterable of nodes, or None (default=None)
273 If a node or iterable of nodes, only triangles involving at least one
274 node in `nbunch` are yielded.
275 If ``None``, yields all unique triangles in the graph.
277 Yields
278 ------
279 tuple
280 A tuple of three nodes forming a triangle ``(u, v, w)``.
282 Examples
283 --------
284 >>> G = nx.complete_graph(4)
285 >>> sorted([sorted(t) for t in all_triangles(G)])
286 [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]
288 Notes
289 -----
290 This algorithm ensures each triangle is yielded once using an internal node ordering.
291 In multigraphs, triangles are identified by their unique set of nodes,
292 ignoring multiple edges between the same nodes. Self-loops are ignored.
293 Runs in ``O(m * d)`` time in the worst case, where ``m`` the number of edges
294 and ``d`` the maximum degree.
296 See Also
297 --------
298 :func:`~networkx.algorithms.triads.all_triads` : related function for directed graphs
299 """
300 if nbunch is None:
301 nbunch = relevant_nodes = G
302 else:
303 nbunch = dict.fromkeys(G.nbunch_iter(nbunch))
304 relevant_nodes = chain(
305 nbunch,
306 (nbr for node in nbunch for nbr in G.neighbors(node) if nbr not in nbunch),
307 )
309 node_to_id = {node: i for i, node in enumerate(relevant_nodes)}
311 for u in nbunch:
312 u_id = node_to_id[u]
313 u_nbrs = G._adj[u].keys()
314 for v in u_nbrs:
315 v_id = node_to_id.get(v, -1)
316 if v_id <= u_id:
317 continue
318 v_nbrs = G._adj[v].keys()
319 for w in v_nbrs & u_nbrs:
320 if node_to_id.get(w, -1) > v_id:
321 yield u, v, w
324@nx._dispatchable(edge_attrs="weight")
325def average_clustering(G, nodes=None, weight=None, count_zeros=True):
326 r"""Compute the average clustering coefficient for the graph G.
328 The clustering coefficient for the graph is the average,
330 .. math::
332 C = \frac{1}{n}\sum_{v \in G} c_v,
334 where :math:`n` is the number of nodes in `G`.
336 Parameters
337 ----------
338 G : graph
340 nodes : container of nodes, optional (default=all nodes in G)
341 Compute average clustering for nodes in this container.
343 weight : string or None, optional (default=None)
344 The edge attribute that holds the numerical value used as a weight.
345 If None, then each edge has weight 1.
347 count_zeros : bool
348 If False include only the nodes with nonzero clustering in the average.
350 Returns
351 -------
352 avg : float
353 Average clustering
355 Examples
356 --------
357 >>> G = nx.complete_graph(5)
358 >>> print(nx.average_clustering(G))
359 1.0
361 Notes
362 -----
363 This is a space saving routine; it might be faster
364 to use the clustering function to get a list and then take the average.
366 Self loops are ignored.
368 References
369 ----------
370 .. [1] Generalizations of the clustering coefficient to weighted
371 complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela,
372 K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007).
373 http://jponnela.com/web_documents/a9.pdf
374 .. [2] Marcus Kaiser, Mean clustering coefficients: the role of isolated
375 nodes and leafs on clustering measures for small-world networks.
376 https://arxiv.org/abs/0802.2512
377 """
378 c = clustering(G, nodes, weight=weight).values()
379 if not count_zeros:
380 c = [v for v in c if abs(v) > 0]
381 return sum(c) / len(c)
384@nx._dispatchable(edge_attrs="weight")
385def clustering(G, nodes=None, weight=None):
386 r"""Compute the clustering coefficient for nodes.
388 For unweighted graphs, the clustering of a node :math:`u`
389 is the fraction of possible triangles through that node that exist,
391 .. math::
393 c_u = \frac{2 T(u)}{deg(u)(deg(u)-1)},
395 where :math:`T(u)` is the number of triangles through node :math:`u` and
396 :math:`deg(u)` is the degree of :math:`u`.
398 For weighted graphs, there are several ways to define clustering [1]_.
399 the one used here is defined
400 as the geometric average of the subgraph edge weights [2]_,
402 .. math::
404 c_u = \frac{1}{deg(u)(deg(u)-1))}
405 \sum_{vw} (\hat{w}_{uv} \hat{w}_{uw} \hat{w}_{vw})^{1/3}.
407 The edge weights :math:`\hat{w}_{uv}` are normalized by the maximum weight
408 in the network :math:`\hat{w}_{uv} = w_{uv}/\max(w)`.
410 The value of :math:`c_u` is assigned to 0 if :math:`deg(u) < 2`.
412 Additionally, this weighted definition has been generalized to support negative edge weights [3]_.
414 For directed graphs, the clustering is similarly defined as the fraction
415 of all possible directed triangles or geometric average of the subgraph
416 edge weights for unweighted and weighted directed graph respectively [4]_.
418 .. math::
420 c_u = \frac{T(u)}{2(deg^{tot}(u)(deg^{tot}(u)-1) - 2deg^{\leftrightarrow}(u))},
422 where :math:`T(u)` is the number of directed triangles through node
423 :math:`u`, :math:`deg^{tot}(u)` is the sum of in degree and out degree of
424 :math:`u` and :math:`deg^{\leftrightarrow}(u)` is the reciprocal degree of
425 :math:`u`.
428 Parameters
429 ----------
430 G : graph
432 nodes : node, iterable of nodes, or None (default=None)
433 If a singleton node, return the number of triangles for that node.
434 If an iterable, compute the number of triangles for each of those nodes.
435 If `None` (the default) compute the number of triangles for all nodes in `G`.
437 weight : string or None, optional (default=None)
438 The edge attribute that holds the numerical value used as a weight.
439 If None, then each edge has weight 1.
441 Returns
442 -------
443 out : float, or dictionary
444 Clustering coefficient at specified nodes
446 Examples
447 --------
448 >>> G = nx.complete_graph(5)
449 >>> print(nx.clustering(G, 0))
450 1.0
451 >>> print(nx.clustering(G))
452 {0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
454 Notes
455 -----
456 Self loops are ignored.
458 References
459 ----------
460 .. [1] Generalizations of the clustering coefficient to weighted
461 complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela,
462 K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007).
463 http://jponnela.com/web_documents/a9.pdf
464 .. [2] Intensity and coherence of motifs in weighted complex
465 networks by J. P. Onnela, J. Saramäki, J. Kertész, and K. Kaski,
466 Physical Review E, 71(6), 065103 (2005).
467 .. [3] Generalization of Clustering Coefficients to Signed Correlation Networks
468 by G. Costantini and M. Perugini, PloS one, 9(2), e88669 (2014).
469 .. [4] Clustering in complex directed networks by G. Fagiolo,
470 Physical Review E, 76(2), 026107 (2007).
471 """
472 if G.is_directed():
473 if weight is not None:
474 td_iter = _directed_weighted_triangles_and_degree_iter(G, nodes, weight)
475 clusterc = {
476 v: 0 if t == 0 else t / ((dt * (dt - 1) - 2 * db) * 2)
477 for v, dt, db, t in td_iter
478 }
479 else:
480 td_iter = _directed_triangles_and_degree_iter(G, nodes)
481 clusterc = {
482 v: 0 if t == 0 else t / ((dt * (dt - 1) - 2 * db) * 2)
483 for v, dt, db, t in td_iter
484 }
485 else:
486 # The formula 2*T/(d*(d-1)) from docs is t/(d*(d-1)) here b/c t==2*T
487 if weight is not None:
488 td_iter = _weighted_triangles_and_degree_iter(G, nodes, weight)
489 clusterc = {v: 0 if t == 0 else t / (d * (d - 1)) for v, d, t in td_iter}
490 else:
491 td_iter = _triangles_and_degree_iter(G, nodes)
492 clusterc = {v: 0 if t == 0 else t / (d * (d - 1)) for v, d, t, _ in td_iter}
493 if nodes in G:
494 # Return the value of the sole entry in the dictionary.
495 return clusterc[nodes]
496 return clusterc
499@nx._dispatchable
500def transitivity(G):
501 r"""Compute graph transitivity, the fraction of all possible triangles
502 present in G.
504 Possible triangles are identified by the number of "triads"
505 (two edges with a shared vertex).
507 The transitivity is
509 .. math::
511 T = 3\frac{\#triangles}{\#triads}.
513 Parameters
514 ----------
515 G : graph
517 Returns
518 -------
519 out : float
520 Transitivity
522 Notes
523 -----
524 Self loops are ignored.
526 Examples
527 --------
528 >>> G = nx.complete_graph(5)
529 >>> print(nx.transitivity(G))
530 1.0
531 """
532 triangles_contri = [
533 (t, d * (d - 1)) for v, d, t, _ in _triangles_and_degree_iter(G)
534 ]
535 # If the graph is empty
536 if len(triangles_contri) == 0:
537 return 0
538 triangles, contri = map(sum, zip(*triangles_contri))
539 return 0 if triangles == 0 else triangles / contri
542@nx._dispatchable
543def square_clustering(G, nodes=None):
544 r"""Compute the squares clustering coefficient for nodes.
546 For each node return the fraction of possible squares that exist at
547 the node [1]_
549 .. math::
550 C_4(v) = \frac{ \sum_{u=1}^{k_v}
551 \sum_{w=u+1}^{k_v} q_v(u,w) }{ \sum_{u=1}^{k_v}
552 \sum_{w=u+1}^{k_v} [a_v(u,w) + q_v(u,w)]},
554 where :math:`q_v(u,w)` are the number of common neighbors of :math:`u` and
555 :math:`w` other than :math:`v` (ie squares), and :math:`a_v(u,w) = (k_u -
556 (1+q_v(u,w)+\theta_{uv})) + (k_w - (1+q_v(u,w)+\theta_{uw}))`, where
557 :math:`\theta_{uw} = 1` if :math:`u` and :math:`w` are connected and 0
558 otherwise. [2]_
560 Parameters
561 ----------
562 G : graph
564 nodes : container of nodes, optional (default=all nodes in G)
565 Compute clustering for nodes in this container.
567 Returns
568 -------
569 c4 : dictionary
570 A dictionary keyed by node with the square clustering coefficient value.
572 Examples
573 --------
574 >>> G = nx.complete_graph(5)
575 >>> print(nx.square_clustering(G, 0))
576 1.0
577 >>> print(nx.square_clustering(G))
578 {0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
580 Notes
581 -----
582 Self loops are ignored.
584 While :math:`C_3(v)` (triangle clustering) gives the probability that
585 two neighbors of node v are connected with each other, :math:`C_4(v)` is
586 the probability that two neighbors of node v share a common
587 neighbor different from v. This algorithm can be applied to both
588 bipartite and unipartite networks.
590 References
591 ----------
592 .. [1] Pedro G. Lind, Marta C. González, and Hans J. Herrmann. 2005
593 Cycles and clustering in bipartite networks.
594 Physical Review E (72) 056127.
595 .. [2] Zhang, Peng et al. Clustering Coefficient and Community Structure of
596 Bipartite Networks. Physica A: Statistical Mechanics and its Applications 387.27 (2008): 6869–6875.
597 https://arxiv.org/abs/0710.0117v1
598 """
599 if nodes is None:
600 node_iter = G
601 else:
602 node_iter = G.nbunch_iter(nodes)
603 clustering = {}
604 _G_adj = G._adj
606 class GAdj(dict):
607 """Calculate (and cache) node neighbor sets excluding self-loops."""
609 def __missing__(self, v):
610 v_neighbors = self[v] = set(_G_adj[v])
611 v_neighbors.discard(v) # Ignore self-loops
612 return v_neighbors
614 G_adj = GAdj() # Values are sets of neighbors (no self-loops)
616 for v in node_iter:
617 v_neighbors = G_adj[v]
618 v_degrees_m1 = len(v_neighbors) - 1 # degrees[v] - 1 (used below)
619 if v_degrees_m1 <= 0:
620 # Can't form a square without at least two neighbors
621 clustering[v] = 0
622 continue
624 # Count squares with nodes u-v-w-x from the current node v.
625 # Terms of the denominator: potential = uw_degrees - uw_count - triangles - squares
626 # uw_degrees: degrees[u] + degrees[w] for each u-w combo
627 uw_degrees = 0
628 # uw_count: 1 for each u and 1 for each w for all combos (degrees * (degrees - 1))
629 uw_count = len(v_neighbors) * v_degrees_m1
630 # triangles: 1 for each edge where u-w or w-u are connected (i.e. triangles)
631 triangles = 0
632 # squares: the number of squares (also the numerator)
633 squares = 0
635 # Iterate over all neighbors
636 for u in v_neighbors:
637 u_neighbors = G_adj[u]
638 uw_degrees += len(u_neighbors) * v_degrees_m1
639 # P2 from https://arxiv.org/abs/2007.11111
640 p2 = len(u_neighbors & v_neighbors)
641 # triangles is C_3, sigma_4 from https://arxiv.org/abs/2007.11111
642 # This double-counts triangles compared to `triangles` function
643 triangles += p2
644 # squares is C_4, sigma_12 from https://arxiv.org/abs/2007.11111
645 # Include this term, b/c a neighbor u can also be a neighbor of neighbor x
646 squares += p2 * (p2 - 1) # Will divide by 2 later
648 # And iterate over all neighbors of neighbors.
649 # These nodes x may be the corners opposite v in squares u-v-w-x.
650 two_hop_neighbors = set.union(*(G_adj[u] for u in v_neighbors))
651 two_hop_neighbors -= v_neighbors # Neighbors already counted above
652 two_hop_neighbors.discard(v)
653 for x in two_hop_neighbors:
654 p2 = len(v_neighbors & G_adj[x])
655 squares += p2 * (p2 - 1) # Will divide by 2 later
657 squares //= 2
658 potential = uw_degrees - uw_count - triangles - squares
659 if potential > 0:
660 clustering[v] = squares / potential
661 else:
662 clustering[v] = 0
663 if nodes in G:
664 # Return the value of the sole entry in the dictionary.
665 return clustering[nodes]
666 return clustering
669@not_implemented_for("directed")
670@nx._dispatchable
671def generalized_degree(G, nodes=None):
672 r"""Compute the generalized degree for nodes.
674 For each node, the generalized degree shows how many edges of given
675 triangle multiplicity the node is connected to. The triangle multiplicity
676 of an edge is the number of triangles an edge participates in. The
677 generalized degree of node :math:`i` can be written as a vector
678 :math:`\mathbf{k}_i=(k_i^{(0)}, \dotsc, k_i^{(N-2)})` where
679 :math:`k_i^{(j)}` is the number of edges attached to node :math:`i` that
680 participate in :math:`j` triangles.
682 Parameters
683 ----------
684 G : graph
686 nodes : container of nodes, optional (default=all nodes in G)
687 Compute the generalized degree for nodes in this container.
689 Returns
690 -------
691 out : Counter, or dictionary of Counters
692 Generalized degree of specified nodes. The Counter is keyed by edge
693 triangle multiplicity.
695 Examples
696 --------
697 >>> G = nx.complete_graph(5)
698 >>> print(nx.generalized_degree(G, 0))
699 Counter({3: 4})
700 >>> print(nx.generalized_degree(G))
701 {0: Counter({3: 4}), 1: Counter({3: 4}), 2: Counter({3: 4}), 3: Counter({3: 4}), 4: Counter({3: 4})}
703 To recover the number of triangles attached to a node:
705 >>> k1 = nx.generalized_degree(G, 0)
706 >>> sum([k * v for k, v in k1.items()]) / 2 == nx.triangles(G, 0)
707 True
709 Notes
710 -----
711 Self loops are ignored.
713 In a network of N nodes, the highest triangle multiplicity an edge can have
714 is N-2.
716 The return value does not include a `zero` entry if no edges of a
717 particular triangle multiplicity are present.
719 The number of triangles node :math:`i` is attached to can be recovered from
720 the generalized degree :math:`\mathbf{k}_i=(k_i^{(0)}, \dotsc,
721 k_i^{(N-2)})` by :math:`(k_i^{(1)}+2k_i^{(2)}+\dotsc +(N-2)k_i^{(N-2)})/2`.
723 References
724 ----------
725 .. [1] Networks with arbitrary edge multiplicities by V. Zlatić,
726 D. Garlaschelli and G. Caldarelli, EPL (Europhysics Letters),
727 Volume 97, Number 2 (2012).
728 https://iopscience.iop.org/article/10.1209/0295-5075/97/28005
729 """
730 if nodes in G:
731 return next(_triangles_and_degree_iter(G, nodes))[3]
732 return {v: gd for v, d, t, gd in _triangles_and_degree_iter(G, nodes)}