# Influence of Dynamical Change of Edges on Clustering Coefficients

Authors: Yuhong Ruan; Anwei Li
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Clustering coefficient is a very important measurement in complex networks, and it describes the average ratio between the actual existent edges and probable existent edges in the neighbor of one vertex in a complex network. Besides, in a complex networks, the dynamic change of edges can trigger directly the evolution of network and further affect the clustering coefficients. As a result, in this paper, we investigate the effects of the dynamic change of edge on the clustering coefficients. It is illustrated that the increase and decrease of the clustering coefficient can be effectively controlled by adding or deleting several edges of the network in the evolution of complex networks.


---

## Body

## 1. Introduction

Clustering coefficient is one of the most important quantities in complex networks which can depict the average number of the ratio of the actual existence sides of the neighbors of the point and the sides that may exist in the neighbors of the point in the complex networks. At present, there are two different but the most basic definitions of clustering coefficients. Firstly, Watts and Strogatz proposed the concept of the clustering coefficients in their creative small-world network model which is denoted byC [1]. Secondly, shortly after Watts and Strogatz proposed the clustering coefficients, Newman et al. defined a concept similar to the former “transitivity,” which is denoted by C
∗ [2].Although the clustering coefficients is widely used in the study of complex networks, scholars do not have clustering coefficients discontinuous [3–19]. Shi et al. made a good overview on the research in this area and proposed a general method of calculating the clustering coefficients [20]. Soffer and Vazquez proposed a definition of clustering coefficients independent of degree [21].In the complex networks, dynamic change of the edges directly led to the dynamic evolution of the network and thus affect the variation of the clustering coefficients. And one of the core features of complex networks is a huge number of nodes and edges. This feature directly affects the complexity of calculating the clustering coefficient. In this paper, how dynamical changes of the edges affect the clustering coefficient is deeply presented which can reveal the impact of changes of the edge in the quality and quantity on the clustering coefficients. In addition, the obtained results show that, in the evolution of complex networks, we can make the clustering coefficients increase or decrease by deleting or adding the certain edges of networks.


## 2. Basic Concepts

For a given complex network,A
=
(
a
i
j
) denotes the adjacency matrix of the network, |
V
| denotes the number of nodes in the network, k
(
r
) denotes the degree of node r, N
G
(
r
) denotes the set of neighbors of node r, E
(
r
) denotes the number of edges in the neighbors N
G
(
r
) of node r, and C
(
r
) denotes the clustering coefficient of node r; namely,(1)
C
r
=
2
E
r
k
r
k
r
-
1
,with global clustering coefficient:(2)
C
=
∑
r
=
1
|
V
|
C
r
|
V
|
.As a special case, ifk
(
r
)
=
1
(
r
=
1,2
,
…
,
|
V
|
), then C
(
r
)
=
1.For sake of description, we define a set△
(
i
,
j
)
=
{
r
∣
a
i
j
a
r
i
a
r
j
=
1
} by the adjacency matrix A
=
(
a
i
j
)
|
V
|
×
|
V
| of the network. The set is used to describe a set of triangles with a shared edge e
i
j. And we use the △
(
i
,
j
) to denote the number of these triangles. In fact, when the edge e
i
j exists, △
(
i
,
j
) is equal to the number of nodes in N
G
(
i
)
∩
N
G
(
j
). We show an example in Figure 1.Figure 1
The dashed line represents the triangles with a shared edgee
i
j and △
(
i
,
j
)
=
3.


## 3. Effect of Edge Changes on the Clustering Coefficients

### 3.1. Effect of Deleting an Edge on the Clustering Coefficients

In this paper, we do not consider deleting the associated edge of suspension node. One edgee
i
j of network is deleted, k
(
i
), k
(
j
), N
G
(
i
), and N
G
(
j
) will certainly change, and △
i
,
j may change. These factors that are intertwined directly affect the change of C
(
i
), C
(
j
) and then affect the change of the complex network clustering coefficient C.Case 1 (k
(
i
)
≥
3 and k
(
j
)
≥
3).
(1) After the edgee
i
j is deleted, the triangles that contained the shared edge e
i
j turn to trielements because of losing side e
i
j, but k
r
(
r
∈
△
(
i
,
j
)
) does not change. As a result, the changing amount of C
(
r
)
(
r
∈
△
(
i
,
j
)
) is(3)
△
C
r
=
2
E
r
-
1
k
r
k
r
-
1
-
2
E
r
k
r
k
r
-
1
=
-
2
k
r
k
r
-
1
,
r
∈
△
i
,
j
.
(2)N
G
i turns to N
G
′
i, j
∉
N
G
′
i. k
i turns to k
′
i
=
k
i
-
1. In addition, the triangles which contained the shared edge e
i
j turn to trimer because of losing side e
i
j. Therefore, the number of the edges of neighbors N
G
′
i of node i reduces |
△
|
i
,
j, C
i turns to C
′
i, and the amount of change is denoted by △
C
(
i
). As a result, we have the following expressions:(4)
C
′
i
=
2
E
i
-
△
i
,
j
k
i
-
1
k
i
-
2
,
△
C
i
=
△
C
′
i
-
C
i
hiiiiii
=
2
E
i
-
△
i
,
j
k
i
-
1
k
i
-
2
-
E
i
k
i
k
i
-
1
hiiiiii
=
2
k
i
△
i
,
j
k
i
k
i
-
1
2
E
i
k
i
k
i
-
1
mmiiimmmm
-
k
i
△
i
,
j
k
i
k
i
-
1
mmmmiiimm
×
k
i
-
2
-
1
k
i
△
i
,
j
k
i
k
i
-
1
hiiiiiii
=
2
k
i
-
2
C
i
-
△
i
,
j
k
i
-
1
.Similarly,C
(
j
) turns to C
′
(
j
), and the amount of change is denoted by △
C
(
j
) with(5)
△
C
j
=
C
′
j
-
C
j
=
2
k
j
-
2
C
j
-
△
i
,
j
k
j
-
1
.As mentioned above, whene
i
j is a edge of the complex networks with k
(
i
)
⩾
3 and k
j
⩾
3, deleting edge e
i
j will lead to the change amount of the network clustering coefficient C which is denoted by △
C:(6)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
C
i
-
△
i
,
j
/
(
k
i
-
1
)
k
i
-
2
hhhhh
h
+
C
j
-
△
i
,
j
/
(
k
j
-
1
)
k
j
-
2
hhhihhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 2 (k
(
i
)
=
2 and k
(
j
)
⩾
3).
Consider the following:(7)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
1
-
C
i
2
+
C
j
-
△
i
,
j
/
(
k
j
-
1
)
k
j
-
2
hhhhhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 3 (k
(
i
)
≥
3 and k
(
j
)
=
2).
Consider the following:(8)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
C
i
-
△
i
,
j
/
k
i
-
1
k
i
-
2
+
1
-
C
j
2
hhhhhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 4 (k
(
i
)
=
2 and k
(
j
)
=
2).
Consider the following:(9)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
1
-
C
i
2
+
1
-
C
j
2
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.


### 3.2. Effect of Adding an Edge on the Clustering Coefficients

If edgee
i
j is added, clustering coefficient C
r
(
r
∈
△
(
i
,
j
)
), C
(
i
), and C
(
j
) will change.In this case, we just considerk
(
i
)
≥
2 and k
(
j
)
≥
2.(1)
The changing amount ofC
(
r
) is as follows: (10)
△
C
r
=
2
k
r
k
r
-
1
,
r
∈
△
i
,
j
.
(2)
N
G
(
i
) turns into N
G
′
(
i
), j
∈
N
G
′
(
i
). k
(
i
) turn into k
′
(
i
)
=
k
(
i
)
+
1. Without loss of generality, we assume that the former trielements turn into triangle because of adding edge e
i
j. Therefore, the number of the edges among the neighbors of node i increases △
(
i
,
j
). The above reasons make C
(
i
) turn into C
′
(
i
) and the changing amount is denoted by △
C
(
i
). As a result, we have the following expressions:(11)
C
′
i
=
2
E
r
+
△
i
,
j
k
i
k
i
+
1
,with(12)
△
C
i
=
C
′
i
-
C
i
=
2
E
i
+
△
i
,
j
k
i
k
i
+
1
-
2
E
i
k
i
k
i
-
1
=
2
k
i
△
i
,
j
k
i
k
i
-
1
-
4
E
i
k
i
k
i
-
1
i
×
k
i
+
1
-
1
=
2
k
i
+
1
△
i
,
j
k
i
-
1
-
C
i
.Similarly,C
(
j
) turns into C
′
(
j
), and the changing amount is denoted by △
C
(
j
) with(13)
C
′
j
=
2
E
j
+
△
i
,
j
k
j
k
j
+
1
,
△
C
j
=
C
′
j
-
C
j
,
=
2
k
j
+
1
△
i
,
j
k
j
-
1
-
C
j
.After adding an edgee
i
j into the network, the changing amount of the clustering coefficients C of the network is △
C with (14)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
△
i
,
j
/
k
i
-
1
-
C
i
k
i
+
1
hhhhhh
+
△
i
,
j
/
(
k
j
-
1
)
-
C
j
k
j
+
1
hhhhhhi
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.From the above analysis, one can see that, by adding or deleting an edge in the complex networks, the clustering coefficients of the complex networks may change. If we continue in-depth to analysis the above conclusions under the premise without destroying network connectivity, the following conclusions can be clearly gained.Theorem 1.
Deleting (adding) the edgee
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network increases (decreases).Proof.
If the edgee
i
j does not constitute a triangle with any nodes in the network, then (15)
△
C
r
=
-
2
k
r
k
r
-
1
=
0
,
△
i
,
j
=
0
.
Based on the above analysis, ifk
(
i
)
=
2, then △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
1
-
0
=
1; if k
(
i
)
≥
3, then △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
2
C
(
i
)
[
|
V
|
(
k
(
i
)
-
2
)
]
-
1. That is to say that deleting the edge e
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network increases.
Similarly, based on formula (13), adding the edge e
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network decreases.Theorem 2.
IfC
(
i
)
≥
(
△
i
,
j
/
k
i
-
1
), then △
C
(
i
)
≥
0 after the edge e
i
j was deleted.Proof.
Whenk
(
i
)
=
2, if △
(
i
,
j
)
=
0, by Theorem 1, △
C
(
i
)
≥
0; if △
(
i
,
j
)
=
1, after the edge e
i
j was deleted, C
(
i
)
=
1, △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
1
-
1
=
0, and △
C
(
i
)
≥
0.
Whenk
(
i
)
≥
3,(16)
△
C
i
=
C
′
i
-
C
i
=
2
C
(
i
)
-
△
i
,
j
/
(
k
i
-
1
)
k
i
-
2
.Obviously, if C
(
i
)
≥
△
i
,
j
/
k
i
-
1, then △
C
(
i
)
≥
0.Corollary 3.
IfC
(
i
)
<
(
△
i
,
j
/
(
k
(
i
)
-
1
)
), then △
C
(
i
)
≤
0 if edge e
i
j is deleted.
IfC
(
i
)
<
(
△
i
,
j
/
(
k
i
-
1
)
), then △
(
i
,
j
)
≠
0 or k
(
i
)
=
1 (do not consider this case). When △
(
i
,
j
)
≠
0, as k
(
i
)
=
2, after the edge e
i
j was deleted, △
C
(
i
)
≥
0.
It is obtained directly from formula (13).Corollary 4.
IfC
(
i
)
>
(
△
i
,
j
/
(
k
i
-
1
)
), then △
C
(
i
)
<
0 if the edge e
i
j is added.


## 3.1. Effect of Deleting an Edge on the Clustering Coefficients

In this paper, we do not consider deleting the associated edge of suspension node. One edgee
i
j of network is deleted, k
(
i
), k
(
j
), N
G
(
i
), and N
G
(
j
) will certainly change, and △
i
,
j may change. These factors that are intertwined directly affect the change of C
(
i
), C
(
j
) and then affect the change of the complex network clustering coefficient C.Case 1 (k
(
i
)
≥
3 and k
(
j
)
≥
3).
(1) After the edgee
i
j is deleted, the triangles that contained the shared edge e
i
j turn to trielements because of losing side e
i
j, but k
r
(
r
∈
△
(
i
,
j
)
) does not change. As a result, the changing amount of C
(
r
)
(
r
∈
△
(
i
,
j
)
) is(3)
△
C
r
=
2
E
r
-
1
k
r
k
r
-
1
-
2
E
r
k
r
k
r
-
1
=
-
2
k
r
k
r
-
1
,
r
∈
△
i
,
j
.
(2)N
G
i turns to N
G
′
i, j
∉
N
G
′
i. k
i turns to k
′
i
=
k
i
-
1. In addition, the triangles which contained the shared edge e
i
j turn to trimer because of losing side e
i
j. Therefore, the number of the edges of neighbors N
G
′
i of node i reduces |
△
|
i
,
j, C
i turns to C
′
i, and the amount of change is denoted by △
C
(
i
). As a result, we have the following expressions:(4)
C
′
i
=
2
E
i
-
△
i
,
j
k
i
-
1
k
i
-
2
,
△
C
i
=
△
C
′
i
-
C
i
hiiiiii
=
2
E
i
-
△
i
,
j
k
i
-
1
k
i
-
2
-
E
i
k
i
k
i
-
1
hiiiiii
=
2
k
i
△
i
,
j
k
i
k
i
-
1
2
E
i
k
i
k
i
-
1
mmiiimmmm
-
k
i
△
i
,
j
k
i
k
i
-
1
mmmmiiimm
×
k
i
-
2
-
1
k
i
△
i
,
j
k
i
k
i
-
1
hiiiiiii
=
2
k
i
-
2
C
i
-
△
i
,
j
k
i
-
1
.Similarly,C
(
j
) turns to C
′
(
j
), and the amount of change is denoted by △
C
(
j
) with(5)
△
C
j
=
C
′
j
-
C
j
=
2
k
j
-
2
C
j
-
△
i
,
j
k
j
-
1
.As mentioned above, whene
i
j is a edge of the complex networks with k
(
i
)
⩾
3 and k
j
⩾
3, deleting edge e
i
j will lead to the change amount of the network clustering coefficient C which is denoted by △
C:(6)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
C
i
-
△
i
,
j
/
(
k
i
-
1
)
k
i
-
2
hhhhh
h
+
C
j
-
△
i
,
j
/
(
k
j
-
1
)
k
j
-
2
hhhihhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 2 (k
(
i
)
=
2 and k
(
j
)
⩾
3).
Consider the following:(7)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
1
-
C
i
2
+
C
j
-
△
i
,
j
/
(
k
j
-
1
)
k
j
-
2
hhhhhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 3 (k
(
i
)
≥
3 and k
(
j
)
=
2).
Consider the following:(8)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
C
i
-
△
i
,
j
/
k
i
-
1
k
i
-
2
+
1
-
C
j
2
hhhhhh
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.Case 4 (k
(
i
)
=
2 and k
(
j
)
=
2).
Consider the following:(9)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
1
-
C
i
2
+
1
-
C
j
2
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.


## 3.2. Effect of Adding an Edge on the Clustering Coefficients

If edgee
i
j is added, clustering coefficient C
r
(
r
∈
△
(
i
,
j
)
), C
(
i
), and C
(
j
) will change.In this case, we just considerk
(
i
)
≥
2 and k
(
j
)
≥
2.(1)
The changing amount ofC
(
r
) is as follows: (10)
△
C
r
=
2
k
r
k
r
-
1
,
r
∈
△
i
,
j
.
(2)
N
G
(
i
) turns into N
G
′
(
i
), j
∈
N
G
′
(
i
). k
(
i
) turn into k
′
(
i
)
=
k
(
i
)
+
1. Without loss of generality, we assume that the former trielements turn into triangle because of adding edge e
i
j. Therefore, the number of the edges among the neighbors of node i increases △
(
i
,
j
). The above reasons make C
(
i
) turn into C
′
(
i
) and the changing amount is denoted by △
C
(
i
). As a result, we have the following expressions:(11)
C
′
i
=
2
E
r
+
△
i
,
j
k
i
k
i
+
1
,with(12)
△
C
i
=
C
′
i
-
C
i
=
2
E
i
+
△
i
,
j
k
i
k
i
+
1
-
2
E
i
k
i
k
i
-
1
=
2
k
i
△
i
,
j
k
i
k
i
-
1
-
4
E
i
k
i
k
i
-
1
i
×
k
i
+
1
-
1
=
2
k
i
+
1
△
i
,
j
k
i
-
1
-
C
i
.Similarly,C
(
j
) turns into C
′
(
j
), and the changing amount is denoted by △
C
(
j
) with(13)
C
′
j
=
2
E
j
+
△
i
,
j
k
j
k
j
+
1
,
△
C
j
=
C
′
j
-
C
j
,
=
2
k
j
+
1
△
i
,
j
k
j
-
1
-
C
j
.After adding an edgee
i
j into the network, the changing amount of the clustering coefficients C of the network is △
C with (14)
△
C
=
△
C
i
+
△
C
j
+
∑
r
∈
△
i
,
j
△
C
r
V
=
2
V
∑
r
∈
△
i
,
j
‍
△
i
,
j
/
k
i
-
1
-
C
i
k
i
+
1
hhhhhh
+
△
i
,
j
/
(
k
j
-
1
)
-
C
j
k
j
+
1
hhhhhhi
-
∑
r
∈
△
i
,
j
‍
1
k
r
k
r
-
1
.From the above analysis, one can see that, by adding or deleting an edge in the complex networks, the clustering coefficients of the complex networks may change. If we continue in-depth to analysis the above conclusions under the premise without destroying network connectivity, the following conclusions can be clearly gained.Theorem 1.
Deleting (adding) the edgee
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network increases (decreases).Proof.
If the edgee
i
j does not constitute a triangle with any nodes in the network, then (15)
△
C
r
=
-
2
k
r
k
r
-
1
=
0
,
△
i
,
j
=
0
.
Based on the above analysis, ifk
(
i
)
=
2, then △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
1
-
0
=
1; if k
(
i
)
≥
3, then △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
2
C
(
i
)
[
|
V
|
(
k
(
i
)
-
2
)
]
-
1. That is to say that deleting the edge e
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network increases.
Similarly, based on formula (13), adding the edge e
i
j does not constitute a triangle with any nodes in the network, and the clustering coefficient of the network decreases.Theorem 2.
IfC
(
i
)
≥
(
△
i
,
j
/
k
i
-
1
), then △
C
(
i
)
≥
0 after the edge e
i
j was deleted.Proof.
Whenk
(
i
)
=
2, if △
(
i
,
j
)
=
0, by Theorem 1, △
C
(
i
)
≥
0; if △
(
i
,
j
)
=
1, after the edge e
i
j was deleted, C
(
i
)
=
1, △
C
(
i
)
=
C
′
(
i
)
-
C
(
i
)
=
1
-
1
=
0, and △
C
(
i
)
≥
0.
Whenk
(
i
)
≥
3,(16)
△
C
i
=
C
′
i
-
C
i
=
2
C
(
i
)
-
△
i
,
j
/
(
k
i
-
1
)
k
i
-
2
.Obviously, if C
(
i
)
≥
△
i
,
j
/
k
i
-
1, then △
C
(
i
)
≥
0.Corollary 3.
IfC
(
i
)
<
(
△
i
,
j
/
(
k
(
i
)
-
1
)
), then △
C
(
i
)
≤
0 if edge e
i
j is deleted.
IfC
(
i
)
<
(
△
i
,
j
/
(
k
i
-
1
)
), then △
(
i
,
j
)
≠
0 or k
(
i
)
=
1 (do not consider this case). When △
(
i
,
j
)
≠
0, as k
(
i
)
=
2, after the edge e
i
j was deleted, △
C
(
i
)
≥
0.
It is obtained directly from formula (13).Corollary 4.
IfC
(
i
)
>
(
△
i
,
j
/
(
k
i
-
1
)
), then △
C
(
i
)
<
0 if the edge e
i
j is added.


## 4. Discussion and Conclusion

In this paper, we present a systematic study on the effects of dynamic change of edges on clustering coefficients. It was found that the increase and decrease of the clustering coefficient can be effectively characterized by adding or deleting some edges of the network in the evolution of complex networks.For the adaptive network, the susceptible may keep away from the infective for the reason that the susceptible individuals have the ability to recognize the infective group and avoid connecting with them [22]. In this case, the susceptible will delete or add some edges in the complex networks. That is to say that our results can be extended to the disease transmission on complex networks [23–25].



---

*Source: 172720-2015-05-14.xml*