1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
"""
Algorithms to characterize the number of triangles in a graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
# Copyright (C) 2004-2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__= ['triangles', 'average_clustering', 'clustering', 'transitivity']
import networkx as nx
from networkx import NetworkXError
def triangles(G,nbunch=None):
"""Compute the number of triangles.
Finds the number of triangles that include a node as one of the vertices.
Parameters
----------
G : graph
A networkx graph
nbunch : container of nodes, optional
Compute triangles for nodes in nbunch. The default is all nodes in G.
Returns
-------
out : dictionary
Number of trianges keyed by node label.
Examples
--------
>>> G=nx.complete_graph(5)
>>> print nx.triangles(G,0)
6
>>> print nx.triangles(G)
{0: 6, 1: 6, 2: 6, 3: 6, 4: 6}
>>> print nx.triangles(G,(0,1)).values()
[6, 6]
Notes
-----
When computing triangles for the entire graph
each triangle is counted three times, once at each node.
Self loops are ignored.
"""
if G.is_directed():
raise NetworkXError("triangles() is not defined for directed graphs.")
if nbunch in G:
return _triangles_and_degree_iter(G,nbunch).next()[2]/2 # return single value
return dict( (v,t/2) for v,d,t in _triangles_and_degree_iter(G,nbunch))
def _triangles_and_degree_iter(G,nbunch=None):
""" Return an iterator of (node, degree, triangles).
This double counts triangles so you may want to divide by 2.
See degree() and triangles() for definitions and details.
"""
if G.is_multigraph():
raise NetworkXError("Not defined for multigraphs.")
if nbunch is None:
nodes_nbrs = G.adj.iteritems()
else:
nodes_nbrs= ( (n,G[n]) for n in G.nbunch_iter(nbunch) )
for v,v_nbrs in nodes_nbrs:
vs=set(v_nbrs)
if v in vs:
vs.remove(v)
ntriangles=0
for w in vs:
ws=set(G[w])
if w in ws:
ws.remove(w)
ntriangles+=len(vs.intersection(ws))
yield (v,len(vs),ntriangles)
def average_clustering(G):
"""Compute average clustering coefficient.
A clustering coefficient for the whole graph is the average,
.. math::
C = \\frac{1}{n}\\sum_{v \in G} c_v,
where :math:`n` is the number of nodes in :math:`G`.
Parameters
----------
G : graph
A networkx graph
Returns
-------
out : float
Average clustering
Examples
--------
>>> G=nx.complete_graph(5)
>>> print nx.average_clustering(G)
1.0
Notes
-----
This is a space saving routine; it might be faster
to use clustering to get a list and then take the average.
Self loops are ignored.
"""
order=G.order()
s=sum(clustering(G).values())
return s/float(order)
def clustering(G,nbunch=None,weights=False):
""" Compute the clustering coefficient for nodes.
For each node find the fraction of possible triangles that exist,
.. math::
c_v = \\frac{2 T(v)}{deg(v)(deg(v)-1)}
where :math:`T(v)` is the number of triangles through node :math:`v`.
Parameters
----------
G : graph
A networkx graph
nbunch : container of nodes, optional
Limit to specified nodes. Default is entire graph.
weights : bool, optional
If True return fraction of connected triples as dictionary
Returns
-------
out : float, dictionary or tuple of dictionaries
Clustering coefficient at specified nodes
Examples
--------
>>> G=nx.complete_graph(5)
>>> print nx.clustering(G,0)
1.0
>>> print nx.clustering(G)
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
Notes
-----
The weights are the fraction of connected triples in the graph
which include the keyed node. Ths is useful for computing
transitivity.
Self loops are ignored.
"""
if G.is_directed():
raise NetworkXError("Clustering algorithms are not defined for directed graphs.")
if weights:
clusterc={}
weights={}
for v,d,t in _triangles_and_degree_iter(G,nbunch):
weights[v]=float(d*(d-1))
if t==0:
clusterc[v]=0.0
else:
clusterc[v]=t/float(d*(d-1))
scale=1./sum(weights.itervalues())
for v,w in weights.iteritems():
weights[v]=w*scale
return clusterc,weights
clusterc={}
for v,d,t in _triangles_and_degree_iter(G,nbunch):
if t==0:
clusterc[v]=0.0
else:
clusterc[v]=t/float(d*(d-1))
if nbunch in G:
return clusterc.values()[0] # return single value
return clusterc
def transitivity(G):
"""Compute transitivity.
Finds the fraction of all possible triangles which are in fact triangles.
Possible triangles are identified by the number of "triads" (two edges
with a shared vertex).
T = 3*triangles/triads
Parameters
----------
G : graph
A networkx graph
Returns
-------
out : float
Transitivity
Examples
--------
>>> G=nx.complete_graph(5)
>>> print nx.transitivity(G)
1.0
"""
triangles=0 # 6 times number of triangles
contri=0 # 2 times number of connected triples
for v,d,t in _triangles_and_degree_iter(G):
contri += d*(d-1)
triangles += t
if triangles==0: # we had no triangles or possible triangles
return 0.0
else:
return triangles/float(contri)
|
