^{1,2}

^{3}

^{2}

^{2}

^{1}

^{2}

^{3}

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.

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 [

It has been observed that not only triangles but also other subgraphs are significant in real networks. We say that a graph

Another kind of local characterization of networks is made numerically by using one of several measures known as “centrality” [

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 [

Among the many representative network models, the classical Erdös-Rényi (ER) random-graph 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

The rest of this paper is organized as follows. In Section

Subgraph centrality characterizes the participation of each node in all subgraphs in a network. The subgraph centrality of node

By a series of deducing, the subgraph centrality for all

A global characterization of the network can be carried out by means of the average subgraph centrality, denoted by

It was shown that

The ER random-graph network is generated by the following steps (ER algorithm); see [

Start with

Pick up every pair of nodes and connect them by edge with probability

The WS small-world network model is generated by the following steps (WS algorithm); see [

Start with a regular nearest-neighboring network with

At every step, for each node, operate on its connections to its

The BA scale-free network model is generated by the following steps (BA algorithm); see [

Growth: starting from a small fully connected network of nodes

Preferential attachment: the probability of a new link to end up in an existing node

In this section, we discuss the distributions of subgraph centralities calculated by (

The simulation results are plotted in Figure

(a) The subgraph centrality

Relative deviations of subgraph centralities

The simulation results reveal the following observations.

It is clear, from a comparison of Figure

Figure

Similar to the analysis of ER complex networks, Figure

(a) The subgraph centrality

Relative deviations of subgraph centralities

The simulation results reveal the following observations.

It is clear, from a comparison of Figure

Figure

If

The mean subgraph centrality

The curves of the distributions of subgraph centralities, mean subgraph centralities, and the relative deviations are plotted in Figures

(a) Log-log plot of the subgraph centrality

Relative deviations of subgraph centralities

The simulation results reveal the following observations.

It is clear, from a comparison of Figure

Figure

Figure

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

The simulation results are averaged over 50 network realizations. In Figure

Probability distributions of subgraph centrality

The simulation results show that the plots of

Similar to the simulation of ER complex networks, Figure

(a) Probability distributions of subgraph centrality

The simulation results reveal the following observations.

Figure

From simulation results, we conclude that the distributions of subgraph centrality follow the gamma distribution. Probability distributions of subgraph centrality

The simulation results are averaged over 50 network realizations. In Figure

(Color online) Log-log plot of the cumulative distributions of

From simulations, it is found that the cumulative distributions of

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.

The authors declare that there is no conflict of interests regarding the publication of this paper.

The research is supported by the National Science Foundation of China (nos. 61164005, 60863006), the National Basic Research Program of China (no. 2010CB334708), and the Program for Changjiang Scholars and Innovative Research Team in University (no. IRT1068).