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"""Functions for computing clustering of pairs"""
3import itertools
5import networkx as nx
7__all__ = [
8 "clustering",
9 "average_clustering",
10 "latapy_clustering",
11 "robins_alexander_clustering",
12]
15def cc_dot(nu, nv):
16 return len(nu & nv) / len(nu | nv)
19def cc_max(nu, nv):
20 return len(nu & nv) / max(len(nu), len(nv))
23def cc_min(nu, nv):
24 return len(nu & nv) / min(len(nu), len(nv))
27modes = {"dot": cc_dot, "min": cc_min, "max": cc_max}
30@nx._dispatchable
31def latapy_clustering(G, nodes=None, mode="dot"):
32 r"""Compute a bipartite clustering coefficient for nodes.
34 The bipartite clustering coefficient is a measure of local density
35 of connections defined as [1]_:
37 .. math::
39 c_u = \frac{\sum_{v \in N(N(u))} c_{uv} }{|N(N(u))|}
41 where `N(N(u))` are the second order neighbors of `u` in `G` excluding `u`,
42 and `c_{uv}` is the pairwise clustering coefficient between nodes
43 `u` and `v`.
45 The mode selects the function for `c_{uv}` which can be:
47 `dot`:
49 .. math::
51 c_{uv}=\frac{|N(u)\cap N(v)|}{|N(u) \cup N(v)|}
53 `min`:
55 .. math::
57 c_{uv}=\frac{|N(u)\cap N(v)|}{min(|N(u)|,|N(v)|)}
59 `max`:
61 .. math::
63 c_{uv}=\frac{|N(u)\cap N(v)|}{max(|N(u)|,|N(v)|)}
66 Parameters
67 ----------
68 G : graph
69 A bipartite graph
71 nodes : list or iterable (optional)
72 Compute bipartite clustering for these nodes. The default
73 is all nodes in G.
75 mode : string
76 The pairwise bipartite clustering method to be used in the computation.
77 It must be "dot", "max", or "min".
79 Returns
80 -------
81 clustering : dictionary
82 A dictionary keyed by node with the clustering coefficient value.
85 Examples
86 --------
87 >>> from networkx.algorithms import bipartite
88 >>> G = nx.path_graph(4) # path graphs are bipartite
89 >>> c = bipartite.clustering(G)
90 >>> c[0]
91 0.5
92 >>> c = bipartite.clustering(G, mode="min")
93 >>> c[0]
94 1.0
96 See Also
97 --------
98 robins_alexander_clustering
99 average_clustering
100 networkx.algorithms.cluster.square_clustering
102 References
103 ----------
104 .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
105 Basic notions for the analysis of large two-mode networks.
106 Social Networks 30(1), 31--48.
107 """
108 if not nx.algorithms.bipartite.is_bipartite(G):
109 raise nx.NetworkXError("Graph is not bipartite")
111 try:
112 cc_func = modes[mode]
113 except KeyError as err:
114 raise nx.NetworkXError(
115 "Mode for bipartite clustering must be: dot, min or max"
116 ) from err
118 if nodes is None:
119 nodes = G
120 ccs = {}
121 for v in nodes:
122 cc = 0.0
123 nbrs2 = {u for nbr in G[v] for u in G[nbr]} - {v}
124 for u in nbrs2:
125 cc += cc_func(set(G[u]), set(G[v]))
126 if cc > 0.0: # len(nbrs2)>0
127 cc /= len(nbrs2)
128 ccs[v] = cc
129 return ccs
132clustering = latapy_clustering
135@nx._dispatchable(name="bipartite_average_clustering")
136def average_clustering(G, nodes=None, mode="dot"):
137 r"""Compute the average bipartite clustering coefficient.
139 A clustering coefficient for the whole graph is the average,
141 .. math::
143 C = \frac{1}{n}\sum_{v \in G} c_v,
145 where `n` is the number of nodes in `G`.
147 Similar measures for the two bipartite sets can be defined [1]_
149 .. math::
151 C_X = \frac{1}{|X|}\sum_{v \in X} c_v,
153 where `X` is a bipartite set of `G`.
155 Parameters
156 ----------
157 G : graph
158 a bipartite graph
160 nodes : list or iterable, optional
161 A container of nodes to use in computing the average.
162 The nodes should be either the entire graph (the default) or one of the
163 bipartite sets.
165 mode : string
166 The pairwise bipartite clustering method.
167 It must be "dot", "max", or "min"
169 Returns
170 -------
171 clustering : float
172 The average bipartite clustering for the given set of nodes or the
173 entire graph if no nodes are specified.
175 Examples
176 --------
177 >>> from networkx.algorithms import bipartite
178 >>> G = nx.star_graph(3) # star graphs are bipartite
179 >>> bipartite.average_clustering(G)
180 0.75
181 >>> X, Y = bipartite.sets(G)
182 >>> bipartite.average_clustering(G, X)
183 0.0
184 >>> bipartite.average_clustering(G, Y)
185 1.0
187 See Also
188 --------
189 clustering
191 Notes
192 -----
193 The container of nodes passed to this function must contain all of the nodes
194 in one of the bipartite sets ("top" or "bottom") in order to compute
195 the correct average bipartite clustering coefficients.
196 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
197 for further details on how bipartite graphs are handled in NetworkX.
200 References
201 ----------
202 .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
203 Basic notions for the analysis of large two-mode networks.
204 Social Networks 30(1), 31--48.
205 """
206 if nodes is None:
207 nodes = G
208 ccs = latapy_clustering(G, nodes=nodes, mode=mode)
209 return sum(ccs[v] for v in nodes) / len(nodes)
212@nx._dispatchable
213def robins_alexander_clustering(G):
214 r"""Compute the bipartite clustering of G.
216 Robins and Alexander [1]_ defined bipartite clustering coefficient as
217 four times the number of four cycles `C_4` divided by the number of
218 three paths `L_3` in a bipartite graph:
220 .. math::
222 CC_4 = \frac{4 * C_4}{L_3}
224 Parameters
225 ----------
226 G : graph
227 a bipartite graph
229 Returns
230 -------
231 clustering : float
232 The Robins and Alexander bipartite clustering for the input graph.
234 Examples
235 --------
236 >>> from networkx.algorithms import bipartite
237 >>> G = nx.davis_southern_women_graph()
238 >>> print(round(bipartite.robins_alexander_clustering(G), 3))
239 0.468
241 See Also
242 --------
243 latapy_clustering
244 networkx.algorithms.cluster.square_clustering
246 References
247 ----------
248 .. [1] Robins, G. and M. Alexander (2004). Small worlds among interlocking
249 directors: Network structure and distance in bipartite graphs.
250 Computational & Mathematical Organization Theory 10(1), 69–94.
252 """
253 if G.order() < 4 or G.size() < 3:
254 return 0
255 L_3 = _threepaths(G)
256 if L_3 == 0:
257 return 0
258 C_4 = _four_cycles(G)
259 return (4.0 * C_4) / L_3
262def _four_cycles(G):
263 # Also see `square_clustering` which counts squares in a similar way
264 cycles = 0
265 seen = set()
266 G_adj = G._adj
267 for v in G:
268 seen.add(v)
269 v_neighbors = set(G_adj[v])
270 if len(v_neighbors) < 2:
271 # Can't form a square without at least two neighbors
272 continue
273 two_hop_neighbors = set().union(*(G_adj[u] for u in v_neighbors))
274 two_hop_neighbors -= seen
275 for x in two_hop_neighbors:
276 p2 = len(v_neighbors.intersection(G_adj[x]))
277 cycles += p2 * (p2 - 1)
278 return cycles / 4
281def _threepaths(G):
282 paths = 0
283 for v in G:
284 for u in G[v]:
285 for w in set(G[u]) - {v}:
286 paths += len(set(G[w]) - {v, u})
287 # Divide by two because we count each three path twice
288 # one for each possible starting point
289 return paths / 2