See discussions, stats, and author profiles for this publication at: [Link]

net/publication/265552563

A Simple Model Clarifies the Complicated Relationships of Complex Networks

Article in Scientific Reports · August 2014

DOI: 10.1038/srep06197

CITATIONS READS

23 2,287

7 authors, including:

Bojin Zheng Hongrun Wu

South Central Minzu University Wuhan University
40 PUBLICATIONS 239 CITATIONS 43 PUBLICATIONS 858 CITATIONS

SEE PROFILE SEE PROFILE

Li Kuang Jianmin Wang

Huawei Technologies Soochow University
18 PUBLICATIONS 271 CITATIONS 346 PUBLICATIONS 28,196 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Bojin Zheng on 19 September 2014.

The user has requested enhancement of the downloaded file.

 OPEN A simple model clarifies the complicated
SUBJECT AREAS:
relationships of complex networks
COMPLEX NETWORKS Bojin Zheng1,2,3, Hongrun Wu3, Li Kuang3, Jun Qin1, Wenhua Du1, Jianmin Wang4 & Deyi Li4
APPLIED MATHEMATICS
COMPUTATIONAL SCIENCE 1
College of Computer Science, South-Central University For Nationalities, Wuhan 430074, China, 2State Key Laboratory of
Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China, 3Computer
School, Wuhan University, Wuhan 430072, China, 4School of Software, Tsinghua University, Beijing 100084, China.
Received
3 July 2013
Real-world networks such as the Internet and WWW have many common traits. Until now, hundreds of
Accepted
models were proposed to characterize these traits for understanding the networks. Because different models
31 July 2014 used very different mechanisms, it is widely believed that these traits origin from different causes. However,
Published we find that a simple model based on optimisation can produce many traits, including scale-free,
27 August 2014 small-world, ultra small-world, Delta-distribution, compact, fractal, regular and random networks.
Moreover, by revising the proposed model, the community-structure networks are generated. By this model
and the revised versions, the complicated relationships of complex networks are illustrated. The model
brings a new universal perspective to the understanding of complex networks and provide a universal
Correspondence and method to model complex networks from the viewpoint of optimisation.
requests for materials
should be addressed to

C
omplex networks have been found to be efficient and effective in illuminating various biological, social,
B.Z. (zhengbojin@
and technological systems1–4, for examples, the Internet5,6, WWW and protein-interaction networks7.
[Link]) Through the efforts of many scientists, numerous traits of complex networks, such as the scale-free
property8, the small-world effect9–11, the community structure8 and the fractal structure7,12, have been discovered.
Such traits are the foundation to model the real-world networks for understanding their origins and mechanisms.
To explain such traits, hundreds of models have been proposed. For example, the Watts-Strogatz (WS) model9
illustrates the origin of the small-world effect and demonstrates the relationships of small-world networks,
random networks and regular networks: i.e., small-world networks are an intermediate form between random
networks and regular networks. The Barabási-Albert (BA) model5,13 demonstrates the scale-free property of
networks, and Amaral et al.14 clarified the relationship between scale-free networks and small-world networks.
Li et al.15 demonstrated the relationship between scale-free networks and random networks through the locality
hypothesis. Song et al.7,12 proposed a method to define fractal networks, which involves the relationship between
small-world networks and fractal networks.
Generally speaking, based on current knowledge, complex networks can be categorized into many types
according to the traits, such as random15,16, regular, scale-free13, small-world9,11, ultra small-world10, community-
structure, compact17, fractal, and Delta-distribution networks. However, the relationships among these types of
complex networks only have been partially explored.
Considering the number of the proposed models10,12,15,16,18–20 that explains the types of complex networks, it
is reasonable to believe that these types of complex networks would have different causes: different types of
complex networks originate from different origins and different mechanisms. However, when a network has
multiple traits, multiple different mechanisms should be used to explain their corresponding traits; and there
should be an assembling mechanism to combine these mechanisms of traits together. The combinatorics
would make such a schema quite complicated, no matter that there are hundreds of different mechanisms for
only one trait. People has to solve the competition of these mechanisms as well, if we take the Occam’s Razor
for granted.
Here, by using only three common measures, the degree of nodes, the degree of edges, and the average shortest
path length, we implemented a simple model based on optimisation that can produce random, regular, scale-free,
small-world, ultra small-world, compact, fractal and Delta-distribution networks. Moreover, with a slight revi-
sion, the model also can produce community-structure networks. Furthermore, all traits and their combinations
can be explained by revising the proposed model. These results suggest that we can illustrate the relationships of
various types of complex networks under the framework of optimisation, and bring a new perspective on
understanding the real-world networks such as the Internet and WWW.

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 1

 [Link]/scientificreports

Here, xi is the degree of node i, y for the average shortest path length,
d=3 d=3
B B A for the evolving network, and c/xmin/a/b/N are non-negative con-
1 3 stants. Furthermore, xmin is the minimum degree of the nodes
d=3 d=4 d=3 d=4 throughout the entire network. The function dij is equal to 1 when
A
1 C A 4 C
1
a link between node i and node j exists; or it equals 0.
m=3 m=12 5
d=5 d=5 In equation (1), the proposed model is a bi-objective optimisation
D D problem. The proposed model has feasible solutions, each solution
indicating a network, and every best solution is a desired resultant
(a) (b)
network.
d=3 d=3 As to single-objective optimisation problems, the concept of ‘‘the
B b B best solution’’ is easy to understand. If one solution has the largest
3×
3 a
3 ×3 function value for a maximisation problem or the smallest function
d=3 d=4 d=3 d=4
3×4 C A
3a×4b C value for a minimisation problem, then it is the best solution.
A
3× 3×
a
However, bi-objective optimisation problems are quite different22.
m=36 5 m 5b
d=5 d=5 Commonly, the solution with the best function value for the first
D D objective is far from the best for the second objective. Therefore, the
(c) (d)
concept of ‘‘the best solution’’ must be extended in bi-objective opti-
misation problems.
Figure 1 | Definitions on the edge degree. (a) In the simplest case, the The simplest way to extend this concept is to define ‘‘the best
edge degree of every edge is 1, irrelative to the degrees of both nodes at the solution’’ as ‘‘no solution is better at satisfying both objectives’’.
ends of the edge. (b) The edge degrees of node A are the degrees of the This extended concept often results in multiple best solutions.
neighbors, irrelative to the degree of node A itself. Here, regarding the Because none of the best solutions are dominated by a feasible solu-
nodes on two ends of an edge, the degrees of an identical edge relative to the tion, they form a non-dominant set, which is known as the ‘‘Pareto
different nodes are different. (c) The edge degrees are the product of the front’’, a term coined by David E. Goldberg23 in honor of V. Pareto24.
degrees of nodes on the ends. (d) In the general form, the edge degree is the By the way, another great achievement of V. Pareto is the finding of
product of the power functions of the degrees of both nodes at the ends. the power law phenomenon in the wealth distribution. For more
The previous cases are special cases with different values for a and b. detailed information on the Pareto front, please refer to the SI.
For any given parameter setting, there is a Pareto front for the
Results proposed model. When optimisation algorithms are used to solve the
A network or graph is a set of nodes with edges. Regarding the nodes, proposed model, they actually obtain sampling points of Pareto
the degree is the primary measurement. As to the edges, the concept front. According to these sampling points, the resultant networks
of edge degree has been defined in various ways. To characterize the can be constructed.
holistic features of the entire network, the average shortest path With the implementation of different parameters, the obtained
length is widely used21. These three measures are the most commonly network would exhibit different traits and would correspond to dif-
used measures in the study of complex networks. ferent types. Because theses types are obtained for the same model,
It may appear that these measures have no bearing on the resultant the origin of these types and the relationships of the types can be
types of complex networks. However, our model shows that there is determined.
an intrinsic relationship among them. The types are determined by
three common measures. Types of networks. Researchers have observed many types of
complex networks. Here, we discuss the most common types: i.e.,
The model. As mentioned above, the model requires a definition on the scale-free, small-world, ultra small-world, fractal, community-
the edge degree. Because the degree is the most commonly used structure, compact, Delta-distribution, random, and regular
measure of nodes, the degree of an edge could be defined as a networks. Here, we theoretically demonstrate that these common
function of the degrees of the two nodes at its ends. Here, the edge complex networks can be produced by the model described above.
degree is defined as the product of the power function of the degrees
Scale-free network. The most popular theoretical description of scale-
of two nodes at both ends (see Fig. 1).
free networks is the BA model5. However, if we treat the node degrees
Based on the definitions above, the proposed model can be stated as a random variable, the proposed model can also produce scale-free
as follows. networks. Obviously, some scale-free networks that satisfy the equa-
A connected undirected network evolves to minimise the sum- tion (1) are in the Pareto front, while others are not. Here, we dem-
mation of the degrees of the nodes and to maximise the summation onstrate that the proposed model can produce scale-free networks in
of the degrees of the edges with a constant average shortest path length. the Pareto front, which we refer to as optimal scale-free networks.
That is, every network is evolving and should be optimised to When discussing the scale-free property or and random networks,
achieve two objectives with a constraint on its average shortest path we actually are discussing the degree distribution, i.e., treat the degree
length. values as samples of a random variable. Therefore, here we treat xi
Mathematically, this model is expressed by equation (1). and xj as samples of the random variable X. Because the samples are
8 independent and identically distributed, based on the Lagrangian
> P
N
>
> minF1 ðAÞ~ xi relaxation method25, equation (1) can be rewritten as equation (2).
>
< i~1
! 8
> >
> min f1 ðxi Þ~xi zhðy{cÞ2
>
> PN P
N
a b < !{1
>
: max F2 ðAÞ~ xi xj dij
> min f ðx Þ~ P xa xb d
N
i~1 j~1 ð1Þ >
: 2 i i j ij zhðy{cÞ2 ð2Þ
j~1
s:t:
y~c s:t: Nwxi §xmin

Nwxi §xmin Here, h is an arbitrary positive real number.

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 2

 [Link]/scientificreports

Because xi and xj come from the same random variable, we use xi to networks. When c does not constrain the forms of the networks, we
approximate xj, so f2 can be further rewritten as equation (3). say that c is proper.
A proper c depends on the constant xmin. From equation (8),
f2 ðxi Þ%xi - ð1 z a z bÞ zhðy{cÞ2 ð3Þ which is the continuous version of the power law distribution, when
Equation (3) has an analytic solution of a Pareto front26, which can be c is determined, the probability of X depends on the constant xmin,
rewritten as equation (4), when y 5 c, where c does not constraint the so the proper c would decrease as xmin increases.
 
random variable X through the validation of the network topology c{1 X {c
structure. pð X Þ~ ð8Þ
xmin xmin
f2 ðxi Þ~ðxi Þ{ð1zazbÞ ð4Þ According to the definition of F2, when some hub nodes link to
other hub nodes, F2 is maximised. When F2 is maximised, if c is
Because f2 is a function that can be defined on the sample space, we
proper, and the hub nodes tend to link together, the obtained
can obtain equation (5).
networks would have a single center. Because hub nodes are the
pð X Þ~Cð X Þ{ð1zazbÞ ð5Þ similar nodes to link together, the obtained network is hierarch-
ical: i.e., the obtained network is onion-structure27,28 alike or
Here, C is a constant to normalise p(X) and satisfies the equation (6). compact. In such networks, the hub nodes tend to form an inter-
1 connected core, and the non-hub nodes with similar degree
C~ N{1 ð6Þ link together and encircle the core hierarchically. Moreover, the
P
ð X Þ{ð1zazbÞ lower the degree of the node, the farther the node stay from the
X~1 center.
Equation (5) indicates that under the condition that a ? 0 or b ? 0 When c decreases to force the degree distribution away from that
and when c does not constraint the distribution of X, i.e., is proper, of a scale-free network, the hub nodes collect more edges until the
the network is scale-free, and the exponent of the degree distribution network finally becomes a star-like or Delta-distribution network.
obeys equation (7). Fractal network. Scale-free networks have a degree distribution of the
c~1zazb ð7Þ form p(k) , k2c. According to the definition of self-similarity (i.e.,
when an entire object is exactly or approximately similar to a part of
According to the definition of the optimal scale-free network, all itself), scale-free networks can be regarded as self-similar with
optimal scale-free networks are the best solutions of this model. respect to the probability of the degree or can exhibit a probabilistic
Regarding the non-optimal scale-free networks, when F1 is fixed, similarity when we treat p(k) as a function.
F2 is not optimal: i.e., the hub nodes are not linked together. When Alternatively, Song et al. proposed a definition on fractality of
the hub nodes are divided into two or more groups, the network is complex networks over the length. In the box covering method, if
called a community-structure network. Thus, the non-optimal scale- the box number NB has a power law relationship with the maximum
free networks are actually community-structure networks or trans- box diameter lB, as shown in Equation (9), then the networks present
itional forms between optimal scale-free networks and community- fractality or similarity over different length scales. Here, the fractality
structure networks. actually is a type of structural similarity.
Community-structure network. Community-structure scale-free net- NB *lB {dB ð9Þ
works can also be depicted by this model with a slight modification.
With this modification, community-structure scale-free networks Obviously, structural similarity over the length, which is expected in
become the best solutions of the new model. a fractal network, is different to the definition of probabilistic sim-
Community-structure scale-free networks are non-optimal scale- ilarity over node degrees.
free networks. Assume that there are two identical communities Additionally, the diameter of the whole network is often positively
linked by only one edge; when certain edges in no. 1 community relative to average shortest path length, hence a fractal network is
are moved to no. 2, F2 of the entire network can increase as the often expected to exhibit a power relationship between the node
number and average shortest path length, and this relationship is
average shortest path length decreases, and simultaneously, no. 1
expressed in Equation (10).
community loses some edges, resulting in an increased average short-
est path length; that is, we can reach a solution that exhibits a larger F2 c*N 1 = w ðww1Þ ð10Þ
but with the same c. Therefore, the community-structure scale-free
networks are non-optimal. Equation (10) implies that the average shortest path length should be
To produce optimal community-structure scale-free networks, the quite large. In fact, because c depends on xmin, the average shortest
proposed model should be modified. path length of the network should change with xmin. When xmin
In the real world, community structure often relates to similarity increases, c of the fractal network can be smaller than ln(N). Here, the
distances, such as geographic distances, cultural distances or cognit- qualitative relationships of N, xmin, c and w require further
ive distances. By taking these distances into consideration, optimal investigation.
community-structure scale-free networks can be produced by an In the proposed model, because c ranges from 1 to N 2 1, the
enhanced model (see the SI). This result indicates the origin of the average shortest path length of the fractal network must be included.
community-structure scale-free networks. When c is in the ranges of the fractal networks, the scale-free net-
The modified model here can produce typical networks with com- works should be stretched. That is, a larger value of c forces some
munity structures. To address the other non-optimal scale-free net- marginal nodes away from the center of network. When applying the
works, more constraints must be added. We leave these issues to box covering method, the larger c, i.e., often the larger diameter, may
future work. result in a power law relation between the box number and the
maximum box diameter possible, thereby result in structural
Compact network and Delta-distribution network. According to similarity.
equation (1), the average shortest path length of the network is a More detailed information and the simulation results on fractal
hard constraint, so the constant c can alter the forms of the resultant networks are discussed in the SI.

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 3

 [Link]/scientificreports

Figure 2 | Typical networks and their degree distributions. The upper box in each subfigure shows the degree distribution of the network in the
lower box. The degree distributions are plotted in a log-log coordinate system. (a) This resultant network is a compact network, whose c is smaller than
ln(N). (b) This resultant network demonstrates a network with two equivalent communities. (c) This beautiful network is a fractal network. (d) This
resultant network is also a compact network but with denser edges. (e) This resultant network is a community-structure network. Each community has
denser edges. (f) This resultant network is a fractal network. The community-structure networks (b) and (e) are generated by the revised model in the SI,
and the networks with multiple communities are shown in the SI; the fractality of (c) and (f) are also shown in the SI.

Small-world network and ultra small-world network. The small- The Simulation. Having theoretically analysed the produced types of
world network exhibits a clear feature in which the average shortest networks, we now discuss the simulation results.
path length is approximately ln(N), in addition to a larger clustering To solve this bi-objective optimisation problem by computer
coefficient9. The latter feature is easily satisfied. Hence, we discuss the simulations, we use multi-objective optimisation algorithms.
previous feature only. Because F1 is discrete, the histogram method (see the SI) is a suitable
According to the definition of the small-world property, when the approach for transferring this problem to a single-objective optimi-
average shortest path length of the obtained network is given by sation problem, that is, first fix F1, and only optimise F2.
c^lnðN Þ, the network is considered a small-world network. Furthermore, to solve F2, we employ a greedy strategy. That is, we
Moreover, when c^lnðlnðN ÞÞ, the network is an ultra small-world randomly generate a network and then continue to randomly change
network. For any given network, the number of nodes determined an edge and update the network to a better solution. That is, if the
the maximum of degree values, i.e., the maximum of random variable change leads to a better F2 and more closely approximates the average
X. According to equation (8), when xmin increases, if we also shortest path, then we accept the change; otherwise, we refuse the
increase the maximum of degree values, then we can keep the c fixed. change. Besides, the proposed algorithm can be used to generate
The increase of xmin and maximum of degree values means more complex networks with arbitrary traits or the combinations of traits.
edges in a network, and more edges means smaller average shortest For more information, see the SI.
path length, that is, the ultra small-world property could emerge Based on the method described above, we obtained various net-
under some circumstances. works using different parameters. Because this optimisation algo-
Random network. When a 5 b 5 0, F2 reduces to F1. Because F1 rithm is a random algorithm, we performed this algorithm ten
should be minimised and F2 should be maximised, the minimisation times to verify its robustness. All of the runs that used the same
of F1 will completely violate the maximisation of F2, such that every parameters generated similar results; thus, only the results obtained
solution would belong to the Pareto front. Therefore, the resulting from the first run are shown (Fig. 2). Because we only used the greedy
networks are random if c does not constraint the distribution of X. strategy, the resultant networks are local optimal solutions, not glo-
When c is small and closes to 1, the network approximates a Delta- bal optimal solutions. Although heuristic algorithms such as the
distribution network. When c is large, some nodes are forced to simulated annealing algorithm30 can obtain the global optimal solu-
depart away from the denser center such that the degree distribution tions, the computation time would be longer. Therefore we used the
resembles the power law distribution, with the amplitude ranging greedy strategy to obtain satisfactory results.
across several magnitude. These results may imply a desirable study According to the theoretical analysis, the exponents of the degree
on the randomness and Zipf’s-law-like distribution29. distributions of the obtained networks depend on a and b; therefore,

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 4

 [Link]/scientificreports

complete network small world network

Table 1 | The parameters and results of selected networks.E is the
fixed value of F1, c9 is the exponent of the obtained network, y is
Community-structured network
the actual average shortest path of the obtained network
Delta distribution network
No. E c xmin c9 y Compact network
(a) 762 3.9 2 2.10 3.9 Fractal network
6
(b) 762 5.5 2 2.11 5.5
(c) 762 7 2 2.13 7 5
(d) 1157 3.1 3 2.16 3.1
(e) 1157 4.5 3 2.19 4.5 4 Maximum of average shortest path
(f) 1157 5.0 3 2.28 5.0

xmin
3
we designed 3 classes of experiments, with with a 5 0 and b 5 0, a 5
0 and b 5 1, a 5 1 and b 5 1, respectively. Because xmin is related to 2
c, we designed 3 sub-classes of experiments, with xmin 5 1, 2, 3 for
each of the classes. For each subclass, we investigated various values
of c. To show the generated networks clearly, the number of nodes N
1
in the simulations is set as 300. Also the simulations with larger size,
the number of nodes with 1500, 3483 and 18000, are reported in SI. c=1 c=ln(N) c=(N+1)/3
From the experimental results, we chose some typical results to average shortest path c
report in the SI. Here, we selected 6 typical networks with c 5 2(a 5
0, b 5 1); the parameters and results are reported in Table 1, and the Figure 3 | The schematic map on the relationships among various
resultant topology is shown in Fig. 2. complex networks. This figure assumes c 5 2. When c varies, this figure
Fig. 2 shows the compact, community-structure and fractal net- would also vary slightly. When c 5 1, the network is the complete network.
works. The rows of the sub-figures show the effect of c. When c When c 5 1, the generated network will be a complete network. With xmin
increases, the network type changes from compact to fractal. The 5 1, when c increases starting from 1, firstly the resultant network is a
columns of the sub-figures show the effect of xmin. When xmin delta-distribution network; when c increases continuously, the resultant
increases, the network average shortest path length for the same type network is a compact network; when c increases continuously, the
decreases. Besides, we can see that the fractal networks here demon- resultant network can be community-structure scale-free network if
strated the hub aggregation behaviors. considering the similarity distance; when c increases continuously, the
The results in Table 1 and Fig. 2 indicate that the obtained net- resultant network is fractal network; when c achieves the maximum, the
works fit the power law distributions31. Besides, statistical evaluations resultant network is a linear regular network; when c 5 ln(N), the resultant
on the fitness of the distribution of resultant networks are also network is a small-world scale-free network. When xmin 5 2 and the other
reported in SI. As shown in Table 1, the exponents of the networks parameters keep the same, the order of the types of networks remains the
are approximately equal to the expected values, and the expected same, but the spectral line(the positions of c) shift left and the ranges on c
average shortest path length were also obtained. decrease. For example, the generated network is small-world network
Moreover, we observed that the community-structure networks when xmin 5 1 and c 5 ln(N), but when xmin 5 3 and c 5 ln(N), the
exhibit a wide range of values of c because they can change the link(s) network changes to be fractal network, and the result is shown as Fig. 2(f).
between the communities to adapt to the topological distance. When So when xmin changes, the types also change.
c is smaller, the link can connect the central nodes of the communit-
ies; when c is larger, the link can connect two marginal nodes in distribution network, compact network, community-structure, frac-
different communities. For fractal networks, when c reaches a certain tal network. The other parameters, xmin and c also affect the types of
value, the network is stretched. As c increases, the network first networks. When xmin increase yet the other parameters keep the
exhibits many circles and then becomes linear with a head that exhi- same, the sequence for the types of networks remains the same, but
bits dense nodes and edges. the spectral line shift left and the ranges of network types on c
In general, this model can generate various types of networks, decrease. The schematic map on c 5 3 is shown in SI.
including small-world, ultra small-world, scale-free, community- Based on the proposed model, the scale-free network plays a key
structure, and compact networks. Some types of the obtained net- and central role, and scale-free networks can be categorized into
works are strongly dependent on the average shortest path length c. several classes. First, the scale-free networks can be divided into
However, because there are no accurate definitions for the various two types, optimal and non-optimal. Optimal scale-free networks
types of networks, we cannot determine an accurate c for each type include the ultra small-world, small-world, compact, and fractal net-
from the experiments; we can only determine the relative relation- works, which are controlled by the average shortest path length
ships between the types and the parameters. For more details on the constraint. Outside of the optimal scale-free networks but in the
results, please refer to the SI. Pareto front, there are the Delta-distribution and regular net-
works. Regarding the non-optimal scale-free networks, there are
Discussion community-structure networks and transitional forms between
According to the simulation and theoretical results, the relationships optimal scale-free networks and community-structure networks.
of complex networks can be illustrated under the framework of the Moreover, scale-free networks can be classified by an exponent. When
proposed model. the exponent is larger than 1, the resulting networks are scale-free.
Here, we assume that N 5 300, c 5 2 and show a schematic map of However, when the exponent equals 1, the networks can be random.
the relationships in Fig. 3. When N or c changes, the schematic map In general, we demonstrated that a simple model can produce
also changes. many common types of complex networks, including scale-free,
From Fig. 3, we can see that the average shortest path length can be small-world, ultra small-world, community-structure, compact,
regarded as a spectral line to discern the types of networks. With the fractal, Delta-distribution, regular and random networks in this
increase of c, the order of the types is complete network, delta- paper. Our results indicate that three key measures can determine

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 5

 [Link]/scientificreports

many types of complex networks. Moreover, because these types 16. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D.-U. Complex
networks: structure and dynamics. Phys. Rep. 424, 175–308 (2006).
originate from the same model, their relationships can be illustrated
17. Zheng, B., Huang, D., Li, D., Chen, G. & Lan, W. Some scale-free networks could
under the framework of the proposed model. be robust under the selective node attacks. Europhys. Lett. 94, 28010 (2011).
The proposed model brings a new perspective for understanding 18. Guimerà, R., Sales-pardo, M. & Amaral, L. A. N. Classes of complex networks
the complex networks and a new paradigm for distinguishing the defined by role-to-role connectivity profiles. Nat. Phys. 3, 63–69 (2007).
explanations of origins and mechanisms. When the proposed model 19. Newman, M. E. J. Power laws, Pareto distributions and Zipf’s law. Contemp. Phys.
46, 323–351 (2005).
is used to describe a certain complex network, it provides only one 20. Amaral, L. A. N. & Ottino, J. M. Complex networks: Augmenting the framework
explanation on the origin and leaves the explanations of the mechan- for the study of complex systems. Eur. Phys. J. B. 38, 1434–6028 (2004).
isms to the optimisation algorithms. For instance, if we use a genetic 21. Holme, P. & Kim, B. J. Attack vulnerability of complex networks. Phys. Rev. E. 65,
algorithm to solve the proposed model, then the genetic mechanism 056109 (2002).
(or evolutionary mechanism) can be regarded as the mechanism of 22. Schaffer, J. Multiple Objective Optimization with Vector Evaluated Genetic
Algorithms. In Proceedings of the First International Conference on Genetic
the modeled complex network. That is, the mechanisms of complex Algorithms, 93–100 (1985).
networks can be diverse while still representing similar phenomena. 23. Jeffrey, H., Nicholas, N. & David, E. G. A Niched Pareto Genetic Algorithm for
Besides, physicists have used the optimisation to explain the world Multiobjective Optimization. In Proceedings of the First IEEE Conference on
for centuries, for examples, the Fermat principle and the principle of Evolutionary Computation, IEEE World Congress on Computational Intelligence,
vol. 1, 82–87 (Piscataway, New Jersey, 1994).
minimum free energy etc.. Here our model is another example. By 24. Pareto, V. Cours d’Economie Politique (Droz, Geneva, 1896).
the optimisation method, we can characterize all the traits and their 25. Bertsekas, D. P. Nonlinear Programming: 2nd Edition (Athena Scientific, 1999).
combinations, so the optimisation provides a universal method to 26. Li, H. & Zhang, Q. Multiobjective Optimization Problems With Complicated
model the real-world networks such as the Internet, WWW and Pareto Sets, MOEA/D and NSGA-II. IEEE Trans. Evolut. Comput. 13, 284–302
protein-interaction networks. The ideal modeling networks gener- (2009).
27. Schneider, C. M., Moreira, A. A., José, S. Andrade, J., Havlin, S. & Herrmann, H. J.
ated by this universal method are useful of exploring the dynamics on Mitigation of malicious attacks on networks. Proc. Natl. Acad. Sci. USA 108,
complex networks, such as the synchronization, epidemic spreading 3838–3841 (2011).
and gaming. 28. Wu, Z. & Holme, P. Onion structure and network robustness. Phys. Rev. E. 84,
026106 (2011).
29. Li, W. Random texts exhibit Zipf’s-law-like word frequency distribution. IEEE
Methods Trans. Inf. Theory 38, 1842–1845 (1992).
This paper first proposed an optimisation model based on three commonly used 30. Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by Simulated
measures, i.e., the node degree, the edge degree and the average shortest path length. Annealing. Science 220, 671–680 (1983).
To solve this optimisation model, an algorithm with the greedy strategy was pro- 31. Clauset, A., Shalizi, C. R. & Newman, M. E. Power-law distributions in empirical
posed. To obtain complex networks with larger sizes, a fast but specific algorithm was data. SIAM Rev. 51, 661–703 (2009).
proposed. When solved this optimisation model, complex networks with different
traits were obtained. According to the parameter settings of the proposed model, the
relationships of traits of complex networks were illustrated. The details please refer to
the SI.
Acknowledgments
We are grateful to Oskar Burger, Chunlai Zhou, Aimin Zhou, Baobin Wang, Weiwu Wang,
1. Newman, M. E. J. the structure and function of complex networks. SIAM Rev. 45, Yanni Han, Jun Hu, Yuanxiang Li, Guishen Chen, Haisu Zhang, Yutao Ma, Jun’an Lu, Di
167–256 (2003). Ning, and Xianjun Shen for many discussions, Shenzhan Li, Fei Xu, and Biao Wang for their
2. Newman, M. The structure of scientific collaboration networks. Proc. Natl. Acad. experimental assistance, and Yang Yang, Alan C. and Kristi H. for language assistance in
Sci. USA 98, 404–409 (2001). writing this paper. B.Z. thanks the National Basic Research Program of China (No.
3. Wasserman, S. & Faust, K. Social Network Analysis (Cambridge University Press, 2014CB340401) and the State Key Laboratory of Networking and Switching Technology
1994). (No. SKLNST-2010-1-04) and the State Key Laboratory of Software Engineering (No.
4. Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The large-scale SKLSE2012-09-15) and the China Scholarship Council for the supports. D.L. thanks the
organization of metabolic networks. Nature 407, 651–654 (2000). National Natural Science Foundation of China (No. 61273213 and 61272111) for the
5. Barabási, A. L. & Albert, R. Emergence of scaling in random networks. Science 286, supports. J.Q. is grateful for support from the Fundamental Research Funds for the Central
509–512 (1999). Universities (No. CZY12032 and CZY13010).
6. Li, L., Alderson, D., Doyle, J. C. & Willinger, W. Towards a theory of scale-free
graphs: Definition, properties, and implications. Internet Mathematics 2, 431–523 Author contributions
(2005). B.Z. designed research; B.Z. and H.W. performed research; B.Z., H.W., L.K. and W.D.
7. Song, C., Havlin, S. & Makse, H. A. Self-similarity of complex networks. Nature analyzed data and performed simulations; B.Z., J.Q., J.W. and D.L. wrote the manuscript; all
433, 392–395 (2005). authors discussed the results and reviewed the manuscript.
8. Girvan, M. & Newman, M. E. J. Community structure in social and biological
networks. Proc. Natl. Acad. Sci. USA 99, 8271–8276 (2002).
9. Watts, D. J. & Strogatz, S. H. Collective Dynamics of ‘Small-World’ Networks. Additional information
Nature 393, 440–442 (1998). Supplementary information accompanies this paper at [Link]
10. Cohen, R. & Havlin, S. Scale-Free Networks are Ultrasmall. Phys. Rev. Lett. 90, scientificreports
058701 (2003).
Competing financial interests: The authors declare no competing financial interests.
11. Albert, R., Jeong, H. & Barabási, A.-L. Internet: Diameter of the World-Wide Web.
Nature 401, 130–131 (1999). How to cite this article: Zheng, B. et al. A simple model clarifies the complicated
12. Song, C., Havlin, S. & Makse, H. A. Origins of fractality in the growth of complex relationships of complex networks. Sci. Rep. 4, 6197; DOI:10.1038/srep06197 (2014).
networks. Nat. Phys. 2, 275–281 (2006).
13. Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. This work is licensed under a Creative Commons Attribution 4.0 International
Phys. 74, 47–97 (2002). License. The images or other third party material in this article are included in the
14. Amaral, L. A. N., Scala, A., Barthélémy, M. & Stanley, H. E. Classes of small-world article’s Creative Commons license, unless indicated otherwise in the credit line; if
networks. Proc. Natl. Acad. Sci. USA 97, 11149–11152 (2000). the material is not included under the Creative Commons license, users will need
15. Erdós, P. & Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hung. to obtain permission from the license holder in order to reproduce the material. To
Acad. Sci 5, 17–61 (1960). view a copy of this license, visit [Link]

SCIENTIFIC REPORTS | 4 : 6197 | DOI: 10.1038/srep06197 6

View publication stats