2
Algorithms to characterize the number of triangles in a graph.
5
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
6
# Copyright (C) 2004-2008 by
1
# -*- coding: utf-8 -*-
2
"""Algorithms to characterize the number of triangles in a graph."""
3
from itertools import combinations
5
from networkx import NetworkXError
6
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>',
7
'Dan Schult (dschult@colgate.edu)',
8
'Pieter Swart (swart@lanl.gov)',
9
'Jordi Torrents <jtorrents@milnou.net>'])
10
# Copyright (C) 2004-2011 by
7
11
# Aric Hagberg <hagberg@lanl.gov>
8
12
# Dan Schult <dschult@colgate.edu>
9
13
# Pieter Swart <swart@lanl.gov>
10
14
# All rights reserved.
13
__all__= ['triangles', 'average_clustering', 'clustering', 'transitivity']
16
from networkx import NetworkXError
18
def triangles(G,nbunch=None):
16
__all__= ['triangles', 'average_clustering', 'clustering', 'transitivity',
19
def triangles(G, nodes=None):
19
20
"""Compute the number of triangles.
21
Finds the number of triangles that include a node as one of the vertices.
22
Finds the number of triangles that include a node as one vertex.
27
nbunch : container of nodes, optional
28
Compute triangles for nodes in nbunch. The default is all nodes in G.
28
nodes : container of nodes, optional (default= all nodes in G)
29
Compute triangles for nodes in this container.
33
Number of trianges keyed by node label.
34
Number of triangles keyed by node label.
47
When computing triangles for the entire graph
48
each triangle is counted three times, once at each node.
50
Self loops are ignored.
48
When computing triangles for the entire graph each triangle is counted
49
three times, once at each node. Self loops are ignored.
53
52
if G.is_directed():
54
53
raise NetworkXError("triangles() is not defined for directed graphs.")
56
return next(_triangles_and_degree_iter(G,nbunch))[2] // 2 # return single value
57
return dict( (v,t // 2) for v,d,t in _triangles_and_degree_iter(G,nbunch))
56
return next(_triangles_and_degree_iter(G,nodes))[2] // 2
57
return dict( (v,t // 2) for v,d,t in _triangles_and_degree_iter(G,nodes))
59
def _triangles_and_degree_iter(G,nbunch=None):
59
def _triangles_and_degree_iter(G,nodes=None):
60
60
""" Return an iterator of (node, degree, triangles).
62
62
This double counts triangles so you may want to divide by 2.
66
66
if G.is_multigraph():
67
67
raise NetworkXError("Not defined for multigraphs.")
70
nodes_nbrs = iter(G.adj.items())
70
nodes_nbrs = G.adj.items()
72
nodes_nbrs= ( (n,G[n]) for n in G.nbunch_iter(nbunch) )
72
nodes_nbrs= ( (n,G[n]) for n in G.nbunch_iter(nodes) )
74
74
for v,v_nbrs in nodes_nbrs:
75
vs=set(v_nbrs)-set([v])
83
79
ntriangles+=len(vs.intersection(ws))
84
80
yield (v,len(vs),ntriangles)
87
def average_clustering(G):
88
"""Compute average clustering coefficient.
90
A clustering coefficient for the whole graph is the average,
83
def _weighted_triangles_and_degree_iter(G, nodes=None, weight='weight'):
84
""" Return an iterator of (node, degree, weighted_triangles).
86
Used for weighted clustering.
90
raise NetworkXError("Not defined for multigraphs.")
92
if weight is None or G.edges()==[]:
95
max_weight=float(max(d.get(weight,1.0)
96
for u,v,d in G.edges(data=True)))
98
nodes_nbrs = G.adj.items()
100
nodes_nbrs= ( (n,G[n]) for n in G.nbunch_iter(nodes) )
102
for i,nbrs in nodes_nbrs:
103
inbrs=set(nbrs)-set([i])
104
weighted_triangles=0.0
107
wij=G[i][j].get(weight,1.0)/max_weight
109
jnbrs=set(G[j])-seen # this keeps from double counting
110
for k in inbrs&jnbrs:
111
wjk=G[j][k].get(weight,1.0)/max_weight
112
wki=G[i][k].get(weight,1.0)/max_weight
113
weighted_triangles+=(wij*wjk*wki)**(1.0/3.0)
114
yield (i,len(inbrs),weighted_triangles*2)
117
def average_clustering(G, nodes=None, weight=None, count_zeros=True):
118
r"""Compute the average clustering coefficient for the graph G.
120
The clustering coefficient for the graph is the average,
94
C = \\frac{1}{n}\\sum_{v \in G} c_v,
124
C = \frac{1}{n}\sum_{v \in G} c_v,
96
where :math:`n` is the number of nodes in :math:`G`.
126
where `n` is the number of nodes in `G`.
132
nodes : container of nodes, optional (default=all nodes in G)
133
Compute average clustering for nodes in this container.
135
weight : string or None, optional (default=None)
136
The edge attribute that holds the numerical value used as a weight.
137
If None, then each edge has weight 1.
139
count_zeros : bool (default=False)
140
If False include only the nodes with nonzero clustering in the average.
106
145
Average clustering
116
155
This is a space saving routine; it might be faster
117
to use clustering to get a list and then take the average.
156
to use the clustering function to get a list and then take the average.
119
158
Self loops are ignored.
162
.. [1] Generalizations of the clustering coefficient to weighted
163
complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela,
164
K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007).
165
http://jponnela.com/web_documents/a9.pdf
166
.. [2] Marcus Kaiser, Mean clustering coefficients: the role of isolated
167
nodes and leafs on clustering measures for small-world networks.
168
http://arxiv.org/abs/0802.2512
123
s=sum(clustering(G).values())
124
return s/float(order)
126
def clustering(G,nbunch=None,weights=False):
127
""" Compute the clustering coefficient for nodes.
170
c=clustering(G,nodes,weight=weight).values()
172
c = [v for v in c if v > 0]
173
return sum(c)/float(len(c))
175
def clustering(G, nodes=None, weight=None):
176
r"""Compute the clustering coefficient for nodes.
178
For unweighted graphs the clustering of each node `u`
179
is the fraction of possible triangles that exist,
129
180
For each node find the fraction of possible triangles that exist,
133
c_v = \\frac{2 T(v)}{deg(v)(deg(v)-1)}
135
where :math:`T(v)` is the number of triangles through node :math:`v`.
184
c_u = \frac{2 T(u)}{deg(u)(deg(u)-1)},
186
where `T(u)` is the number of triangles through node `u` and
187
`deg(u)` is the degree of `u`.
189
For weighted graphs the clustering is defined
190
as the geometric average of the subgraph edge weights [1]_,
194
c_u = \frac{1}{deg(u)(deg(u)-1))}
195
\sum_{uv} (\hat{w}_{uv} \hat{w}_{uw} \hat{w}_{vw})^{1/3}.
197
The edge weights `\hat{w}_{uv}` are normalized by the maximum weight in the
198
network `\hat{w}_{uv} = w_{uv}/\max(w)`.
200
The value of `c_u` is assigned to 0 if `deg(u) < 2`.
141
nbunch : container of nodes, optional
142
Limit to specified nodes. Default is entire graph.
143
weights : bool, optional
144
If True return fraction of connected triples as dictionary
206
nodes : container of nodes, optional (default=all nodes in G)
207
Compute clustering for nodes in this container.
209
weight : string or None, optional (default=None)
210
The edge attribute that holds the numerical value used as a weight.
211
If None, then each edge has weight 1.
148
out : float, dictionary or tuple of dictionaries
215
out : float, or dictionary
149
216
Clustering coefficient at specified nodes
156
223
>>> print(nx.clustering(G))
157
224
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
162
The weights are the fraction of connected triples in the graph
163
which include the keyed node. Ths is useful for computing
166
228
Self loops are ignored.
232
.. [1] Generalizations of the clustering coefficient to weighted
233
complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela,
234
K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007).
235
http://jponnela.com/web_documents/a9.pdf
169
237
if G.is_directed():
170
raise NetworkXError("Clustering algorithms are not defined for directed graphs.")
174
for v,d,t in _triangles_and_degree_iter(G,nbunch):
175
weights[v]=float(d*(d-1))
179
clusterc[v]=t/float(d*(d-1))
180
scale=1./sum(weights.values())
181
for v,w in weights.items():
183
return clusterc,weights
238
raise NetworkXError('Clustering algorithms are not defined ',
239
'for directed graphs.')
240
if weight is not None:
241
td_iter=_weighted_triangles_and_degree_iter(G,nodes,weight)
243
td_iter=_triangles_and_degree_iter(G,nodes)
186
for v,d,t in _triangles_and_degree_iter(G,nbunch):
247
for v,d,t in td_iter:
190
251
clusterc[v]=t/float(d*(d-1))
193
254
return list(clusterc.values())[0] # return single value
196
257
def transitivity(G):
197
"""Compute transitivity.
199
Finds the fraction of all possible triangles which are in fact triangles.
200
Possible triangles are identified by the number of "triads" (two edges
201
with a shared vertex).
203
T = 3*triangles/triads
258
r"""Compute graph transitivity, the fraction of all possible triangles
261
Possible triangles are identified by the number of "triads"
262
(two edges with a shared vertex).
268
T = 3\frac{\#triangles}{\#triads}.
231
293
return triangles/float(contri)
295
def square_clustering(G, nodes=None):
296
r""" Compute the squares clustering coefficient for nodes.
298
For each node return the fraction of possible squares that exist at
302
C_4(v) = \frac{ \sum_{u=1}^{k_v}
303
\sum_{w=u+1}^{k_v} q_v(u,w) }{ \sum_{u=1}^{k_v}
304
\sum_{w=u+1}^{k_v} [a_v(u,w) + q_v(u,w)]},
306
where `q_v(u,w)` are the number of common neighbors of `u` and `w`
307
other than `v` (ie squares), and
308
`a_v(u,w) = (k_u - (1+q_v(u,w)+\theta_{uv}))(k_w - (1+q_v(u,w)+\theta_{uw}))`,
309
where `\theta_{uw} = 1` if `u` and `w` are connected and 0 otherwise.
315
nodes : container of nodes, optional (default=all nodes in G)
316
Compute clustering for nodes in this container.
321
A dictionary keyed by node with the square clustering coefficient value.
325
>>> G=nx.complete_graph(5)
326
>>> print(nx.square_clustering(G,0))
328
>>> print(nx.square_clustering(G))
329
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
333
While `C_3(v)` (triangle clustering) gives the probability that
334
two neighbors of node v are connected with each other, `C_4(v)` is
335
the probability that two neighbors of node v share a common
336
neighbor different from v. This algorithm can be applied to both
337
bipartite and unipartite networks.
341
.. [1] Pedro G. Lind, Marta C. González, and Hans J. Herrmann. 2005
342
Cycles and clustering in bipartite networks.
343
Physical Review E (72) 056127.
348
node_iter = G.nbunch_iter(nodes)
353
for u,w in combinations(G[v], 2):
354
squares = len((set(G[u]) & set(G[w])) - set([v]))
355
clustering[v] += squares
359
potential += (len(G[u]) - degm) * (len(G[w]) - degm) + squares
361
clustering[v] /= potential
363
return list(clustering.values())[0] # return single value
added
removed
networkx/algorithms/cluster.py
