## Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient

| Ting Li      | Xianshi Yu             | Bing-Yi Jing   |
|--------------|------------------------|----------------|
| HKUST        | University of Michigan | HKUST          |
| tlial@ust.hk | xsyu@umich.edu         | majing@ust.hk  |

## Abstract

In this paper, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications.

## 1 Introduction

Nowadays, complex networks are ubiquitous in the real world. Network summary statistics have been widely used in experimental and empirical studies. Some of these are model-free such as network size, density, average shortest path and so on. Some are related to generative models' parameters, for instance, the number of blocks for the stochastic block model (SBM)([11]).

Many real-world networks show properties of small-world networks ([28]) as their neighborhood connectivity is higher than that in comparable random networks. To measure the clustering strength, the clustering coefficient is proposed in graph theory. Two versions of the measure exist: the global one and the local one. The global clustering coefficient was proposed in [21] and is

$$\overset { \sim } { c } = \frac { \overset { \sim } { \sim } } { 3 \times \text{number of triangles} }. \quad \ \ \ \ ( 1 )$$

It was extended to weighted networks by [23]. The local clustering coefficient was introduced by [28] and generalized to weighted, directed, and bipartite graphs ([3], [17], [6]).

However, the clustering coefficient is not without problems. For example, under the degree corrected block model (DCBM), ˆ cc not only tends to 0 when the network is large and sparse, but also involves noise from degree heterogeneity (more details in Section 2 below). To overcome these issues, we propose a so-called normalized clustering coefficient:

$$\hat { \rho } = \frac { \hat { T } \hat { E } ^ { 3 } } { \hat { V } ^ { 3 } },$$

where ˆ T , ˆ V and ˆ E are the ratios of the number of triangles ( ), triplets ( ) and edges ( ) in the network to the total number of potential connections respectively. The normalization makes the new indicator, unlike the clustering coefficient, robust to network size, network density and degree heterogeneity. Moreover, the normalized clustering coefficient reflects the "in-out-ratio" of the DCBM. In our simulations and empirical studies, the new measure out performs the clustering coefficient in networks clustering and dynamic network analysis. It is also a good criteria on measuring the quality of sub-networks in network sampling.

In related work, [8] and [13] proposed similar statistics for testing the existence of communities structure based on small subgraphs. Partly inspired by [8] and [13], we investigate the clustering strength of the network through three-node subgraphs, which has a quite different motivation from former works.

More precisely, we make contributions as follows:

- · A novel statistic that is robust to network size, network density and degree heterogeneity is proposed to measure the clustering strength of networks.
- · The normalized clustering coefficient has nice statistical properties under different popular network generative models.
- · Both simulations and real data analysis show that the normalized clustering coefficient can be applied for networks clustering, network sampling and dynamic network analysis.

The rest of the paper is organized as follows. We introduce the normalized clustering coefficient in detail and analyze its properties under different network generative models in Section 2. In Section 3, we describe the applications of the normalized clustering coefficient in networks clustering, network sampling and dynamic networks analysis. We make conclusion in Section 4. Technical proofs of the mathematical results, additional simulations and more details of the real data are given in Appendix.

## 2 The normalized clustering coefficient

/negationslash

Let G V,E ( ) denote a network with node set V and edge set E. Let | V | = N. For any i, j ∈ { 1 2 , , . . . , N } and i = j , let A i,j = 1 if there is an edge between node i and node j ; otherwise, A i,j = 0 . Set A i,i = 0 for all i ∈ { 1 2 , , . . . , N } . The normalized clustering coefficient is defined as

$$\hat { \rho } = \frac { \hat { T } \hat { E } ^ { 3 } } { \hat { V } ^ { 3 } },$$

where ˆ = E ( N 2 ) -1 ∑ 1 ≤ ≤ ≤ i j N A i,j , ˆ = V ( N 3 ) -1 ∑ 1 ≤ ≤ ≤ ≤ i j k N ( A i,j A i,k + A j,i A j,k + A k,i A k,j ) / 3 and ˆ = T ( N 3 ) -1 ∑ 1 ≤ ≤ ≤ ≤ i j k N A i,j A j,k A k,i . Using the adjacency matrix A , the normalized clustering coefficient can be rewritten as

$$\hat { \rho } = \frac { ( N - 2 ) ^ { 2 } t r ( A ^ { 3 } ) ( \mathbf 1 ^ { \prime } A \mathbf 1 ) ^ { 3 } } { N ( N - 1 ) ( \mathbf 1 ^ { \prime } A ^ { 2 } \mathbf 1 - t r ( A ^ { 2 } ) ) ^ { 3 } }, \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \end{array}$$

where tr () denotes the trace of the matrix and 1 is the all-one vector. This is the form we use in simulations and empirical studies.

The computational complexity of the normalized clustering coefficient, which is mainly from counting triangles, is O Nd ( 2 ) ([26]), where d is the maximum degree in the network. Since many networks in the real world are sparse where d /lessmuch N , the complexity is modest. Furthermore, the counting of triangles and triplets can be achieved through parallel computation using the edge list, which will significantly increase the computing efficiency.

Unlike the clustering coefficient, the normalized clustering coefficient involves the number of edges and utilizes the cubic of ˆ E/V ˆ to perform normalization. The proposed indicator has nice properties under some of the popular network generative models.

## 2.1 Under the Erdös-Rényi model

Under the Erdös-Rényi model with link probability p, the clustering coefficient ˆ cc → 3 p, and the normalized clustering coefficient ˆ ρ → 1 . The clustering coefficient was proposed to measure the degree to which nodes that share a common neighbor tend to have links. However, the Erdös-Rényi model assumes links appear independently, so the number of common neighbors will not change the probability that two nodes are connected. In this sense, it is more natural to conclude that the strength of this kind of connection is 1, as the normalized clustering coefficient does.

## 2.2 Under the DCBM

We first give a brief introduction of the DCBM. Then, we show that the clustering coefficient is not a proper measure while the normalized clustering coefficient has nice properties under the DCBM.

In the real world, there are various sources of community structures in networks. In social networks, there are families, work and friendship circles, interest groups, universities, and companies. In protein interaction networks, proteins are often grouped according to their functions within the cells. Furthermore, nodes in real networks often show degree heterogeneity even when they are in the same community. In order to accommodate community structure as well as degree heterogeneity in networks, [15] proposed the degree-corrected stochastic block model (DCBM). The theoretical properties of DCBM have been studied for community detection, including but not limited to [12, 19, 30, 9].

/negationslash

/negationslash

/negationslash

The DCBM can be described as follows: given a network G generated from the DCBM, each node i ∈ { 1 , . . . , N } is assigned a class label z i ∈ { 1 , . . . , K } where z i ∼ Multinomial ( ·| π ) and π = ( π , ..., π 1 K ) with ∑ K i =1 π i = 1 . The adjacent matrix A = { A i,j } n × n is defined by A i,j ∼ Bernoulli ( ·| θ θ B i j z ,z i j ) for i = j, and A i,i = 0 for all i ∈ { 1 2 , , . . . , N } , where { θ i : i = 1 , . . . , N } are non-negative degree-correction parameters, and B is the K × K symmetric probability matrix. In general, we only require min { B i,i } &gt; max { B i,j } , where i, j ∈ { 1 2 , , . . . , K } and i = j. However, in the following discussion, we reduce the parameter domain to B i,i = p &gt; q = B i,j , for all i, j ∈ { 1 2 , , . . . , K } and i = j. We also set π i = 1 K for all i ∈ { 1 2 , , . . . , K } . Without loss of generality, we further assume the constraint E ( θ 2 ) = 1 .

Now, we demonstrate that the clustering coefficient is not an appropriate measure under the DCBM framework. Let E = P ( A i,j = 1) , V = P ( A i,j A i,k = 1) and T = P ( A i,j A j,k A k,i = 1) . Then, under the DCBM, we have

$$E \ & = \ ( \mathbb { E } ( \theta ) ) ^ { 2 } \left ( \frac { p } { K } + \frac { ( K - 1 ) q } { K } \right ), \\ V \ & = \ ( \mathbb { E } ( \theta ) ) ^ { 2 } \left ( \frac { p } { \text{--} } + \frac { ( K - 1 ) q } { \text{--} } \right ) ^ { 2 }.$$

$$T \ = \ \frac { p ^ { 3 } } { K ^ { 2 } } + \frac { \stackrel { \cdots } { 3 ( K - 1 ) p q ^ { 2 } } } { K ^ { 2 } } + \frac { \stackrel { \cdot } { ( K - 1 ) ( K - 2 ) q ^ { 3 } } } { K ^ { 2 } }.$$

$$\begin{array} { c c c } - & \langle - \langle \nu ^ { \prime \prime } & \L K & \nu ^ { \prime } & \langle \nu ^ { \prime } \\ V & = & ( \mathbb { E } ( \theta ) ) ^ { 2 } \left ( \frac { p } { K } + \frac { ( K - 1 ) q } { K } \right ) ^ { 2 }, \\ T & = & \frac { p ^ { 3 } } { \sim } + \frac { 3 ( K - 1 ) p q ^ { 2 } } { \cdot } + \frac { ( K - 1 ) ( K - 2 ) q ^ { 3 } } { \cdot }. \end{array}$$

Hence the expectation of the clustering coefficient given in (1) can be approximated as:

$$\Phi _ { \mathbb { E } ( \hat { c } c ) } \approx c c \equiv \frac { 3 T } { V } = \frac { \mu _ { \mathbb { E } ( P ^ { 3 } + 3 ( K - 1 ) p q ^ { 2 } + ( K - 1 ) ( K - 2 ) q ^ { 3 } ) } } { ( \mathbb { E } ( \theta ) ) ^ { 2 } \left ( p + ( K - 1 ) q \right ) ^ { 2 } }. \quad \quad \quad ( 6 ) \\ \text{the above equation demonstrates that it is difficult to draw useful information from the clustering}$$

The above equation demonstrates that it is difficult to draw useful information from the clustering coefficient. First, the clustering coefficient involves p , q and E ( θ ) , which makes it difficult to get straight forward intuition about what is the clustering coefficient measuring. Second, it will tend to 0 as N goes to infinity in sparse ( p = O (1 /N ) ) or semi-sparse ( p = O (log( N /N ) ) ) networks. Therefore the clustering coefficient is not an appropriate measure at least under the DCBM.

In order to modify the clustering coefficient, we aim to remove the effects of θ and network density. From (3) and (4), E ( θ ) could be eliminated by taking the ratio V/E. We divide T by ( V/E ) 3 to remove link probability p and obtain the normalized clustering coefficient. The expectation of the normalized clustering coefficient can be approximated as

$$\mathbb { E } ( \hat { \rho } ) \approx \rho \equiv \frac { T E ^ { 3 } } { V ^ { 3 } } = \frac { K r ^ { 3 } + 3 K ( K - 1 ) r + K ( K - 1 ) ( K - 2 ) } { ( r + ( K - 1 ) ) ^ { 3 } }, \quad \quad ( 7 ) \\. \quad \ \, \quad \ \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \quad \. \. \quad \. \. \quad \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \ \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \. \ }$$

where r = p/q &gt; 1 . Moreover, since d dr E ( ρ ) = 3 K K ( -1)( r -1) 2 ( r + K -1) 4 &gt; 0 , ρ is an increasing function of r. Hence, the normalized clustering coefficient can be used to infer the "in-out-ratio" r under the DCBM framework. The larger the value of the normalized clustering coefficient, the stronger the community effect.

The next theorem shows that ˆ ρ is asymptotically normal with a high convergence rate d -3 / 2 , where d = Np.

Theorem 1 Under the DCBM with K ≥ 2 as a constant, assume E (Θ ) = 4 O (1) , N -1 /lessmuch p /equivasymptotic q /lessmuch N -2 3 and ˆ V &gt; 0 . Let ρ = TE 3 V 3 . Then

$$\omega \rho = \frac { 1 } { V ^ { 3 } } \cdot \, \i n e n \\ \frac { \sqrt { ( \begin{matrix} ^ { N } _ { 3 } ) T } ( \hat { \rho } - \rho ) \\ \rho \end{matrix} } } { \rho } \sim N ( 0, 1 ).$$

Since ρ ∈ (1 , K ) and K is a given constant, the convergence rate is O ( √ N T . 3 ) The technical proof of Theorem 1 is given in Appendix A.

Since ρ is a monotone function of r , combined with the result of Theorem 1, the value of the "in-outratio" of the DCBM can be inferred from the value of the normalized clustering coefficient instead of applying a community detection algorithm first and then calculating the "in-out-ratio" with the community labels. To our best knowledge, this is the first work to infer the "in-out-ratio" under the DCBM without applying community detection algorithms.

## 2.3 Under the LCD model

In this subsection we explore the normalized clustering coefficient under the LCD model, which was first introduced in [5]. Let d G ( v ) denote the degree of the vertex v in the graph G. Define a random graph process ( G ( ) t m t ) ≥ 0 , where m is an integer, so that G ( ) t m is a graph on { v i : 1 ≤ i ≤ } t generated as follows: start with the graph with one vertex and m self-loops ( G (1) m ) . Form G ( ) t m based on G ( t -1) m by adding a new vertex v t together with m edges between v t and { v i 1 , v i 2 , . . . , v i m } , where i j is randomly chosen with probability

$$\Theta & \text{chosen with probability} \\ \mathbb { P } ( i _ {$$

j ∈ { 1 2 , , . . . , m } . Send m edges from v t to m different vertexes and the probability that a vertex is chosen is proportional to its degree. The LCD model satisfies the vague description of the generation rule from the Barabási-Albert model (BA model), which was introduced by [2].

The normalized clustering coefficient has the following property under the LCD model:

Theorem 2 Let m ≥ 1 be fixed. Then as N →∞ , we have

$$\mathbb { E } ( \hat { \rho } ) \sim \frac { 3 m ($$

From Theorem 2, the normalized clustering coefficient only depends on the parameter m. Furthermore, since 3 m m ( -1) 4( m +1) 2 is a monotone function of m, we can infer m from the value of the normalized clustering coefficient. The proof of Theorem 2 is given in Appendix A.

Investigating the expectation of the normalized clustering coefficient, it is interesting to find that its range is [0 , 3 4 ) under the LCD model, 1 under the Erdös-Rényi model and (1 , K ) under the DCBM as shown in Figure 1. Therefore, we can roughly identify the generative model of the observed network by simply counting the normalized clustering coefficient.

Figure 1

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-1a900cd7-8258-46f7-a4ea-8de55e9bcaf0.jpg)

## 3 Applications

In this section, we describe several possible applications of the normalized clustering coefficient in network data analysis.

## 3.1 Networks clustering

Given two networks G 1 and G 2 with adjacency matrices A 1 and A , 2 a natural question is: are they generated from the same probabilistic generative model? This is referred to as networks clustering, which attempts to group similar networks together. In the computer science literature ([27], [29]), kernel based similarity measures between networks are proposed and computed efficiently. Recently, two algorithms called Networks Clustering based on Graphon Estimates (NCGE) and Networks Clustering based on Log Moments (NCLM) are proposed by [22] to deal with the networks clustering task with or without node correspondence.

In this subsection, we demonstrate that the normalized clustering coefficient could provide important information about the structure of networks, and thus is potentially useful for networks clustering. Intuitively, we can compare the normalized clustering coefficients, ˆ ρ 1 and ˆ ρ , 2 of G 1 and G 2 respectively. If | ˆ ρ 1 -ˆ ρ 2 | is larger than a certain threshold c, we will reject the claim H 0 : G 1 and G 2 are generated from the same generative model.

## 3.1.1 A real example: Twitter network

Wecalculate the normalized clustering coefficient of Twitter ego networks to detect abnormal accounts. More details about the dataset and data preprocessing can be found in [14] and Appendix B. The density plot of the normalized clustering coefficient and the clustering coefficient are shown in Figure 2.

Figure 2: (a)Density plot of the clustering coefficient. (b)Density plot of the normalized clustering coefficient. (c)Density plot of the normalized clustering coefficient of low-degree users. (d)The ROC curves.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-7d0e9c8d-3bc4-48d4-b1e7-7bb55bf51446.jpg)

From Figure 2(a), the distribution of the clustering coefficient of fake accounts (red line) is very similar to that of normal accounts (green line). However, the distributions of the normalized clustering coefficient of the two types of accounts (Figure 2 (b)) are quite different. The normal accounts have larger normalized clustering coefficients than the fake accounts, which is consistent with the reality that there are community structures in real social networks while the fake users create links randomly.

It is also interesting to see that the density curve of the normal accounts' normalized clustering coefficient has a small peak between 0 and 0.5. This might be because the data are not completely labeled, which means that many fake accounts are incorrectly treated as normal ones, and most of

them have small normalized clustering coefficients. This represents evidence of the claim in [14] that Twitter operators have not discovered a substantial number of malicious accounts. In order to test our assumption, we randomly sampled 50,000 normal users whose degree is between 4 and 20, and we believe few of them are unlabeled fake users since fake users tend to connect to many users. We plot the density of their normalized clustering coefficient which is larger than 0 in Figure 2(c). The plot confirms that without unlabeled fake users, the distribution of the normalized clustering coefficient is normal.

Even with labeling issues, the normalized clustering coefficient still out performs the clustering coefficient. We calculate the ROC curves of these two statistics for comparison in 2(d). The AUC of the normalized clustering coefficient is 0.661 (red) and that of the clustering coefficient is 0.627 (green). The optimal threshold of the normalized clustering coefficient is 0.787 with specificity 0.561 and sensitivity 0.708.

It would be more flexible if we treat the normalized clustering coefficient as a new feature of networks and add it into other networks clustering algorithms. More simulation results of networks clustering can be found in Appendix B.

## 3.1.2 Theoretical result for the DCBM

To illustrate the above idea, we look at a special case of the DCBM with the same number of groups and balanced group size. Then the networks clustering problem is reduced to testing whether two networks have the same "in-out-ratio" for their generative models.

Proposition 1 Let G 1 be a network generated from the DCBM with parameters { N ,B,K,π,p ,q , 1 1 1 Θ 1 } , and G 2 be a network generated from the DCBM with parameters { N ,B,K,π,p ,q , 2 2 2 Θ 2 } , where π i = 1 /K,i ∈ { 1 , . . . , K } . Let r 1 = p /q 1 1 and r 2 = p /q . 2 2 Given adjacency matrices A 1 and A 2 of G 1 and G 2 respectively, we want to test

$$H _ { 0 } & \colon r _ { 1 } = r _ { 2 }, \\ H$$

/negationslash

Here, we allow the size of networks, the average degree of networks as well as the degree distribution of nodes to be different, which reflects the situation in the real world.

From Theorem 1, we have (ˆ ρ 1 -ˆ ) ρ 2 ∼ N ρ ( 1 -ρ , 2 ρ 2 1 ( N 1 3 ) T 1 + ( ρ 2 2 N 2 3 ) T 2 ) . Under null hypothesis, we obtain (ˆ ρ 1 -ˆ ) ρ 2 ∼ N (0 , ρ 2 ( N 1 3 ) T 1 + ( ρ 2 N 2 3 ) T 2 ) . Notice that in practice, the value of ρ is unknown. However, from equation (7), we have ρ ∈ (1 , K ) . Therefore, as long as the average degree is ω (1) , we can construct the following powerful test based on the normalized clustering coefficient:

Proposition 2 To test Proposition 1, we compute the normalized clustering coefficient of each network to obtain ˆ ρ 1 and ˆ ρ 2 first. We reject the null hypothesis when | ˆ ρ 1 -ˆ ρ 2 | &gt; φ -1 (1 -α 2 ) K √ 6 √ 1 d 3 1 + 1 d 3 2 with significant level α, where d 1 and d 2 are the average degrees of two networks.

Now, let us consider the power of the test in Proposition 2.

$$\begin{array} { l l$$

Although we have assumed the number of groups to be constant, it can be generalized to K = ( o d 3 2 ) , when ∆ = ρ O (1) . The proof of Theorem 3 is given in Appendix A.

## 3.2 Network sampling

In the real world, the enormous number of network nodes makes it infeasible to study the entire network computationally or visually. Therefore, network sampling is applied to understand the network structure and visualize the network.

Many sampling schemes have been proposed in the literature. The most intuitive one must be random node sampling, which chooses nodes independently and uniformly at random from the original network. However, the scheme is shown in [18] that due to its inclusion of all the edges for a sampled node set only, it is less likely to preserve the original level of connectivity. Several variations of node sampling have been proposed in the literature (for instance, [20]; [1]). Other sampling methods such as random walk based sampling and its derivatives and snow ball sampling are also widely used in practice. We recommend [24] for an excellent review of network sampling.

With so many sampling schemes to choose from, it is crucial to ask which one to pick, and more importantly, how to evaluate the sample quality. In [20], novel methods were proposed to check the goodness of sampling. In this section, we will show that the normalized clustering coefficient is a good criterion to evaluate the goodness of sampling.

First, let us state the network sampling in mathematical form. Given an input graph G V,E ( ) and a sampling fraction f , a sampling algorithm samples a representative sub-graph G s ( V , E s s ) with a subset of the nodes V s ⊂ V and a subset of the edges E s ⊂ { e ij | v i ∈ V , v s j ∈ V s } , such that | V s | = N s = fN . The goal is to ensure that the sampled sub-graph G s preserves the properties of the original graph G . Let the original network generated from the DCBM have parameters { N,K,π,p,q, Θ } . We want G s to have the same properties as a network generated from the DCBM with parameters { N , K , π , p s s s s , q s , Θ s } . It is hard to keep p s = p and q s = q because the average degree will probably change after sampling. However, it is reasonable to require r s = p /q s s = p/q = r. Recall equation 7, it is a necessary condition that ρ s = ρ, which implies ˆ ρ s should be close to ˆ ρ. Since we cannot make sure K s = K and π s = π, the closeness of the normalized clustering coefficient between the sub-network and the original network is not a sufficient condition to ensure the sub-network preserves the structure of the original one. However, it can help to screen out the bad sampling results and pick out the best ones.

In order to evaluate popular network sampling methods, we use three huge networks from different domains, the Arxiv COND-MAT (condense matter physics) collaboration network, the Enron email network and a human protein-protein interaction network (all are downloaded from http://snap. stanford.edu/ ). We apply random node sampling (NS), random edge sampling (ES), random walk sampling (RWS), random walk with flying back sampling (RWFS), random walk with jumping out sampling (RWJS), forest fire sampling (FF) and snowball sampling (SS) to draw 10 sub-networks each with sampling fraction f = 10% . More details of the data and sampling methods are given in Appendix C. We calculate the normalized clustering coefficient of each sub-network and obtain the mean and standard deviation for each sampling method to compare them with the original normalized clustering coefficient. The results are shown as follows:

|           |   Original | NS             | ES           | RWS          | RWJS         | RWFS         | FF           | SS           |
|-----------|------------|----------------|--------------|--------------|--------------|--------------|--------------|--------------|
| ConMatter |     103.68 | 123.52 (43.02) | 17.83 (1.46) | 24.91 (2.99) | 37.50 (5.56) | 20.81 (4.90) | 11.58 (2.19) | 12.35 (3.85) |
| Email     |       1.54 | 1.80 (1.43)    | 1.91 (0.02)  | 1.99 (0.06)  | 1.93 (0.04)  | 1.92 (0.10)  | 1.11 (0.18)  | 0.92 (0.43)  |
| PPI       |       2.53 | 2.89 (1.43)    | 2.01 (0.06)  | 2.08 (0.09)  | 1.88 (0.07)  | 1.98 (0.08)  | 1.35 (0.49)  | 1.05 (0.51)  |

Subgraph of ConMatter network

(a) Sub-graph of ConMatter (b) Sub-graph of Enron network (c) Sub-graph of PPI network Figure 3

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-daec4a8e-07b0-4e78-b555-67b528a32fda.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-ec410855-e1c2-47f3-a32b-9925f9ce736c.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-889197b2-0c08-49d2-9158-22d1d991adbc.jpg)

From the above table, we find that none of the sampling methods is always the best for every dataset. NS has quite large standard deviation because it often picks sub-networks with many isolated nodes. The disconnected issue is more serious with NS when the original network is sparse. All the methods fail on the co-author network. This is mainly because there are too many communities in the network (the original normalized clustering coefficient is 103.68, which indicates the number of communities should be larger than 104), and it is difficult to cover all the communities in the sub-network with a

limited size. In other words, it is hard to achieve K s = K , so ˆ ρ s will surely be far from ˆ ρ. However, this reflects the informativeness of the normalized clustering coefficient for network sampling from another point of view.

All the random walk based methods (RWS, RWJS and RWFS) have relatively good and stable performance. FF and SS are not so good mainly because of the bias they introduced. Since both FF and SS strongly rely on the initial node, they tend to sample the nodes from the same community with the initial node,which will lead to inaccurate estimation of the community proportion ( π ).

We plot the sub-network whose normalized clustering coefficient is the closest to that of the original large network in Figure 3 to visualize the structure of the original huge network.

More network sampling simulations can be found in Appendix C.

## 3.3 Dynamic network analysis

Networks often evolve with time. It is of great interest to capture the changing dynamics. Some research has focused on the problem of change point detection. We recommend [16] for a nice review. Detecting communities in dynamic networks is also studied both in statistics and computer science and is well reviewed in [25].

When performing analysis on dynamic networks, computational capability is required not only for large graphs, but for a long sequence of large graphs over time. The computational complexity of the algorithm is crucial especially for online learning over a short time. The normalized clustering coefficient, which only requires simple counting of triangles, could be updated every second, so it is helpful in monitoring the rapid revolution of dynamic networks. It is also useful for evaluating the clustering effect and is robust to changes in the number of vertexes and average degree.

We test the performance of the normalized clustering coefficient on the co-sponsorship networks structured from bills sponsored in the U.S. Senate during the 93rd-114th Congresses ([7]). More details of the data are given in Appendix D. We compute the normalized clustering coefficient, the clustering coefficient and the true "in-out-ratio" for each year's network. The true "in-out-ratio" is computed as number of edges between congress-persons in the same party number of edges between congress-persons in different parties .

Figure 4 illustrates that the normalized clustering coefficient can infer the true community strength without using the party labels, while the clustering coefficient cannot. There is an obvious change point during the 107th Senate. During that senate (January 3, 2001 to January 3, 2003), a rare even split occurred and the defection of a single senator led to three changes in majorities. The 9-11 attacks were highly disruptive and the U.S. Congress voted to allow the president to invade Iraq. The same attitudes from the two parties toward these events may explain the low community strength in the Senate.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-dad8a5c3-599f-40cc-8d3b-0c2c25ca6cf6.jpg)

t

T

## 4 Conclusion

Figure 4: Plot of the clustering strength of the cosponsorship networks structured from bills sponsored in the U.S. Senate during 93rd-114th Congresses. The normalized clustering coefficient (black line) can reveal the truth (red line) without using the party labels, while the clustering coefficient (green line) cannot.

We proposed a novel network statistic, the normalized clustering coefficient, to measure the clustering effect, and it is robust to the degree heterogeneity, network size and network density. The statistic not only has nice statistical properties, but its computational complexity is modest which makes it suitable for extremely large networks and rapidly varying dynamic networks. The statistic can also be applied for networks clustering, network sampling and dynamic network analysis.

## References

- [1] Ahmed, N. K., Neville, J., and Kompella, R. (2014). Network sampling: From static to streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) , 8(2), 7.

- [2] Barabási, A. L., and Albert, R. (1999). Emergence of scaling in random networks. science , 286(5439), 509-512.
- [3] Barrat, A., Barthelemy, M., and Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America , 101(11), 3747.
- [4] Bollobás, B., and Riordan, O. (2003). Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet , 1-34.
- [5] Bollobás, B., and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica , 24(1), 5-34.
- [6] Clemente, G. P., and Grassi, R. (2018). Directed clustering in weighted networks: A new perspective. Chaos, Solitons and Fractals , 107, 26-38.
- [7] Fowler, J. H. (2006). Legislative cosponsorship networks in the US House and Senate. Social Networks , 28(4), 454-465.
- [8] Gao, C., and Lafferty, J. (2017). Testing for global network structure using small subgraph statistics. arXiv preprint arXiv:1710.00862.
- [9] Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2018). Community detection in degree-corrected block models. The Annals of Statistics , 46(5), 2153-2185.
- [10] Gross, J. H., Kirkland, J. H., and Shalizi, C. (2012). Cosponsorship in the US Senate: A multilevel two-mode approach to detecting subtle social predictors of legislative support.
- [11] Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks , 5(2), 109-137.
- [12] Jin, J. (2015). Fast community detection by SCORE. The Annals of Statistics . 43(1), 57-89.
- [13] Jin, J., Ke, Z. T., and Luo, S. (2018, July). Network Global Testing by Counting Graphlets. In International Conference on Machine Learning , (pp. 2338-2346).
- [14] Kagan, D., Elovichi, Y., and Fire, M. (2018). Generic anomalous vertices detection utilizing a link prediction algorithm. Social Network Analysis and Mining , 8(1), 27.
- [15] Karrer, B. and Newman, M. E. (2011). Stochastic blockmodels and community structure in networks. Physical Review E , 83(1), 016107.
- [16] Kendrick, L., Musial, K. and Gabrys, B. (2018). Change point detection in social networks-Critical review with experiments. Computer Science Review , 29, 1-13.
- [17] Latapy, M., Magnien, C., and Del Vecchio, N. (2008). Basic notions for the analysis of large two-mode networks. Social Networks , 30(1), 31-48.
- [18] Lee, S. H., Kim, P. J., and Jeong, H. (2006). Statistical properties of sampled networks. Physical Review E , 73(1), 016102.
- [19] Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics , 43(1), 215-237.
- [20] Leskovec, J., and Faloutsos, C. (2006, August). Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , (pp. 631-636). ACM.
- [21] Luce, R. D., and Perry, A. D. (1949). A method of matrix analysis of group structure. Psychometrika , 14(2), 95-116.
- [22] Mukherjee, S. S., Sarkar, P., and Lin, L. (2017). On clustering network-valued data. In Advances in neural information processing systems , pp. 7071-7081.
- [23] Opsahl, T., and Panzarasa, P. (2009). Clustering in weighted networks. Social Networks , 31(2), 155-163.
- [24] Rezvanian, A., Moradabadi, B., Ghavipour, M., Khomami, M. M. D., and Meybodi, M. R. (2019). Social Network Sampling. In Learning Automata Approach for Social Networks , (pp. 91-149). Springer, Cham.
- [25] Rossetti, G., and Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR) , 51(2), 35.

- [26] Schank, T., and Wagner, D. (2004). Approximating clustering-coefficient and transitivity. Journal of Graph Algorithms and Applications , 9(2), 265-275.
- [27] N. Shervashidze, SVN. Vishwanathan, TH. Petri, K. Mehlhorn, and KM. Borgwardt. (2009) Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics (pp. 488-495).
- [28] Watts, D. J., and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature , 393(6684), 440.
- [29] Wolfe, P. J., and Olhede, S. C. (2013). Nonparametric graphon estimation. arXiv preprint arXiv:1309.5936.
- [30] Zhao, Y., Levina, E., and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics . 40(4), 2266-2292.

## Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient: Supplementary Information

Ting Li tlial@ust.hk

HKUST

Xianshi Yu University of Michigan xsyu@umich.edu

Bing-Yi Jing HKUST majing@ust.hk

## Appendix A

## Proof of Theorem 1

The following lemmas, which will be used later, are Lemma C.1 and Lemma C.2 from [2]:

Lemma 1 Assume E Θ = 4 O (1) and N -1 /lessmuch p /equivasymptotic q = (1) o . Then

$$\mathbb { E } ( \hat { E } - E ) ^ { 2 } = O ( \$$

Lemma 2 Assume E Θ = 4 O (1) and N -1 /lessmuch p /equivasymptotic q = N -2 3 . Then

$$\colon A s s u m e \, \mathbb { E } \Theta ^ {$$

Proof of Theorem 1.

$$\begin{array} {$$

By Lemma 1 and Lemma 2, TE 3 V 3 +( ˆ T -T ) E 3 V 3 is the dominating term. Hence which is the result.

$$\theta _ { 0 } \stackrel { \prime \, v \, \kappa }$$

## Proof of Theorem 2

The following two lemmas, which are Theorem 14 and Theorem 16 from [1], describe the number of triangles and triplets in G ( ) t m .

Preprint. Under review.

Lemma 3 Let m ≥ 1 be fixed. The expected value of the number of triangles in G ( ) t m is given by

$$( 1 + o ( 1 ) ) \frac { m ( m - 1 ) ( m + 1 )$$

as N →∞ .

Lemma 4 Let m ≥ 1 and /epsilon1 &gt; 0 be fixed. Then holds with a high probability as N →∞ .

$$\ m a \, \Phi \, \L e l \, m \, \leq$$

For a graph G ( ) t m generated from the LDC model, the number of edges is fixed at mN. Combining this fact with Lemma 3 and Lemma 4, we can easily reach the result in Theorem 2.

## Proof of Theorem 3

Similar to the proof of Theorem 1, ˆ ρ 1 -ˆ ρ 2 is dominated by

From Lemma 2 we have

$$& \text{ar to the proof of Theorem 1, } \hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } \text{ is dominated by} \\ & \rho _ { 1 } - \rho _ { 2 } + \frac { \rho _ { 1 } } { \binom { N _ { 1 } } { 3 } T _ { 1 } } \frac { \sqrt { \binom { N _ { 1 } } { 3 } } ( \hat { T } _ { 1 } - T ) } { \sqrt { T _ { 1 } } } - \frac { \rho _ { 2 } } { \binom { N _ { 2 } } { 3 } T _ { 2 } } \frac { \sqrt { \binom { N _ { 2 } } { 3 } } ( \hat { T } _ { 2 } - T ) } { \sqrt { T _ { 2 } } }. \\ & \text{Lemma} \, 2 \, \text{ we have} \\ & \quad \nolimits _ { \alpha ^ { 2 } }$$

Without loss of generality, let r 1 &gt; r . 2 Then ρ 1 &gt; ρ . 2 Therefore, from the assumption, we have

$$\hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } \sim N ( \rho _ { 1 } - \rho _ { 2 }, \frac { \rho _ { 1 } ^ { 2 } } { \binom { N _ { 1 } } { 3 } T _ { 1 } } + \frac { \rho _ { 2 } ^ { 2 } } { \binom { N _ { 2 } } { 3 } T _ { 2 } } ). \\ \text{erality, let $r_{1}>r_{2}$. Then $\rho_{1}>\rho_{2}$. Therefore, from the assun} \\ \gamma _ { 1 }.$$

which is the result.

$$\hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } \stackrel { \sim } { \longrightarrow } N ( \rho _ { 1 } - \rho _ { 2 }, \frac { \rho _ { 1 } ^ { 2 } } { \hat { \rho } _ { 1 } ^ { 2 } } + \frac { \rho _ { 2 } ^ { 2 } } { \hat { \rho } _ { 2 } ^ { 2 } } ). \\ \text{Without loss of generality, let } r _ { 1 } > r _ { 2 }. \text{ Then } \rho _ { 1 } > \rho _ { 2 }. \text{ Therefore, from the assumption, we have } \\ \mathbb { P } ( \text{Reject } H _ { 0 } | H _ { 1 } ) \ \geq \ \mathbb { P } \left ( d ^ { \frac { 3 } { 2 } } | \hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } | \geq c | H _ { 1 } \right ) \ \text{ (here } c = \phi ^ { - 1 } ( 1 - \frac { \alpha } { 2 } ) K \sqrt { 6 } \right ) \\ \geq \ \ 1 - \mathbb { P } \left ( d ^ { \frac { 3 } { 2 } } | \hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } | \leq c | H _ { 1 } \right ) \\ \geq \ \ 1 - \mathbb { P } \left ( d ^ { \frac { 3 } { 2 } } ( \hat { \rho } _ { 1 } - \hat { \rho } _ { 2 } ) < c | H _ { 1 } \right ) \\ \geq \ \ 1 - \mathbb { P } \left ( d ^ { \frac { 3 } { 2 } } ( \Delta \rho - \hat { \rho } _ { 1 } + \hat { \rho } _ { 2 } ) \geq ( d ^ { \frac { 3 } { 2 } } \Delta \rho - c ) | H _ { 1 } \right ) \\ \geq \ \ 1 - \frac { 1 } { 1 + \frac { ( \Delta \rho ^ { 2 d \phi } } { 2 \phi } } } \left ( b y \, \text{ Cantelli inequality} \right ) \\ \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
 \text{which is the result.} \\ \text{ } \\ \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{                                                                                                                                                                                                         }                                                                                                                                                                                                       
  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{
  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \end{
  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text { } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \end{}$$

## Appendix B

## Simulations on networks clustering

Simulation studies are conducted to compare the performance of the clustering coefficient and the normalized clustering coefficient in networks clustering.

In Simulation 1, we take N = 200 , K = 3 , π = (1 3 1 3 1 / , / , / 3) , Θ ≡ 1 , and average degree λ = 15 . We use the "in-out-ratio" r 1 = p /q 1 1 = 20 3 / to generate 500 different networks, and r 2 = 10 to generate another 500 different networks. Then, we calculate the normalized clustering coefficient and the clustering coefficient for these 1000 networks to see whether we can identify these two types of networks through these two measures. The density curves for these two types of networks are plotted in Figures 1 (a) and (b)). It can be seen that both measures can separate the two types of networks well.

(a) Density plot of the normalized clustering coef-(b) Density plot of the clustering coefficient in ficient in Simulation 1. Simulation 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-29f9dd95-5451-45a5-8c9d-0952a5b90460.jpg)

Figure 1

Simulation 2 modifies the settings in Simulation 1. This time the Θ values are drawn independently with P θ ( = 0 2) = 0 8 . . and P θ ( = 1) = 0 2 . , corresponding to the DCBM with hubs. Meanwhile, 500 networks are sampled with the average degrees λ 1 and λ 2 drawn from uniform distributions U (25 30) , and U (10 15) , , respectively. Other parameters are kept unchanged. Figures 2 (a) and (b) show that because of the effect of average degree and degree heterogeneity, the clustering coefficient cannot tell the difference between these two types of networks. However, the normalized clustering coefficient can still tell them apart. Furthermore, the last 500 networks all have larger normalized clustering coefficients than the first 500 networks, which is consistent with the ground truth.

(a) Density plot of the normalized clustering coef-(b) Density plot of the clustering coefficient in ficient in Simulation 2. Simulation 2.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-0695c5f5-1f8b-488f-b361-359c7cf850a9.jpg)

Figure 2

In Simulation 3, different from Simulation 1, we make the distribution of Θ different for the two types of networks with Θ 1 and Θ 2 from two power law distributions with shape parameters α 1 = 4 2 . and α 2 = 6 respectively. We keep other parameters the same as in Simulation 1. Figures 3(a) and (b) show that the clustering coefficient could not remove the effect of the distribution of Θ , while the normalized clustering coefficient could still catch the main difference between these two types of networks.

(a) Density plot of the normalized clustering coef-(b) Density plot of the clustering coefficient in ficient in Simulation 3. Simulation 3.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-7d1aa544-8b41-4545-8536-0d3fc599a012.jpg)

Figure 3

From Simulations 1-3, it is clear that the average degree and the distribution of the degree of nodes do not affect the normalized clustering coefficient, while the clustering coefficient is badly affected. Furthermore, from Figures 1-3, the normalized clustering coefficient is Gaussian with relatively small variance. All of these observations are consistent with the analysis in Section 2.

## Real data on network clustering

## We download the data from

https://github.com/Kagandi/anomalous-vertices-detection/tree/master/data.

The network is constructed from the friendships between Twitter users in 2014 along with some labels of fake accounts. There are 5,384,160 nodes , among which 12,437 are labeled as fake accounts by Twitter. There are 16,011,443 edges in total. In [4], the authors propose an anomalous vertice detection algorithm based on link prediction.

However, we first extract the one-step ego network of each node, which leads to 5,384,160 different networks in total. Then, we calculate the normalized clustering coefficient for each ego network and classify the nodes with this coefficient. We also compare the performance of the normalized clustering coefficient and the clustering coefficient. We focus on the nodes with degree larger than 20. In total, 148,830 users have more than 20 friends and 7,526 are labeled as fake. Among the 148,830 users, the ego networks of 52,031 do not have triangles or triplets and there are 4,473 fake users. Lastly, we focus on the remaining 96,799 accounts with 3,053 fake ids to compare the performance of the two statistics.

## Appendix C

## Network sampling algorithms

The network sampling algorithms we used in the simulations and empirical study are listed as follows:

Random node sampling (NS): Uniformly at random select a set of nodes. A sample is then a graph induced by the selected nodes.

Random edge sampling (ES): Uniformly at random select a set of edges. A sample is then a graph induced by the ends of these edges.

Random walk sampling (RWS): Uniformly at random pick a starting node and then simulate a random walk on the graph.

Random walk with flying back sampling (RWFS): Based on RWS, at every step with probability p = 0 15 . (the value commonly used in the literature [5]) we fly back to the starting node and re-start the random walk.

Random walk with jumping out sampling (RWJS): Based on RWS, at every step with probability p = 0 15 . (the value commonly used in the literature [5]) we randomly jump to any node in the graph and re-start the random walk.

## Forest fire sampling (FF) ([5]):

"We first choose node v uniformly at random. We then gen- erate a random number x that is geometrically distributed with mean p f / (1 -p f ) . Node v selects x out-links incident to nodes that were not yet visited. Let w , w , ..., w 1 2 x denote the other ends of these selected links. We then apply this step recursively to each of w , w , ..., w 1 2 x until enough nodes have been burned. As the process continues, nodes cannot be visited a second time, preventing the construction from cycling. If the fire dies, then we restart it, i.e. select new node v uniformly at random." We take p f = 0 7 . as suggested in [5].

Snowball sampling (SS): We use function snowball\_sampling() in R package "netdep" ( https: //cran.r-project.org/web/packages/netdep/index.html ).

## Simulations on network sampling

We perform simulations to compare different network sampling algorithms based on the normalized clustering coefficient. The better algorithms would be the ones that can obtain sub-networks whose normalized clustering coefficient is closer to that of the original network.

In Simulation 4, we generate a large network G 1 from the DCBM with parameters N = 2000 , K = 3 , π = (1 / 3 1 , / , 3 1 / 3) , r = p/q = 10 , Θ generated from power law distribution and the average degree d = 200 . We let the ratio of sampling f to vary from 2% -40% . For each sampling algorithm and each sampling ratio, we sample 50 sub-networks and calculate their normalized clustering coefficient and then take the average for comparison with the original normalized clustering coefficient ( G s ′ 1 ). The result is plotted in Figure 4. It is clear from Figure 4 that as f increases, the normalized clustering coefficient of sub-networks becoming closer to the original one (light green line). NS and ES perform the best followed by RWJS and RWS. This is because G 1 is quite a dense network which reduces the risk of obtaining isolated nodes in the sub-network when NS or ES is applied. RWFS, FF and SS are unsatisfactory mainly because of the bias introduced by the initial nodes.

Figure 4: The normalized clustering coefficients of sub-networks and the original networks in Simulation 4.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-a7089096-98cf-4416-a245-c71486a75b6f.jpg)

In Simulation 5, we reduce the average degree d to 20 and obtain a new large network G 2 . The result in Figure 5 shows that all the algorithms perform worse than they do in Simulation 4, which indicates that sparsity increases the sampling difficulty. Moreover, the performance of NS and ES is greatly affected when the sampling ratio is less than 10% .

Figure 5: The normalized clustering coefficients of sub-networks and the original networks in Simulation 5.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-3fdb98e3-1c9d-427c-b9eb-670d22a2fd09.jpg)

In Simulation 6, the performance of both NS and ES becomes worse when we reduce the average degree d to 4 to obtain a sparse network G 3 (see Figure 6). The standard deviations of NS and ES are quite large too. Most sub-networks drawn by NS and ES have many isolated nodes, which makes the performance unstable. However, RWJS and RWS continue to perform well in sparse networks. According to these simulations, RWJS and RWS can give a better trade-off between bias and variance than the other algorithms overall.

Figure 6: The normalized clustering coefficients of sub-networks and the original networks in Simulation 6.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00523v1-figure-d4b5c521-69fd-4f76-ac8f-9800883a3b93.jpg)

## Real data on network sampling

More details about the networks used in our empirical study on network sampling can be found on SNAP:

Condensed matter collaboration network (23133 nodes, 93497 edges): https://snap.stanford. edu/data/ca-CondMat.html .

Enron email network (36692 nodes, 183831 edges): http://snap.stanford.edu/data/ email-Enron.html .

Human protein-protein interaction network (21557 nodes, 342353 edges): https://snap. stanford.edu/biodata/datasets/10000/10000-PP-Pathways.html .

## Appendix D

The senate data we used in the dynamic network analysis are downloaded from https://github. com/briatte/congress . Edges are formed between two congress-persons using the weighted propensity ([3]) to cosponsor with threshold 0 1; . that is: let Y ij ( k ) = 1 if i cosponsors j 's k th bill and 0 otherwise, and let c j ( k ) be the number of cosponsors of senator j 's k th bill. The relative weighted propensity to cosponsor of i for j is defined as

$$\rangle \, \text{is denied as} \\ \ W P C _ { i, j } = \frac { \sum _ { k = 1 } ^ { n _ { j } } \frac { Y _ { i j ( k ) } } { c _ { j ( k ) } } } { \sum _ { k = 1 } ^ { n _ { j } } \frac { 1 } { c _ { j ( k ) } } } \\ \text{ith } W P C < 0. 1 \, \text{and set the edge} \colon \\ \text{twork for each year of senate.}$$

Lastly, we eliminate the edges with WPC &lt; 0 1 . and set the edges with WPC ≥ 0 1 . to 1 to obtain an unweighted and undirected network for each year of senate.

## References

- [1] Bollobás, B., and Riordan, O. (2003). Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet , 1-34.

- [2] Gao, C., and Lafferty, J. (2017). Testing for global network structure using small subgraph statistics. arXiv preprint arXiv:1710.00862.
- [3] Gross, J. H., Kirkland, J. H., and Shalizi, C. (2012). Cosponsorship in the US Senate: A multilevel two-mode approach to detecting subtle social predictors of legislative support.
- [4] Kagan, D., Elovichi, Y., and Fire, M. (2018). Generic anomalous vertices detection utilizing a link prediction algorithm. Social Network Analysis and Mining , 8(1), 27.
- [5] Leskovec, J., and Faloutsos, C. (2006, August). Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , (pp. 631-636). ACM.
Ting Li Xianshi Yu Bing-Yi Jing
Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient
In this paper, we propose a novel statistic of networks, the normalized
clustering coefficient, which is a modified version of the clustering
coefficient that is robust to network size, network density and degree
heterogeneity under different network generative models. In particular, under
the degree corrected block model (DCBM), the "in-out-ratio" could be inferred
from the normalized clustering coefficient. Asymptotic properties of the
proposed indicator are studied under three popular network generative models.
The normalized clustering coefficient can also be used for networks clustering,
network sampling as well as dynamic network analysis. Simulations and real data
analysis are carried out to demonstrate these applications.