2011 International Symposium on Nonlinear Theory and its Applications
NOLTA2011, Kobe, Japan, September 4-7, 2011

Controlling Clustering Coeﬃcient of Graphs by Means of 2-Switch Method
Tatsuya Fukami† and Norikazu Takahashi‡†Graduate School of Information Science and Electrical Engineering, Kyushu University
744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan.
‡Faculty of Information Science and Electrical Engineering, Kyushu University
744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan.
Email: fukami@kairo.csce.kyushu-u.ac.jp, norikazu@inf.kyushu-u.ac.jp
Abstract—A clustering coeﬃcient control algorithm for
simple connected undirected graphs is studied. This algorithm is based on the 2-switch which is a well-known graphtransformation that preserves the degree of each node. We
first derive an explicit formula for the amount of change inthe clustering coeﬃcient caused by a single 2-switch. We
next show through computer simulations that the clustering coeﬃcient of scale-free graphs can be controlled over awide range by using this algorithm.
1. Introduction
It is well known that most of large complex networks
in the real world have three common properties: 1) The
average path length is short; 2) The degree distribution follows the power law; 3) The clustering coeﬃcient is high.
Watts-Strogatz (WS) model [1] and Barabási-Albert (BA)model [2] are widely known as two important models forcomplex networks, but these do not have all of the above
properties. The WS model has the first and third properties
but not the second one. On the other hand, the BA modelhas the first and second properties but not the third one.
Hence there have been many attempts to construct networkmodels having all of the three properties [3–6].
Among those attempts, we focus our attention in this paper on the 2-switch based approach [7,8]. The 2-switch is awell-known graph transformation that preserves the degreeof each node [9]. Therefore, by applying a sequence of 2switches to a graph generated by the BA model, we may
obtain a graph having all of the above-mentioned properties. Furthermore, since the amount of change in the clustering coeﬃcient caused by a single 2-switch is very small,the clustering coeﬃcient may be finely controlled.
In this paper, we first derive an explicit formula forthe amount of change in the clustering coeﬃcient caused
by a single 2-switch. We next show experimentally thatthe clustering coeﬃcient of scale-free graphs can be controlled over a wide range by using an algorithm based on
2-switches, while the average path length is kept short.

{1, 2, . . . , n} is the set of nodes and E(G) = {e1 , e2 , . . . , em }is the set of links. Each member of E(G) is an unorderedpair of distinct nodes and denoted by ek = {i, j}. Fora node i of G, the set of all nodes j such that {i, j} ∈E(G) is called the neighborhood of the node i and denoted by Ni (G). If G has three nodes i, j and k such that{{i, j}, { j, k}, {k, i}} ⊆ E(G) then we say that G has a triangle with nodes i, j and k. When we add a link {i, j} to
G = (V(G), E(G)) such that {i, j} < E(G), we express thisoperation as E(G)+{i, j}. Similarly, when we remove a link{i, j} from G = (V(G), E(G)), we express this operation as
E(G) − {i, j}. The degree vector of a graph G is defined as
K(G) = (k1 (G), k2 (G), . . . , kn (G))
where ki (G) is the degree of node i. The clustering coeﬃcient [1] of a graph G is defined as
C(G) =1 ∑Ci (G)
n i∈V(G)

where Ci (G) is the clustering coeﬃcient of node i which isdefined as{ti (G), if ki (G) ≥ 2
Ci (G) = ki (G)(ki (G)−1)/20,
if ki (G) = 0, 1
where ti (G) represents the number of unordered pairs of
nodes { j, k} such that {{i, j}, { j, k}, {k, i}} ⊆ E(G), that is, thenumber of triangles containing node i.
3. Control of Clustering Coeﬃcient
3.1. 2-Switch Method
Let us begin with the following lemma.
Lemma 1 Let G = (V(G), E(G)) be a graph having four
nodes i, j, k, l such that {i, j}, {k, l} ∈ E(G) and {i, l}, { j, k} <E(G). Let H be the graph obtained from G by removing
links {i, j} and {k, l} and adding links {i, l} and { j, k}. Then
G and H have the same degree vector.

2. Notations and Definitions
Throughout this paper, we consider only simple connected undirected graph G = (V(G), E(G)) where V(G) =It is clear from Fig. 1 that Lemma 1 holds true. The
transformation from one graph G into another graph H in
Lemma 1 is called the 2-switch in Reference [9]. So we- 64 -

1. If a ∈ Ni j (G) then G has a triangle with nodes a, i andj but H does not have this triangle.
2. If a ∈ Nkl (G) then G has a triangle with nodes a, k andl but H does not have this triangle.

G

3. If a ∈ Nil (G) then H has a triangle with nodes a, i andl but G does not have this triangle.

H

4. If a ∈ N jk (G) then H has a triangle with nodes a, j andk but G does not have this triangle.

Figure 1: 2-switch

5. If G has a triangle with nodes a, b and c such that{b, c} , {i, j}, {k, l}, {i, l}, { j, k} then H also has thistriangle because none of three links {a, b}, {b, c} and{c, a} is removed by the 2-switch. Conversely, if H
has a triangle with nodes a, b and c such that {b, c} ,{i, j}, {k, l}, {i, l}, { j, k} then G also has this triangle.

also use this terminology in the following. It is also shown
in Reference [9] that a sequence of 2-switches can transform G into H if and only if K(G) = K(H).
The amount of change in the clustering coeﬃcientcaused by a 2-switch is given in the following theorem.
Theorem 1 Let G and H be the same as in Lemma 1. Thenthe diﬀerence of the clustering coeﬃcient between G and H
is given by

From these observations, we haveta (H) − ta (G)= INil (G) (a) + IN jk (G) (a) − INi j (G) (a) − INkl (G) (a)C(H) − C(G)
(
1 ∑
1
=
n a∈N (G) ka (G)(ka (G) − 1)/2
il
∑
1
+
k
(G)(k
(G)
− 1)/2bbb∈N jk (G)
∑
1
−
k
(G)(k
(G)
− 1)/2ccc∈Ni j (G)
∑
1
−
k
(G)(k
(G)
− 1)/2ddd∈N (G)

where IA (a) is the indicator function of a subset A of V(G)defined by{
1, if a ∈ A
IA (a) =0, if a < A
Therefore, the first term of the right-hand side of (2) can betransformed as follows.
∑ta (H) − ta (G)k(G)(ka (G) − 1)/2
a∈V(G)−{i, j,k,l} a
∑
1
=
k
(G)(k
(G)
− 1)/2aa∈V(G)−{i, j,k,l} akl|Nil (G)| − |Ni j (G)|
|Nk j (G)| − |Ni j (G)|+ki (G)(ki (G) − 1)/2 k j (G)(k j (G) − 1)/2)
|Nk j (G)| − |Nkl (G)|
|Nil (G)| − |Nkl (G)|++(1)
kk (G)(kk (G) − 1)/2 kl (G)(kl (G) − 1)/2+

where Ni j (G) = (Ni (G) ∩ N j (G)) ∩ (V(G) − {i, j, k, l}) andN jk (G), Nkl (G), Nil (G) are defined similarly.

=+a∈N jk (G)

−

n

=
=

ka (G)(ka (G) − 1)/2∑
1a∈Nil (G)Proof: By the definition of the clustering coeﬃcient andLemma 1, we haven1∑
C(H) − C(G) =(Ca (H) − Ca (G))
n a=1
1 ∑ ta (H) − ta (G)n a=1 ka (G)(ka (G) − 1)/2(∑
1
ta (H) − ta (G)×(INil (G) (a) + IN jk (G) (a) − INi j (G) (a) − INkl (G) (a))
∑
1

−

∑

1
k
(G)(k
(G)
− 1)/2aa∈Ni j (G) a∑1a∈Nkl (G)n a∈V(G)−{i, j,k,l} ka (G)(ka (G) − 1)/2)∑
ta (H) − ta (G)(2)+
k (G)(ka (G) − 1)/2a∈{i, j,k,l} a

We first investigate the first term of (2) in more detail. Let abe any node other than i, j, k and l. Then we easily observethat the following statements hold true.

ka (G)(ka (G) − 1)/2

ka (G)(ka (G) − 1)/2

Let us next consider the second term of (2). In the following, we deal only with the case where a = i because theremaining cases are similar. Since neither G nor H contains the triangle with nodes i, j and l, all triangles in G and
H containing node i are divided into three disjoint classes:
1) Node j is contained; 2) Node l is contained; 3) Neither
node j nor node l is contained. For these classes of triangles, the following statements hold true.

- 65 -

1. G has a triangle with nodes i, j and c if and only if c ∈Ni j (G), while H does not have such triangles because{i, j} < E(H).

1: Set G 0 to G

2. H has a triangle with nodes i, l and c if and only if c ∈Nil (G), while G does not have such triangles because{i, l} < E(G).

if {i, j}, {k, l} ∈ E(Gt ) and {i, l}, { j, k} < E(Gt ) thenif D(i, j,k,l) (Gt ) > 0 then7:
Apply 2-switch to Gt and let the obtained graphbe denoted by Gt+1
8:
Add 1 to t
9:Reset (i, j, k, l) to (1, 2, 3, 4)
10:
else
11:
Update (i, j, k, l)
12:
end if13:
end if
14: end while
15: return G t and C(G t )3. If G has a triangle with nodes i, b and c such thatj < {b, c} and l < {b, c} then H also has this triangle because none of three links {i, b}, {b, c} and {c, i}
is removed by the 2-switch. Conversely, if H has atriangle with nodes i, b and c such that j < {b, c} andl < {b, c} then G also has this triangle.
From these observations, we haveti (H) − ti (G) = |Nil | − |Ni j |which completes the proof for the case where a = i.

2: Initialize t to 0
3: Initialize (i, j, k, l) to (1, 2, 3, 4)
4: while (i, j, k, l) , (n − 2, n − 1, n, n + 1) do

5:
6:

□

Figure 2: Algorithm for constructing a graph that has thesame degree vector as G and a high clustering coeﬃcient.

By applying a sequence of 2-switches to a graph, we canfinely control the clustering coeﬃcient while keeping thedegree vector unchanged. To be more specific, if we repeat
two operations: 1) selecting four nodes i, j, k, l such thatthe right-hand side of (1) is positive (negative, resp.) and2) applying a 2-switch to the selected four nodes then theclustering coeﬃcient increases (decreases, resp.) gradually.
In addition, by using Theorem 1, it is easy to check whether
there exists a 2-switch that can increase (or decrease) theclustering coeﬃcient of a graph.
The idea of using 2-switches to control the clustering coeﬃcient of graphs is not new (see, for example, [7] and [8]).
However, to the best of the authors’ knowledge, Theorem 1
is the first to provide an explicit formula for the amount ofchange in the clustering coeﬃcient caused by a 2-switch.
In order to confirm the eﬀectiveness of Theorem 1, weshow that graphs such that not only they have the scale-freeproperty but also their clustering coeﬃcients are as high (orlow) as possible can be generated by using 2-switches. A
simple algorithm for constructing such a graph is shownin Fig. 2 where G, the input to the algorithm, is assumed
to be a graph generated by the BA model and D(i, j,k,l) (G)represents the right-hand side of (1). It is important to notethat this algorithm terminates if and only if there is no 2switch to increase the clustering coeﬃcient of Gt .
We first applied our algorithm to small graphs with 10
nodes generated by the BA model. Some of the results areshown in Fig. 3. Although it is diﬃcult to perceive the difference between the initial and final graphs, the clustering
coeﬃcient is certainly increased by the algorithm to about
0.8 in all cases. We next applied our algorithm to larger
graphs with sizes ranging from 50 to 250 nodes. The results
are summarized in Fig. 4 where the horizontal axis represents the number of nodes, the vertical axis represents theclustering coeﬃcient, and ∆m is the number of links connecting a new node to the existing nodes in the BA model.

For each value of n ∈ {50, 60, . . . , 250} and ∆m ∈ {2, 3, 4},
the average of ten results is plotted in the graph. We see
from Fig. 4 that the clustering coeﬃcient of the final graphis about 0.8 in all cases, while the clustering coeﬃcient of
the initial graph is between 0.07 and 0.28. Since the amountof change in the clustering coeﬃcient caused by a single 2switch is very small, this result means that a sequence of2-switches can control the clustering coeﬃcient of scalefree graphs over a wide range.
Finally, we investigated the eﬀect of our algorithm on the
average path length. The results are shown in Fig. 5 where
the horizontal axis represents the number of nodes and thevertical axis represents the average path length. From theseresults, we see that the average path length is increased by
our algorithm but still low.
By using 2-switches, we can also decrease the clustering coeﬃcient while keeping the degree vector unchanged.
In order to verify the eﬀectiveness of this approach, we applied an algorithm similar to the one in Fig. 2 to graphs withsizes ranging from 50 to 250 generated by the BA model.
We then observed that the clustering coeﬃcient of the generated graph was exactly or nearly zero in all cases.

3.2. Algorithm for Controlling Clustering Coeﬃcient4. Conclusions
We have studied a 2-switch based clustering coeﬃcient
control algorithm for undirected graphs. We first derived an
explicit formula for the amount of change in the clustering
coeﬃcient caused by a single 2-switch. We next applied thealgorithm to graphs generated by the BA model with sizes
ranging from 50 to 250 nodes. Experimental results showthat the clustering coeﬃcient can be finely controlled over awide range between about 0 and 0.8, while the average path
length is kept short. This means that the 2-switch basedalgorithm is a useful tool for constructing graphs having- 66 -

(a)

1.0
0.8
0.6
0.4
0.0

clustering coefficientdelta m=2
delta m=3
delta m=4

0.2

1.0
0.8
0.6
0.4
0.2
0.0

clustering coefficientdelta m=2
delta m=3
delta m=4

50

100

150

200

250

50

the number of nodes

100

150

200

250

the number of nodes

(a)

(b)

8
6
4

average path length

0
50

100

150

200

the number of nodes

Figure 3: Results of the application of our algorithm tosmall graphs. The initial and final graphs are shown at left
and right, respectively. The clustering coeﬃcients are (a)0.453333 (left) and 0.793333 (right), (b) 0.618333 (left)
and 0.801667 (right), (c) 0.694524 (left) and 0.790714(right).

delta m=2
delta m=3
delta m=4

2

8
6
4
0

(c)

delta m=2
delta m=3
delta m=42

average path length

10

(b)

10

Figure 4: Results of the application of our algorithm tolarger graphs. (a) Clustering coeﬃcients of initial graphgenerated by the BA model. (b) Clustering coeﬃcient of
the final graph.

(a)

250

50

100

150

200

250

the number of nodes(b)

Figure 5: Eﬀect of our algorithm on the average path
length. (a) Average path length of the initial graph. (b)Average path length of the final graph.
[5] K. Klemm and V. M. Eguiluz, “Growing scale-free
networks with small-world behavior,” Physical Review
E, vol. 65, no. 5, 57102, 2002.

the three properties mentioned in Section 1.
Acknowledgments
This work was supported by KAKENHI 21560068.
References[1] D. J. Watts and S. H. Strogatz, “Collective dynamics
of ‘small-world’ networks,” Nature, vol. 393, pp. 440–
442, 1998.
[2] A.-L. Barabási and R. Albert, “Emergence of scaling
in random networks,” Science, vol. 286, pp. 509–512,
1999.
[3] P. Holme and B. J. Kim, “Growing scale-free networks
with tunable clustering,” Physical Review E, vol. 65,
no. 2, 26107, 2002.
[4] K. Klemm and V. M. Eguiluz, “Highly clustered scalefree networks,” Physical Review E, vol. 65, no. 3,36123, 2002.

[6] W. M. Tam, F. C. M. Lau, and C. K. Tse, “Construction of scale-free networks with adjustable clustering,”
in Proceedings of 2008 International Symposium on
Nonlinear Theory and its Applications, pp. 257–260,
September 2008.
[7] S. Maslov and K. Sneppen, “Specificity and stability
in topology of protein networks,” Science, vol. 296,
pp. 910–913, May 2002.
[8] B. J. Kim, “Performance of networks of artificial neurons: The role of clustering,” Physical Review E,
vol. 69, no. 4, 045101, April 2004.
[9] S. Bereg and H. Ito, “Transforming graphs with thesame degree sequence,” in Computational Geometry
and Graph Theory, H. Ito, M. Kano, N. Katoh, and
Y. Uno, Eds., vol. 4535 of Lecture Notes in Computer
Science, pp. 25–32. Springer Berlin / Heidelberg, 2008.

- 67 -