# On the Distributions of Subgraph Centralities in Complex Networks

Authors: Faxu Li; Liang Wei; Haixing Zhao; Feng Hu
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

Subgraph centrality measure characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than large ones, which makes this measure appropriate for characterizing network motifs. This measure is better in being able to discriminate the
nodes of a network than alternate measures. In this paper, the important issue of subgraph centrality distributions is investigated through theory-guided extensive numerical simulations, for three typical complex network models, namely, the ER random-graph networks, WS small-world networks, and BA
scale-free networks. It is found that these three very different types of complex networks share some common features, particularly that the subgraph centrality distributions in increasing order are all insensitive to the network connectivity characteristics, and also found that the probability distributions of subgraph centrality of the ER and of the WS models both follow the gamma distribution, and the BA scale-free networks exhibit a power-law distribution with an exponential cutoff.


---

## Body

## 1. Introduction

Complex networks, consisting of sets of nodes or vertices joined together in pairs by links or edges, appear frequently in various technological, social, and biological scenarios [1–5]. These networks include the Internet [6], the World Wide Web [7], social networks [8–10], scientific collaboration networks [11], lexicon or semantic networks [12, 13] and neural networks [14], food webs [15], metabolic networks [16], and protein interaction networks [17]. They have been shown to share global statistical features, such as the “small world” and the “scale-free” effects, as well as the “clustering” property.It has been observed that not only triangles but also other subgraphs are significant in real networks. We say that a graphG′=(V′,E′) is a subgraph of G=(V,E) if V′⊆V and E′⊆E. The term “network motifs” designates those patterns that occur in the network far more often than in random networks with degree sequence [18]. Network motifs found in technological and biological networks are small subgraphs that capture specific patterns of interconnection characterizing the networks at the local level [18, 19].Another kind of local characterization of networks is made numerically by using one of several measures known as “centrality” [20]. One of the most used centrality measures is the “degree centrality”, DC [7], which is a fundamental quantity describing the topology of scale-free networks [21].There are several other centrality measures that have been introduced and studied for real-world networks, such as closeness, betweenness, eigenvector and subgraph centrality, and so on. They account for the different node characteristics that permit them to be ranked in the order of importance in the network. Among these centrality measures, subgraph centrality characterizes nodes according to their participation in structural subgraphs in the network, giving higher weights to the smaller subgraphs that can be involved in network motifs. This measure has been tested in artificial networks, showing that it is better in being able to discriminate the nodes of a network than alternate measures [22].Among the many representative network models, the classical Erdös-Rényi (ER) random-graph networks [23], Watts-Strogatz (WS) small-world networks [14] and Barabási-Albert (BA) scale-free networks [24] are particularly significant and important. The questions to be addressed in this paper are as folloiws: “are there any similar statistical properties of the subgraph centralities with respect to the topological features in ER, WS, and BA network models? What probability distributions do the subgraph centrality of the three network models follow?” Noticeably, the two questions have been addressed from different points of view in the literature. For example, it was shown in [22] that the cumulative distribution of subgraph centrality displayed scale-free characteristics in the eight networks studied. From a somewhat different standpoint and approach, this paper performs a careful numerical analysis based on intensive computer simulations to study the subgraph centrality distributions of three representative complex network models: the ER random-graph networks, WS small-world networks, and BA scale-free networks.One of the main findings of this paper is that the probability distributions of subgraph centrality for the ER and WS models both follow the gamma distribution, and the BA scale-free networks exhibit a power-law distribution with an exponential cutoff; another finding is that the subgraph centrality distributions in increasing order of the aforementioned three types of complex networks have very different properties in general and yet meanwhile share some common features. More precisely, by plotting the subgraph centrality indices in increasing order of three network models, we obtain various “subgraph centrality curves” and find that, in different realizations of the same type of network topology of the same size, the relative deviations of their subgraph centrality curves are very small with only up to±0.5 errors. This phenomenon shows that, for a certain network with fixed size and given node-degree distribution, the subgraph centrality distributions of these three very different types of complex networks are all insensitive to the network connectivity characteristics.The rest of this paper is organized as follows. In Section2, we provide a brief definition of subgraph centrality and generating algorithms for the ER random-graph networks, WS small-world networks, and BA scale-free networks, useful throughout the paper. Section 3 presents some theory-guided numerical analysis of the subgraph centrality distributions of three network models in the nondecreasing order. Section 4 gives some theory-guided numerical analyses about the probability distributions of subgraph centrality for three network models. The main results of the paper reported in Sections 3 and 4. Finally, conclusions are drawn in Section 5.


## 2. Preliminaries

### 2.1. Notations

Nis the the number of nodes in a network model. p is the probability parameter. ki is the degree of node i, defined to be the number of edges directly connecting node i. A is the N×N adjacency matrix,  defined by
(1)aij={1ifi≠j,iadjacentj,0otherwise.


### 2.2. Subgraph Centrality(CS)

Subgraph centrality characterizes the participation of each node in all subgraphs in a network. The subgraph centrality of nodei was defined as the “sum" of closed walks of different lengths in the network starting and ending at node i. The contribution of these closed walks decreases as the length of the walks increases. That is, shorter closed walks have more influence on the centrality of the node than longer closed walk. The subgraph centrality of node i in the networks is given by [22]
(2)CS(i)=∑k=0∞‍μk(i)k!.By a series of deducing, the subgraph centrality for alli∈V may be expressed as follows [22]:
(3)CS(i)=∑j=1N‍vjieλj,
where v1,v2,…,vN are an orthonormal basis of RN composed by eigenvectors of A associated with the eigenvalues λ1,λ2,…,λN, and vji denotes the ith component of  vj.A global characterization of the network can be carried out by means of the average subgraph centrality, denoted by〈CS〉. It is given by [22]
(4)〈CS〉=1N∑i=1N‍CS(i)=1N∑i=1N‍eλi.It was shown that〈CS〉 depends only on the eigenvalues and size of the adjacency matrix of the network [22].


### 2.3. Generation Algorithms of Complex Network Models

#### 2.3.1.  The ER Random-Graph Network

The ER random-graph network is generated by the following steps (ER algorithm); see [25].  (1)
Start withN isolated nodes, and number the nodes from 0 to (N-1).(2)
Pick up every pair of nodes and connect them by edge with probabilityp.


#### 2.3.2. The WS Small-World Network

The WS small-world network model is generated by the following steps (WS algorithm); see [25].    (1)
Start with a regular nearest-neighboring network withN nodes, in which each node is connected to its 2m0 neighbors, where m0>0 is a small integer.(2)
At every step, for each node, operate on its connections to itsm0 nearest neighbors, one by one in a clockwise (or counterclockwise) manner: an edge connecting this node to its neighbor will be kept in place, but another end of edge will be reconnected with probability p to a node randomly chosen from elsewhere in the network.


#### 2.3.3. The BA Scale-Free Network Model

The BA scale-free network model is generated by the following steps (BA algorithm); see [25].  (1)
Growth: starting from a small fully connected network of nodesm0>0, where m0>0 is a small integer. At each time step, a new node is added to the existing network, and this new node is connected to m, the previously added nodes, where 1≤m≤m0.(2)
Preferential attachment: the probability of a new link to end up in an existing nodei is proportional to the connectivity ki of this node:
(5)∏‍(ki)=ki∑j=1Nkj.


## 2.1. Notations

Nis the the number of nodes in a network model. p is the probability parameter. ki is the degree of node i, defined to be the number of edges directly connecting node i. A is the N×N adjacency matrix,  defined by
(1)aij={1ifi≠j,iadjacentj,0otherwise.


## 2.2. Subgraph Centrality(CS)

Subgraph centrality characterizes the participation of each node in all subgraphs in a network. The subgraph centrality of nodei was defined as the “sum" of closed walks of different lengths in the network starting and ending at node i. The contribution of these closed walks decreases as the length of the walks increases. That is, shorter closed walks have more influence on the centrality of the node than longer closed walk. The subgraph centrality of node i in the networks is given by [22]
(2)CS(i)=∑k=0∞‍μk(i)k!.By a series of deducing, the subgraph centrality for alli∈V may be expressed as follows [22]:
(3)CS(i)=∑j=1N‍vjieλj,
where v1,v2,…,vN are an orthonormal basis of RN composed by eigenvectors of A associated with the eigenvalues λ1,λ2,…,λN, and vji denotes the ith component of  vj.A global characterization of the network can be carried out by means of the average subgraph centrality, denoted by〈CS〉. It is given by [22]
(4)〈CS〉=1N∑i=1N‍CS(i)=1N∑i=1N‍eλi.It was shown that〈CS〉 depends only on the eigenvalues and size of the adjacency matrix of the network [22].


## 2.3. Generation Algorithms of Complex Network Models

### 2.3.1.  The ER Random-Graph Network

The ER random-graph network is generated by the following steps (ER algorithm); see [25].  (1)
Start withN isolated nodes, and number the nodes from 0 to (N-1).(2)
Pick up every pair of nodes and connect them by edge with probabilityp.


### 2.3.2. The WS Small-World Network

The WS small-world network model is generated by the following steps (WS algorithm); see [25].    (1)
Start with a regular nearest-neighboring network withN nodes, in which each node is connected to its 2m0 neighbors, where m0>0 is a small integer.(2)
At every step, for each node, operate on its connections to itsm0 nearest neighbors, one by one in a clockwise (or counterclockwise) manner: an edge connecting this node to its neighbor will be kept in place, but another end of edge will be reconnected with probability p to a node randomly chosen from elsewhere in the network.


### 2.3.3. The BA Scale-Free Network Model

The BA scale-free network model is generated by the following steps (BA algorithm); see [25].  (1)
Growth: starting from a small fully connected network of nodesm0>0, where m0>0 is a small integer. At each time step, a new node is added to the existing network, and this new node is connected to m, the previously added nodes, where 1≤m≤m0.(2)
Preferential attachment: the probability of a new link to end up in an existing nodei is proportional to the connectivity ki of this node:
(5)∏‍(ki)=ki∑j=1Nkj.


## 2.3.1.  The ER Random-Graph Network

The ER random-graph network is generated by the following steps (ER algorithm); see [25].  (1)
Start withN isolated nodes, and number the nodes from 0 to (N-1).(2)
Pick up every pair of nodes and connect them by edge with probabilityp.


## 2.3.2. The WS Small-World Network

The WS small-world network model is generated by the following steps (WS algorithm); see [25].    (1)
Start with a regular nearest-neighboring network withN nodes, in which each node is connected to its 2m0 neighbors, where m0>0 is a small integer.(2)
At every step, for each node, operate on its connections to itsm0 nearest neighbors, one by one in a clockwise (or counterclockwise) manner: an edge connecting this node to its neighbor will be kept in place, but another end of edge will be reconnected with probability p to a node randomly chosen from elsewhere in the network.


## 2.3.3. The BA Scale-Free Network Model

The BA scale-free network model is generated by the following steps (BA algorithm); see [25].  (1)
Growth: starting from a small fully connected network of nodesm0>0, where m0>0 is a small integer. At each time step, a new node is added to the existing network, and this new node is connected to m, the previously added nodes, where 1≤m≤m0.(2)
Preferential attachment: the probability of a new link to end up in an existing nodei is proportional to the connectivity ki of this node:
(5)∏‍(ki)=ki∑j=1Nkj.


## 3. Distributions of Subgraph Centralities in the Increasing Order

In this section, we discuss the distributions of subgraph centralities calculated by (3) for three typical network models, namely, the ER random-graph model, the WS small-world model and the BA scale-free model, respectively. To quantify the variability of a subgraph centrality, define the relative deviation as
(6)vi=CS(i)-〈CS(i)〉〈CS(i)〉,
where 〈CS(i)〉 is averaged over CS(i) of 50 networks, and 〈CS(i)〉≠0 for all i, i=1,2,…,N.


### 3.1. ER Random-Graph Networks

The simulation results are plotted in Figure1(a), where the number of simulation runs on ER random-graph network model is 50, therefore totally 50 network realizations were generated by ER algorithm, and a total of 2500×50 subgraph centralities were plotted altogether in the same figure (they are not the averages of the subgraph centralities of the 50 simulations). Figure 1(b) shows the averages of the subgraph centralities of the ER model plotted in Figure 1(a). To quantify the variability of the subgraph centralities, the relative deviations defined by (6) were calculated and are plotted in Figure 2. The ER algorithm was run with N=2500 and p=0.08.(a) The subgraph centralityCS(i) curves of the ER model, (b) mean subgraph centrality 〈CS(i)〉 curve of the ER model.
(a)
(b)Figure 2
Relative deviations of subgraph centralitiesCS(i) of the ER model.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure1(a) with Figure 1(b), that the two figures look quite similar; namely, the actual values of each subgraph centrality in all individual runs and averages of the subgraph centralities are not much different. This implies that in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small. A phenomenon needs further investigation in the future.(2)
Figure2 shows that the relative deviations of subgraph centralities are mostly located nearby, with up to ±0.05 errors, which are quite small. This phenomenon shows that the subgraph centralities of ER complex networks are insensitive to the network connectivity characteristics; namely, in different realizations with the same size N and probability p, the subgraph centrality curves are almost the same as shown in Figure 1. Thus, for an ER-type complex network, in order to estimate its subgraph centrality distribution, one does not need to know the detailed information about its specific connectivity topology but only needs to know the values of N and p in general.


### 3.2.  WS Small-World Networks

Similar to the analysis of ER complex networks, Figure3 shows the plots of the curves of the distributions of subgraph centralities and mean subgraph centralities. Figure 4 shows the plot of the relative deviations. The WS algorithm was run with N=2500, m0=25 and p=0.2.(a) The subgraph centralityCS(i) curves of the WS small-world network, (b) mean subgraph centrality 〈CS(i)〉 curve of the WS small-world network.
(a)
(b)Figure 4
Relative deviations of subgraph centralitiesCS(i) of the WS small-world network model.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure3(a) with Figure 3(b), that the two figures look quite similar. This implies that in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small.(2)
Figure4 shows that the relative deviations of subgraph centralities are mostly located nearly, with up to ±0.025 errors, which are quite small. This phenomenon shows that the subgraph centralities of WS complex networks are insensitivite to the network connectivity characteristics; namely, in different realizations with the same size N, parameter m0, and rewiring probability p, the subgraph centrality curves are almost the same as shown in Figure 3. Thus, for an WS-type complex network, in order to estimate its subgraph centrality distribution, one does not need to know the detailed information about its specific connectivity topology but only needs to know the values of N, m0,  and p.(3)
IfN=2500 and m0 are both fixed but the rewiring probability p is increased, then the mean subgraph centrality curve has some gradual change in shape. The 〈CS(i)〉 increases as the rewiring probability p increases, as shown in Figure 5. This phenomenon shows that the rewiring probability p can be used to control the “regular" and “random” levels of the WS small-world network model, which is consistent with our understanding of the model [14]: when p is small, which means only a few edges are rewired, the network generated by the WS algorithm is more like a regular network; but, as p is increased, more edges will be rewired, so the generated network becomes more random; when p=1, every edge will be rewired; therefore, the WS small-world network model literally becomes an ER random-graph network. Thus, by tuning the value of p, one can obtain a transition from a completely regular network to a completely random network.Figure 5
The mean subgraph centrality〈CS(i)〉 curves of the WS small-world network with three rewiring probabilities p=0.2 (red circles), p=0.4 (green squares), and p=0.6 (blue diamonds). All networks have N=2500. All data are averaged over 50 networks.


### 3.3. BA Scale-Free Networks

The curves of the distributions of subgraph centralities, mean subgraph centralities, and the relative deviations are plotted in Figures6 and 7, respectively. It was shown [21] that scale-free characteristics of BA networks are independent of three parameters N, m0, and m. So the algorithm of BA model was run with N=2500, m0=5, and m=3.(a) Log-log plot of the subgraph centralityCS(i) in the BA scale-free network, (b) log-log plot of mean subgraph centrality 〈CS(i)〉 in the BA scale-free network.
(a)
(b)Figure 7
Relative deviations of subgraph centralitiesCS(i) of the BA scale-free network.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure6(a) with Figure 6(b), that the two figures look quite similar. This implies that, in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small.(2)
Figure7 shows that the relative deviations of subgraph centralities are mostly located nearly, with up to ±1 errors; I just found that the relative deviations of BA network are really much more sensitive than the other two kinds of networks. This phenomenon shows that the subgraph centralities of BA complex networks are insensitivite to the network connectivity characteristics; namely, in different realizations with the same size N, parameter m0, and m, the subgraph centralities curves are almost the same.(3)
Figure6 shows that there is a small number with high CS(i) nodes and a large number of low CS(i) nodes in network. This phenomenon shows the scale-free characteristics of BA networks.


## 3.1. ER Random-Graph Networks

The simulation results are plotted in Figure1(a), where the number of simulation runs on ER random-graph network model is 50, therefore totally 50 network realizations were generated by ER algorithm, and a total of 2500×50 subgraph centralities were plotted altogether in the same figure (they are not the averages of the subgraph centralities of the 50 simulations). Figure 1(b) shows the averages of the subgraph centralities of the ER model plotted in Figure 1(a). To quantify the variability of the subgraph centralities, the relative deviations defined by (6) were calculated and are plotted in Figure 2. The ER algorithm was run with N=2500 and p=0.08.(a) The subgraph centralityCS(i) curves of the ER model, (b) mean subgraph centrality 〈CS(i)〉 curve of the ER model.
(a)
(b)Figure 2
Relative deviations of subgraph centralitiesCS(i) of the ER model.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure1(a) with Figure 1(b), that the two figures look quite similar; namely, the actual values of each subgraph centrality in all individual runs and averages of the subgraph centralities are not much different. This implies that in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small. A phenomenon needs further investigation in the future.(2)
Figure2 shows that the relative deviations of subgraph centralities are mostly located nearby, with up to ±0.05 errors, which are quite small. This phenomenon shows that the subgraph centralities of ER complex networks are insensitive to the network connectivity characteristics; namely, in different realizations with the same size N and probability p, the subgraph centrality curves are almost the same as shown in Figure 1. Thus, for an ER-type complex network, in order to estimate its subgraph centrality distribution, one does not need to know the detailed information about its specific connectivity topology but only needs to know the values of N and p in general.


## 3.2.  WS Small-World Networks

Similar to the analysis of ER complex networks, Figure3 shows the plots of the curves of the distributions of subgraph centralities and mean subgraph centralities. Figure 4 shows the plot of the relative deviations. The WS algorithm was run with N=2500, m0=25 and p=0.2.(a) The subgraph centralityCS(i) curves of the WS small-world network, (b) mean subgraph centrality 〈CS(i)〉 curve of the WS small-world network.
(a)
(b)Figure 4
Relative deviations of subgraph centralitiesCS(i) of the WS small-world network model.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure3(a) with Figure 3(b), that the two figures look quite similar. This implies that in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small.(2)
Figure4 shows that the relative deviations of subgraph centralities are mostly located nearly, with up to ±0.025 errors, which are quite small. This phenomenon shows that the subgraph centralities of WS complex networks are insensitivite to the network connectivity characteristics; namely, in different realizations with the same size N, parameter m0, and rewiring probability p, the subgraph centrality curves are almost the same as shown in Figure 3. Thus, for an WS-type complex network, in order to estimate its subgraph centrality distribution, one does not need to know the detailed information about its specific connectivity topology but only needs to know the values of N, m0,  and p.(3)
IfN=2500 and m0 are both fixed but the rewiring probability p is increased, then the mean subgraph centrality curve has some gradual change in shape. The 〈CS(i)〉 increases as the rewiring probability p increases, as shown in Figure 5. This phenomenon shows that the rewiring probability p can be used to control the “regular" and “random” levels of the WS small-world network model, which is consistent with our understanding of the model [14]: when p is small, which means only a few edges are rewired, the network generated by the WS algorithm is more like a regular network; but, as p is increased, more edges will be rewired, so the generated network becomes more random; when p=1, every edge will be rewired; therefore, the WS small-world network model literally becomes an ER random-graph network. Thus, by tuning the value of p, one can obtain a transition from a completely regular network to a completely random network.Figure 5
The mean subgraph centrality〈CS(i)〉 curves of the WS small-world network with three rewiring probabilities p=0.2 (red circles), p=0.4 (green squares), and p=0.6 (blue diamonds). All networks have N=2500. All data are averaged over 50 networks.


## 3.3. BA Scale-Free Networks

The curves of the distributions of subgraph centralities, mean subgraph centralities, and the relative deviations are plotted in Figures6 and 7, respectively. It was shown [21] that scale-free characteristics of BA networks are independent of three parameters N, m0, and m. So the algorithm of BA model was run with N=2500, m0=5, and m=3.(a) Log-log plot of the subgraph centralityCS(i) in the BA scale-free network, (b) log-log plot of mean subgraph centrality 〈CS(i)〉 in the BA scale-free network.
(a)
(b)Figure 7
Relative deviations of subgraph centralitiesCS(i) of the BA scale-free network.The simulation results reveal the following observations.(1)
It is clear, from a comparison of Figure6(a) with Figure 6(b), that the two figures look quite similar. This implies that, in various realizations of the same type of network topology of the same size, the variation of their subgraph centralities is quite small.(2)
Figure7 shows that the relative deviations of subgraph centralities are mostly located nearly, with up to ±1 errors; I just found that the relative deviations of BA network are really much more sensitive than the other two kinds of networks. This phenomenon shows that the subgraph centralities of BA complex networks are insensitivite to the network connectivity characteristics; namely, in different realizations with the same size N, parameter m0, and m, the subgraph centralities curves are almost the same.(3)
Figure6 shows that there is a small number with high CS(i) nodes and a large number of low CS(i) nodes in network. This phenomenon shows the scale-free characteristics of BA networks.


## 4. Probability Distributions of Subgraph Centralities

In this section, the probability distributions of subgraph centrality are discussed for the aforementioned three different types of networks.


### 4.1. ER Random-Graph Networks

The simulation results are averaged over 50 network realizations. In Figure8, we plot the probability distributions of subgraph centrality of the ER random-graph model for different parameters.Probability distributions of subgraph centralityP(CS) and the fitting curve of gamma distribution for the ER network model. (a) P(CS) for N=2500 and p=0.08, gamma distribution with α=2.07 and β=0.28. (b) P(CS) for N=2500 and p=0.15, gamma distribution with α=1.74 and β=0.31. All networks have N=2500.
(a)
(b)The simulation results show that the plots ofP(CS) are quite similar under different parameters  p. We use P-P plots in IBM SPSS Statistics 20.0 to test these simulation data. The distributions like gamma distribution, it also looks like normal distribution, or t-distribution. We find that bias of the gamma distribution is minimum almost three distributions, so we conclude that the distributions of subgraph centrality follow the gamma distribution. Probability distributions of subgraph centrality P(CS) from these simulation data perfectly fit the gamma distribution, where P(CS) values are normalized; see Figure 8.


### 4.2. WS Small-World Networks

Similar to the simulation of ER complex networks, Figure9 shows the plot of the distributions of subgraph centrality under different parameters  p.(a) Probability distributions of subgraph centralityP(CS) in the WS network model with three rewiring probabilities p=0.2 (red circles), p=0.4 (green squares), and p=0.6 (blue diamonds). (b) Probability distributions of subgraph centrality P(CS) with p=0.6 and the fitting curve of gamma distribution with α=1.62 and β=0.33. All networks have N=2500.
(a)
(b)The simulation results reveal the following observations.(1)
Figure9(a) shows that the curves of P(CS) are very similar under different parameters  p in general, and yet meanwhile they also display different features. The distribution of subgraph centrality flattens and widens as the rewiring probability p increases. This phenomenon shows that the rewiring probability p can be used to control the “regular" and “random" levels of the WS small-world network model: when the rewiring probability p is small, which means only a few edges are rewired, the network generated by the WS algorithm is more like a regular network; but, as p is increased, more edges will be rewired, so the generated network becomes more random; when p=1, every edge will be rewired therefore the WS small-world network model literally becomes an ER random-graph network. This phenomenon shows that small worlds are hybrids—part  regular and part random. The topology of a small-world network should fall somewhere between that of regular network and random network. A small-world network is taller and thinner than the distribution of equivalent random network.(2)
From simulation results, we conclude that the distributions of subgraph centrality follow the gamma distribution. Probability distributions of subgraph centralityP(CS) from these simulation data perfectly fit the gamma distribution, where P(CS) values are normalized; see Figure 9(b).


### 4.3. BA Scale-Free Networks

The simulation results are averaged over 50 network realizations. In Figure10, we plot the cumulative distributions of subgraph centrality for different parameters  m.Figure 10
(Color online) Log-log plot of the cumulative distributions ofP(CS) for the BA network model with m=3 (blue circles) and m=5 (red squares). All networks have N=2500.From simulations, it is found that the cumulative distributions ofP(CS) display a power-law distribution with an exponential cutoff. The scale-free characteristics of CS(i) distribution can be explained as follows. CS(i) measures the number of times that a node participates in all subgraphs in the network, giving more weight to smaller subgraphs. Consequently, nodes with high CS(i) participate in large number of small subgraphs, such as connected triplets, triangles, squares, and so forth. The frequency of these nodes in the network is significantly higher than that of nodes participating in a small number of subgraphs or participating only in large subgraphs from which a fat tail distribution results.


## 4.1. ER Random-Graph Networks

The simulation results are averaged over 50 network realizations. In Figure8, we plot the probability distributions of subgraph centrality of the ER random-graph model for different parameters.Probability distributions of subgraph centralityP(CS) and the fitting curve of gamma distribution for the ER network model. (a) P(CS) for N=2500 and p=0.08, gamma distribution with α=2.07 and β=0.28. (b) P(CS) for N=2500 and p=0.15, gamma distribution with α=1.74 and β=0.31. All networks have N=2500.
(a)
(b)The simulation results show that the plots ofP(CS) are quite similar under different parameters  p. We use P-P plots in IBM SPSS Statistics 20.0 to test these simulation data. The distributions like gamma distribution, it also looks like normal distribution, or t-distribution. We find that bias of the gamma distribution is minimum almost three distributions, so we conclude that the distributions of subgraph centrality follow the gamma distribution. Probability distributions of subgraph centrality P(CS) from these simulation data perfectly fit the gamma distribution, where P(CS) values are normalized; see Figure 8.


## 4.2. WS Small-World Networks

Similar to the simulation of ER complex networks, Figure9 shows the plot of the distributions of subgraph centrality under different parameters  p.(a) Probability distributions of subgraph centralityP(CS) in the WS network model with three rewiring probabilities p=0.2 (red circles), p=0.4 (green squares), and p=0.6 (blue diamonds). (b) Probability distributions of subgraph centrality P(CS) with p=0.6 and the fitting curve of gamma distribution with α=1.62 and β=0.33. All networks have N=2500.
(a)
(b)The simulation results reveal the following observations.(1)
Figure9(a) shows that the curves of P(CS) are very similar under different parameters  p in general, and yet meanwhile they also display different features. The distribution of subgraph centrality flattens and widens as the rewiring probability p increases. This phenomenon shows that the rewiring probability p can be used to control the “regular" and “random" levels of the WS small-world network model: when the rewiring probability p is small, which means only a few edges are rewired, the network generated by the WS algorithm is more like a regular network; but, as p is increased, more edges will be rewired, so the generated network becomes more random; when p=1, every edge will be rewired therefore the WS small-world network model literally becomes an ER random-graph network. This phenomenon shows that small worlds are hybrids—part  regular and part random. The topology of a small-world network should fall somewhere between that of regular network and random network. A small-world network is taller and thinner than the distribution of equivalent random network.(2)
From simulation results, we conclude that the distributions of subgraph centrality follow the gamma distribution. Probability distributions of subgraph centralityP(CS) from these simulation data perfectly fit the gamma distribution, where P(CS) values are normalized; see Figure 9(b).


## 4.3. BA Scale-Free Networks

The simulation results are averaged over 50 network realizations. In Figure10, we plot the cumulative distributions of subgraph centrality for different parameters  m.Figure 10
(Color online) Log-log plot of the cumulative distributions ofP(CS) for the BA network model with m=3 (blue circles) and m=5 (red squares). All networks have N=2500.From simulations, it is found that the cumulative distributions ofP(CS) display a power-law distribution with an exponential cutoff. The scale-free characteristics of CS(i) distribution can be explained as follows. CS(i) measures the number of times that a node participates in all subgraphs in the network, giving more weight to smaller subgraphs. Consequently, nodes with high CS(i) participate in large number of small subgraphs, such as connected triplets, triangles, squares, and so forth. The frequency of these nodes in the network is significantly higher than that of nodes participating in a small number of subgraphs or participating only in large subgraphs from which a fat tail distribution results.


## 5. Conclusion

In this paper, both subgraph centrality distributions in the increasing order and probability distributions of subgraph centrality for three representative complex network models have been carefully investigated through extensive theory-guided simulations, including the ER random-graph networks, WS small-world networks, and BA scale-free networks. The results show that these three very different types of complex networks share some common features; particularly, similarities in the subgraph centrality distributions in the increasing order are all insensitive to the network connectivity characteristics. It also shows that the probability distributions of subgraph centrality of the ER and of the WS models both follow the gamma distribution, and the BA scale-free networks exhibit a power-law distribution with an exponential cutoff.



---

*Source: 473248-2013-11-13.xml*