A deterministic small-world network created by edge iterations
Zhongzhi Zhang\corauthref{zz}
Small-world networks are ubiquitous in real-life systems. Most previous models of small-world networks are stochastic. The randomness makes it more difficult to gain a visual understanding on how do different nodes of networks interact with each other and is not appropriate for communication networks that have fixed interconnections. Here we present a model that generates a small-world network in a simple deterministic way. Our model has a discrete exponential degree distribution. We solve the main characteristics of the model.\\ PACS: 89.70.+c, 87.18.Sn, 89.75.-k,05.10-a \begin{keyword} Small-world networks\sep Disordered systems\sep Exponential scaling %Disordered systems\sep Networks %\PACS 89.75.Da\sep 89.75.Fb\sep 89.75.Hc \end{keyword}
Physica_A_Rev.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% A deterministic small-world network
%% Zhongzhi Zhang, Lili Rong, Francesc Comellas
%% PHYSICA A
%% 10 March 2005 19:54
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{elsart}
\usepackage[dvips]{graphicx}

\newtheorem{property}{Property}

\begin{document}
\begin{frontmatter}

\title{A deterministic small-world network created by edge iterations}
\author{Zhongzhi Zhang\corauthref{zz}}
\corauth[zz]{Corresponding author. Tel. 0086-411-84707819.}
\ead{dlutzzz063@yahoo.com.cn}
\author{Lili Rong}
\ead{llrong@dlut.edu.cn}
\address{
Institute of Systems Engineering, Dalian University of Technology,
\\ Dalian 116024, Liaoning, China}%
\author{Chonghui Guo}
\ead{guochonghui@tsinghua.org.cn}
\address{
Department of Applied Mathematics , Dalian University of Technology,
\\ Dalian 116024, Liaoning, China}%




\begin{abstract}
Small-world networks are ubiquitous in real-life systems. Most
previous models of small-world networks are stochastic. The
randomness makes it more difficult to gain a visual understanding on
how do different nodes of networks interact with each other and is
not appropriate for communication networks that have fixed
interconnections. Here we present a model that generates a
small-world network in a simple deterministic way. Our model has a
discrete exponential degree distribution. We solve the main
characteristics of the
model.\\


PACS: 89.70.+c, 87.18.Sn, 89.75.-k,05.10-a


\begin{keyword}
Small-world networks\sep Disordered systems\sep  Exponential scaling
%Disordered systems\sep Networks
%\PACS  89.75.Da\sep 89.75.Fb\sep 89.75.Hc
\end{keyword}
\end{abstract}



%89.20.Hh World Wide Web, Internet
%89.75.Da Systems obeying scaling laws
%89.75.Fb Structures and organization in complex systems
%89.75.-k Complex systems
%89.75.Hc Networks and genealogical trees

\date{}
\end{frontmatter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\vskip -0.5cm\color{Blue}
%\vbox to 0pt{\kern -14cm {
%\noindent \small \copyright 2005
%{\em Elsevier Science B.V. All rights reserved}\\
%{\em Physica A}, submitted.}
%\vss}\color{Black}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Small-world networks describe many real-life networks, such as the
World Wide Web, communication networks, the neuronal network of the
worm C. elegans, the electric power grid of southern California, or
social networks that achieve both a strong local clustering and a
small average path length~\cite{AlBa02,DoMe02,Ne03,St01,Ne00}.
Generally, small-world networks are characterized by three main
properties. First, their average path length (APL) doesn't increase
linearly with the system size, but grows logarithmically with the
number of nodes or slower. Second, average node degree of the
network is small. Third, the network has a high average
clustering~\cite{WaSt98} compared to an Erd\"os-R\'enyi (ER) random
network~\cite{ErRe59,ErRe60} of equal size and average node degree.
Average path length can be used to estimate the average transmission
delay. One can always reduce the average path length by adding more
edges. But for some economical and technical reasons, the average
edge number of nodes must be controlled within an acceptable range.
Moreover, the cliquishness tendency of network nodes leads to a
large clustering coefficient.

The first successful attempt to generate networks with high
clustering coefficients and small APL is the model introduced by
Watts and Strogatz (WS model)~\cite{WaSt98}. This pioneering work
of Watts and Strogatz started an avalanche of research on the
properties of small-world networks and the Watts-Strogatz (WS)
model. A much-studied variant of the WS model was proposed by
Newman and Watts~\cite{NeWa99a,NeWa99b}, in which edges are added
between randomly chosen pairs of nodes, but no edges are removed
from the regular lattice. In 1999, Kasturirangan proposed an
alternative model to WS small-world network~\cite{Ka99}. The model
starts also with one ring lattice, then a number of extra nodes
are added in the middle of the lattice which are connected to a
large number of sites chosen randomly on the main lattice. In
fact, even in the case where only one extra node is added, the
model shows the small-world effect if that node is sufficiently
highly connected, which has been solved exactly by Dorogovtsev and
Mendes~\cite{DoMe00}. To investigate the small-world effect
further, Kleinberg has presented a generalization of the WS model
which is based on a two-dimensional square lattice~\cite{Kl00}.
Besides, in order to study other mechanisms for forming
small-world networks, Ozik, Hunt and Ott introduced a simple
evolution model of growing small-world networks, in which all
connections are made locally to geographically nearby
sites~\cite{OzHuOt04}.

The above models are all random. It is known to us all,
stochasticity is a common feature of complex network models that
generate small-world and scale-free topologies. That is, new nodes
connect using a probabilistic rule to the nodes already present in
the system. But as mentioned by Barab\'asi et al., the randomness,
while in line with the major features of real-life networks, makes
it harder to gain a visual understanding of how networks are shaped,
and how do different nodes relate to each other~\cite{BaRaVi01}. In
addition, the probabilistic analysis techniques and random placement
or addition of edges used in most previous studies are not
appropriate for communication networks that have fixed
interconnections, such as neural networks, computer networks,
electronic circuits, and so on. Therefore, it would be not only of
major theoretical interest but also of great practical significance
to construct models that lead to scale-free
networks~\cite{BaRaVi01,IgYa04,DoGoMe02,JuKiKa02,RaBa03,No03,CoFeRa04,AnHeAnSi05,DoMa05,ZhCoFeRo05,ZhWaHuCh04}
and small-world networks~\cite{CoOzPe00,CoSa02} in deterministic
fashions. A strong advantage of deterministic networks is that it is
often possible to compute analytically their properties, for
example, degree distribution, clustering coefficient, average path
length, diameter and adjacency matrix whose eigenvalue spectrum
characterizes the topology.

In this paper, we focus on the small-world network topology
generated in a deterministic way. In 2000, using graph-theoretic
methods Comellas, Oz\'on and Peters introduced deterministic
small-world communication networks~\cite{CoOzPe00}. Two years later,
Comellas and Sampels presented other two deterministic techniques
for small-world networks with constant and variable degree
distributions, respectively~\cite{CoSa02}. Here we propose a simple
construction technique generating a deterministic small-world
network by attaching to edges which was used by Dorogovtsev et al.
to generate pseudofractal scale-free web~\cite{DoGoMe02}. This exact
approach of our model enables one to obtain the analytic solution
for relevant network parameters: degree distribution, clustering
coefficient and diameter. As a result, our network has strong
clustering and small diameter.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Figure  1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{figure}
%\begin{center}
%\includegraphics[width=6cm]{Apcircle.ps}
%\caption{An Apollonian packing of disks within a circle.}
%\label{fig:Apollo}
%\end{center}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The iterative algorithm for the deterministic small-world network}

It is well known that the number of nodes in most of networks in
real world increases exponentially with time. The World Wide Web,
for example, has been increasing in size exponentially from a few
thousand nodes in the early 1990s to hundreds of millions today.
Therefore, our deterministic model is constructed in this
evolutionary way. That is to say, our model is a growing network,
whose size (the number of nodes) increases exponentially with time.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Figure  1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{center}
\includegraphics[width=16cm]{fig1}
\caption{Construction of the deterministic small-world network,
showing the first four steps of the iterative process. }
\label{fig:cluster}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We denote our network after $t$ step evolution by $N(t)$. The
network is created by an iterative method. Its construction
algorithm is the following: For $t=0$, $N(0)$ is a triangle whose
three nodes connect one another. For $t\geq1$, $N(t)$ is obtained
from $N(t-1)$ by adding for each edge created at step $t-1$ a new
node and attaching it to both end nodes of the edge (see Fig. 1).
Notice that in~\cite{DoGoMe02} Dorogovtsev \emph{et al.} introduced
a pseudofractal scale-free web which is constructed as follows: At
each time step, for every edge of the web (not only the ones created
at the last time step as in our network), a new node is added, which
is attached to both end nodes of the edge. So our model is a variant
of the pseudofractal scale-free web. Now we compute the size and
order of $N(t)$. In the evolution process of the model, for each new
node added, two new edges are created in the network. And for each
of the newly-created edges, a node will be created and connected to
both the ends of the edge in the next step. Therefore,
\begin{equation}
\bigtriangleup n_v(t) =n_v(t)-n_v(t-1)=2\bigtriangleup n_v(t-1),
t>1
\end{equation}
where $n_{v}$ is the total number of nodes in the network. Since
$n_{v}(0)=3$, and $\bigtriangleup n_{v}(1)=3$, it follows that
\begin{equation}
\bigtriangleup n_{v}(t) =3\cdot 2^{t-1},  n_v(t) =3\cdot 2^{t}
\end{equation}
The addition of each new node leads to two new edges. Therefore,
\begin{equation}
\bigtriangleup n_e(t) =n_e(t)-n_e(t-1)=2\bigtriangleup
n_v(t)=3\cdot 2^{t}
\end{equation}
where $n_{e}$ is the total number of edges in the network. As
$n_{e}(0)=3$
\begin{equation}
n_e(t) =3\cdot 2^{t+1}-3
\end{equation}
The average node degree is then
\begin{equation}
\langle k\rangle=\frac{2n_{e}}{v_{v}}=\frac{2 (3\cdot
2^{t+1}-3)}{3\cdot 2^{t}}=4\cdot (1-\frac{1}{2^{t+1}})
\end{equation}
For large $t$ it is small and approximately equal to 4. We can see
when $t$ is large enough the resulting network is a sparse graph
whose nodes have many fewer connections than is possible.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Relevant characteristics of the deterministic small-world Network}
Thanks to its deterministic and discrete nature, the model
described above can be solved exactly. In the following we
concentrate on the degree, clustering coefficient and diameter.
\subsection{Degree distribution}
The degree distribution is one of the most important statistical
characteristics of a network. By definition, the degree of a node
$i$ is the number of edges incident from  $i$. We denote the
degree of node $i$  at step $t$ by $k_{i}(t)$. Degree distribution
$P(k)$ is the probability that a randomly selected node has
exactly $k$ edges. By construction, we have
\begin{equation}
k_{i}(t+1)=k_{i}(t)+2
\end{equation}
if $t_{c,i}$ is the step at which a node $i$ is created, then
$k_{i}(t_{c,i})=2$ and hence
\begin{equation}
k_{i}(t)=2(t-t_{c,i}+1)
\end{equation}
Therefore, the degree spectrum of the present network is series of
discrete values: at time $t$, the number of nodes of degree
$k=2\cdot1,2\cdot2,2\cdot3,\cdots,2\cdot $(t-1)$,
2\cdot$t$,2\cdot$(t+1)$ $, equals to $\bigtriangleup
n_{v}(t),\bigtriangleup n_{v}(t-1),\bigtriangleup
n_{v}(t-2),\cdots,\bigtriangleup n_{v}(2),\bigtriangleup
n_{v}(1),n_{v}(0)$, respectively. Other values of degree are absent
in the spectrum. Due to the discreteness of this degree spectrum, it
is convenient to obtain the degree via its cumulative
distribution~\cite{JuKiKa02}, i.e.
\begin{equation}
P(k)=P(k'>k-1)-P(k'>k).
\end{equation}
Using the fact, $P(k'>k)=P\left (t_{c}<\tau=t-(\frac{k}{2}-1)\right
)$, where $t_{c}$ is the birth time of nodes, we obtain that
\begin{equation}
P(k'>k)=\frac{n_{v}(0)}{n_{v}(t)}+\sum_{t_{c}=1}^{\tau-1}\frac{\bigtriangleup
n_{v}(t_{c})}{n_{v}(t)}=2^{-\frac{k}{2}_{.}}
\end{equation}
Using Eq. (8), we have
\begin{equation}
P(k)=P(k'>k-1)-P(k'>k)=(\sqrt{2}-1)2^{-\frac{k}{2}}
\end{equation}
Obviously, when the size of the network is large, the degree
distribution $P(k)$ is an exponential of a power of degree $k$, so
this deterministic small-world model can be called an exponential
network. Note that most small-world networks including WS network
belong to this type ~\cite{BaWe00}.

\subsection{ Clustering coefficient}
Clustering is another important property of a network, which
provides a measure of the local structure within the network. The
most immediate measure of clustering is the clustering coefficient
$C_{i}$ for every node $i$. By definition, clustering
coefficient~\cite{WaSt98} $C_{i}$ of a node $i$ is the ratio of the
total number $E_{i}$ of edges that actually exist between all
$k_{i}$ its nearest neighbors and the number $k_{i}(k_{i}-1)/2$ of
all possible edges between them, i.e.
$C_{i}=2E_{i}/[k_{i}(k_{i}-1)]$. The clustering coefficient $\langle
C \rangle $ of the whole network is the average of all individual
$C_{i}'s$. Next we will compute the clustering coefficient of every
node and their average value.

When a new node $i$ joins the network, its degree $k_{i}$ and
$E_{i}$ is $2$ and $1$, respectively. Each subsequent addition of a
link to that node increases both $k_{i}$ and $E_{i}$ by one. Thus,
$E_{i}$ equals to $k_{i}-1$ for all nodes at all steps. So one can
see that, in this network there is a one-to-one correspondence
between the degree of a node and its clustering. For a node $v$ of
degree $k$, the exact expression for its clustering coefficient is
$2/k$. This expression indicates that the local clustering scales as
$C(k)\sim k^{-1}$. It is interesting to notice that a similar
scaling has been observed empirically in several real-life
networks~\cite{RaBa03}.


Clearly, the number of nodes with clustering coefficient $C=1,
1/2, 1/3, \cdots, $1/(t-1)$, 1/t, $1/(t+1)$ $, is equal to
$\bigtriangleup n_{v}(t), \bigtriangleup n_{v}(t-1),\bigtriangleup
n_{v}(t-2),\cdots,\bigtriangleup n_{v}(2),\bigtriangleup
n_{v}(1),n_{v}(0)$, respectively. The average clustering
coefficient $\langle C \rangle$ can be easily obtained for
arbitrary $t$,
$$
\begin{array}{l}
\langle C\rangle=2\langle\frac{1}{k}\rangle=\frac{1}{n_v(t)}\left[\sum_{i=1}^t\frac{1}{i}\cdot\Delta n_v(t+1-i)+\frac{1}{t+1}\cdot n_v(0)\right]\\
       \quad\quad=1\cdot\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{2^2}+\frac{1}{3}\cdot\frac{1}{2^3}+ \frac{1}{4} \cdot \frac{1}{2^{4}}+\cdots +
\frac{1}{t-1}\cdot \frac{1}{2^{t-1}}+\frac{1}{t}\cdot
\frac{1}{2^{t}}+ \frac{1}{t+1}\cdot \frac{1}{2^{t}} \\
\quad\quad=\sum_{m=1}^t\frac{1}{m}\left(\frac{1}{2}\right)^m+\frac{1}{t+1}\cdot\frac{1}{2^t}
\end{array}
$$



For infinite $t$, $\langle C \rangle =-ln(1-\frac{1}{2})=ln2$ ,
which approaches to a constant value 0.6931, and so the clustering
is high.
\subsection{Diameter}
The small-world concept describes the fact that there is a
relatively short distance between most pairs of nodes in most
real-life networks. The distance between two nodes is the least
number of edges to get from one node to the other. The average path
length is the smallest number of links connecting a pair of nodes,
averaged over all pairs of nodes. The longest shortest path between
all pairs of nodes is called diameter, which is one of the most
important evaluation indexes because it characterizes the maximum
communication delay in the network. Usually those graphs of smaller
node degree and with smaller diameter or average path length are
preferred as interconnection networks. Small diameter is consistent
with the concept of small-world network and it is easier to compute.
So we will study the diameter instead of average path length. Below
we give the precise analytical computation of diameter of $N(t)$
denoted by $Diam(N(t))$.

Clearly, at step $t = 0$ (resp. $t = 1$), the diameter is equal to 1
(resp. 2). At each step $t\geq 2$, one can easily see that the
diameter always lies between a pair of nodes that have just been
created at this step. We will call such newly-created nodes outer
nodes. At any step $t\geq 2$, we note that an outer node cannot be
connected with two or more nodes that were created during the same
step $t^{'}\geq t-1$. Indeed, we know that from step $2$, no outer
node is connected to a node of the initial triangle $N(0)$. Thus,
for any step $t\geq 2$, any outer node is connected with nodes that
appeared at pairwise different steps. Now consider two outer nodes
created at step $t\geq 2$, say $v_{t}$ and $w_{t}$. Then $v_{t}$ is
connected to two nodes, and one of them must have been created
before or during step $t-2$. We repeat this argument, and we end up
with two cases: (1) $t = 2m$ is even. Then, if we make $m$ "jumps",
from $v_{t}$ we arrive in the initial triangle $N(0)$, in which we
can reach any $w_{t}$ by using an edge of $N(0)$ and making $m$
jumps to $w_{t}$ in a similar way. Thus $Diam(N(2m))\leq 2m+1$. (2)
$t = 2m+1$ is odd. In this case we can stop after m jumps at $N(1)$,
for which we know that the diameter is 2, and make $m$ jumps in a
similar way to reach $w_{t}$. Thus $Diam(N(2m+1))\leq 2(m+1)$. It is
easily seen that the bound can be reached by pairs of outer nodes
created at step $t$. More precisely, those two nodes $v_{t}$ and
$w_{t}$ share the property that they are connected to two nodes that
appeared respectively at steps $t-1$, $t-2$.

Hence, formally, $Diam(N(t)) = t+1$ for any $t\geq 0$. Note that
the logarithm value of total number of nodes $N_{t}$ is
%\ln(N_{t})=\ln(3\cdot 2^{t})= t\cdot \ln2+\ln3$, which
approximately equals to $(t+1)ln2$ for large $t$. Thus the
diameter grows logarithmically with the number of nodes and the
average path length increases more slowly than $ln(N_{t})$.

To see why the diameter and average path length grow so slowly, one
can pull the nodes of the networks represented in Fig. 1 to the
circumference of a circle. The older nodes that had once been
nearest neighbors along the circle are pushed apart as new nodes are
inserted into the interval between them. From Fig. 1, we can see
when new nodes are introduced into the system, the original nodes
are not adjacent but, rather, have a great number of new nodes
between them. Thus, growth leads to long-range edges between old
nodes, and these long-range edges similar to the shortcuts in the WS
model~\cite{WaSt98} are responsible for short diameter and average
path length.

Based on the above discussions, our model is a deterministic
small-world network, because it is a sparse one with high clustering
and short diameter and average path length, which satisfy the three
main necessary properties for small-world network.


\section{Conclusion and discussion}
In conclusion, we have presented a simple model that allows one to
construct deterministic small-world networks. We have obtained the
analytic solution for relevant network parameters of the
deterministic model, which are close to those for usual random
small-world
networks~\cite{WaSt98,NeWa99a,NeWa99b,Ka99,DoMe00,Kl00,OzHuOt04}.
 We believe that
our model may help engineers in network topology-designing and
performance-analyzing, it may also help to demystify the small-world
phenomenon. In addition, the model under consideration is a planar
graph which can be drawn on a plane without edges crossing. Many
real-life networks are planar graphs for technical or natural
requirements, such as layout of printed circuits and vein networks
clinging to cutis. We believe our network may help to understand
some properties of real-world planar networks.


\subsection*{Acknowledgment}
This research was supported by the Natural Science Foundation of
China (Grant No. 70431001). The authors are grateful to the
anonymous referees for their valuable comments and suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{10}

%1

\bibitem{AlBa02}
R. Albert and A.-L. Barab\'asi, Rev. Mod. Phys. 74 (2002) 47.

%2
\bibitem{DoMe02}
S.N. Dorogovtsev and J.F.F. Mendes, Adv. Phys. 51 (2002) 1079.

%3
\bibitem{Ne03}
M. E. J. Newman, SIAM Review 45 (2003) 167.

%4
\bibitem{St01}
S. H. Strogatz, Nature 410 (2001) 268.

%5
\bibitem{Ne00}
M. E. J. Newman, J. Stat. Phys. 101 (2000) 819.

%6
\bibitem{WaSt98}
D.J. Watts and S. H. Strogatz, Nature 393 (1998) 440.

%7
\bibitem{ErRe59}
P. Erd\"os and A. R\'enyi, Publ. Math. 6 (1959) 290.

%8
\bibitem{ErRe60}
P. Erd\"os, and A. R\'enyi, Publ. Math. Ins. Hung. Acad. Sci. 5
(1960) 17.

%9
\bibitem{NeWa99a}
M. E. J. Newman and D. J. Watts, Phys. Lett. A 263 (1999) 341.

%10
\bibitem{NeWa99b}
M. E. J. Newman and D. J. Watts, Phys. Rev. E 60 (1999) 7332.

%11
\bibitem{Ka99}
R. Kasturirangan cond-mat/9904055 (1999).

%12
\bibitem{DoMe00}
S.N. Dorogovtsev and J.F.F. Mendes, Europhys. Lett. 50 (2000) 1.

%13
\bibitem{Kl00}
J. Kleinberg, Nature 406 (2000) 845.

%14
\bibitem{OzHuOt04}
J. Ozik, B.-R. Hunt, and E. Ott, Phys. Rev. E 69 (2004) 026108.

%15
\bibitem{BaRaVi01}
A.-L. Barab\'asi, E. Ravasz, and T. Vicsek, Physica A 299 (2001)
559.

%16
\bibitem{IgYa04}
K. Iguchi and H. Yamada, Phys. Rev. E 71 (2005) 036144.

%17
\bibitem{DoGoMe02}
S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev.
E 65 (2002) 066122.

%18
\bibitem{JuKiKa02}
S. Jung, S. Kim, and B. Kahng, Phys. Rev. E 65 (2002) 056101.

%19
\bibitem{RaBa03}
E. Ravasz and A.-L. Barab\'asi, Phys. Rev. E 67 (2003) 026112.

%20
\bibitem{No03}
J.D. Noh, Phys. Rev. E 67 (2003) 045103.

%21
\bibitem{CoFeRa04}
F. Comellas, G. Fertin, and A. Raspaud, Phys. Rev. E 69 (2004)
037104.

%22
\bibitem{AnHeAnSi05}
J. S. Andrade Jr., H. J. Herrmann, R. F. S. Andrade and L. R.
da Silva, Phys. Rev. Lett. 94 (2005) 018702.

%23
\bibitem{DoMa05}
J. P. K. Doye and C. P. Massen, Phys. Rev. E 71 (2005) 016128.

%24
\bibitem{ZhCoFeRo05}
Z.Z. Zhang, F. Comellas, G. Fertin and L.L Rong, arXiv:
cond-mat/0503316.

%25
\bibitem{ZhWaHuCh04}
T. Zhou, B. H. Wang, P. M. Hui and K. P. Chan, arXiv:
cond-mat/0405258.

%26
\bibitem{CoOzPe00}
F. Comellas, J. Oz\'on, J.G. Peters, Inf. Process. Lett. 76 (2000)
83.

%27
\bibitem{CoSa02}
F. Comellas and M. Sampels, Physica A 309 (2002) 231.


%28
\bibitem{BaWe00}
A. Barrat, and M. Weigt, Eur. Phys. J. B 13 (2000) 547.


\end{thebibliography}


\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibitem{CoOzPe00}
F. Comellas, J. Oz\'on, and  J.G. Peters,
Deterministic small-world communication networks,
Inf. Process. Lett. 76   (2000) pp. 83--90.
%%
\bibitem{CoSa02}
F. Comellas and M. Sampels,
Deterministic small-world networks,
Physica A  309 (2002) 231--235.
%
\bibitem{DoGoMe02}
S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes,
Pseudofractal scale-free web,
Phys. Rev. E {\bf 65} (2002) 066122.
%
\bibitem{JuKiKa02}
S. Jung, S. Kim, and B. Kahng,
Geometric fractal growth model for scale-free networks.
Phys. Rev. E {\bf 65} (2002) 056101.
%
\bibitem{BaRaVi01}
A.-L. Barab\'asi, E. Ravasz,  T. Vicsek,
Deterministic scale-free networks,
Physica A 299 (2001) 559-564.
%
\bibitem{ChLuDeGa03}
F. Chung, Linyuan Lu, T. G. Dewey,  D. J. Galas,
Duplication models for biological networks,
J. of Comput. Biology  10 (5) (2003) 677--688.


��
cond-mat0502335.extracted_bib
\begin{thebibliography}{10}

%1

\bibitem{AlBa02}
R. Albert and A.-L. Barab\'asi, Rev. Mod. Phys. 74 (2002) 47.

%2
\bibitem{DoMe02}
S.N. Dorogovtsev and J.F.F. Mendes, Adv. Phys. 51 (2002) 1079.

%3
\bibitem{Ne03}
M. E. J. Newman, SIAM Review 45 (2003) 167.

%4
\bibitem{St01}
S. H. Strogatz, Nature 410 (2001) 268.

%5
\bibitem{Ne00}
M. E. J. Newman, J. Stat. Phys. 101 (2000) 819.

%6
\bibitem{WaSt98}
D.J. Watts and S. H. Strogatz, Nature 393 (1998) 440.

%7
\bibitem{ErRe59}
P. Erd\"os and A. R\'enyi, Publ. Math. 6 (1959) 290.

%8
\bibitem{ErRe60}
P. Erd\"os, and A. R\'enyi, Publ. Math. Ins. Hung. Acad. Sci. 5
(1960) 17.

%9
\bibitem{NeWa99a}
M. E. J. Newman and D. J. Watts, Phys. Lett. A 263 (1999) 341.

%10
\bibitem{NeWa99b}
M. E. J. Newman and D. J. Watts, Phys. Rev. E 60 (1999) 7332.

%11
\bibitem{Ka99}
R. Kasturirangan cond-mat/9904055 (1999).

%12
\bibitem{DoMe00}
S.N. Dorogovtsev and J.F.F. Mendes, Europhys. Lett. 50 (2000) 1.

%13
\bibitem{Kl00}
J. Kleinberg, Nature 406 (2000) 845.

%14
\bibitem{OzHuOt04}
J. Ozik, B.-R. Hunt, and E. Ott, Phys. Rev. E 69 (2004) 026108.

%15
\bibitem{BaRaVi01}
A.-L. Barab\'asi, E. Ravasz, and T. Vicsek, Physica A 299 (2001)
559.

%16
\bibitem{IgYa04}
K. Iguchi and H. Yamada, Phys. Rev. E 71 (2005) 036144.

%17
\bibitem{DoGoMe02}
S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev.
E 65 (2002) 066122.

%18
\bibitem{JuKiKa02}
S. Jung, S. Kim, and B. Kahng, Phys. Rev. E 65 (2002) 056101.

%19
\bibitem{RaBa03}
E. Ravasz and A.-L. Barab\'asi, Phys. Rev. E 67 (2003) 026112.

%20
\bibitem{No03}
J.D. Noh, Phys. Rev. E 67 (2003) 045103.

%21
\bibitem{CoFeRa04}
F. Comellas, G. Fertin, and A. Raspaud, Phys. Rev. E 69 (2004)
037104.

%22
\bibitem{AnHeAnSi05}
J. S. Andrade Jr., H. J. Herrmann, R. F. S. Andrade and L. R.
da Silva, Phys. Rev. Lett. 94 (2005) 018702.

%23
\bibitem{DoMa05}
J. P. K. Doye and C. P. Massen, Phys. Rev. E 71 (2005) 016128.

%24
\bibitem{ZhCoFeRo05}
Z.Z. Zhang, F. Comellas, G. Fertin and L.L Rong, arXiv:
cond-mat/0503316.

%25
\bibitem{ZhWaHuCh04}
T. Zhou, B. H. Wang, P. M. Hui and K. P. Chan, arXiv:
cond-mat/0405258.

%26
\bibitem{CoOzPe00}
F. Comellas, J. Oz\'on, J.G. Peters, Inf. Process. Lett. 76 (2000)
83.

%27
\bibitem{CoSa02}
F. Comellas and M. Sampels, Physica A 309 (2002) 231.


%28
\bibitem{BaWe00}
A. Barrat, and M. Weigt, Eur. Phys. J. B 13 (2000) 547.


\end{thebibliography}