Title\thanksref{label1}
Title\thanksref{label1}
Scale-free networks are abundant in nature, describing such diverse systems as the world wide web, the web of human sexual contacts, or the chemical network of a cell. All models used to generate a scale-free topology are stochastic, that is they create networks in which the nodes appear to be randomly connected to each other. Here we propose a simple model that generates scale-free networks in a deterministic fashion. We solve exactly the model, showing that the tail of the degree distribution follows a power law.
hier2.tex
% Template article for preprint document class `elsart'
% SP 2001/01/05

\documentclass{elsart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
 \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Deterministic Scale-Free Networks}

% use optional labels to link authors explicitly to addresses:
 \author{Albert-L\'aszl\'o Barab\'asi$^a$, Erzs\'ebet Ravasz$^a$, Tam\'as Vicsek$^b$}
 \address{$^a$Department of Physics, University of Notre Dame, \\ Notre Dame, IN 46556-5670, USA\\
	  $^b$Department of Biological Physics, E\"otv\"os University, \\ 
		P\'azm\'any P\'eter S\'etany	1-A, Budapest, Hungary, H-1117}


\begin{abstract}

    Scale-free networks are abundant in nature, describing such diverse
systems as the world wide web, the web of human sexual contacts, or the chemical network of a
cell.
    All models used to generate a scale-free topology are stochastic,
that is they create networks in which the nodes appear to be randomly
connected to each other.
    Here we propose a simple model that
generates scale-free networks in a deterministic  fashion.
    We solve exactly the model, showing that the tail of the
degree distribution follows a power law.

\end{abstract}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
% PACS codes here, in the form: \PACS code \sep code
Disordered Systems; Networks; Scale-free networks; Scaling
\PACS
\end{keyword}
\end{frontmatter}

% main text
%\section{}
%\label{}

    Networks are ubiquitous in nature and society \cite{reka,alb,dorog},
describing various complex systems, such as the society, a
network of individuals linked by various social links \cite{amaral,newman1,newman2,collab};
the Internet, a network of routers connected by various physical
  connections \cite{falaustos,attack};
the world wide web, a virtual web of documents connected by uniform
resource connectors \cite{diameter} or the cell, a network
of substrates connected by chemical reactions  \cite{43_bio,protein}.
     Despite their diversity, most networks appearing in nature follow universal organizing principles.
    In particular, it has been found that many
     networks of scientific interest are scale-free \cite{BA_sci,BA_phys}, that is, the probability that a randomly selected node has exactly
      $k$ links decays as a power law, following $P(k) \sim k^{-\gamma}$, where $\gamma$ is the degree exponent.
    The list of documented
scale-free networks now include the world wide web \cite{diameter,broder}, the Internet \cite{falaustos},
the cell \cite{43_bio,protein}, the web of human sexual contacts \cite{sex}, the language  \cite{sole}, or the
web of actors in Hollywood \cite{actor}, most of which appear to have degree exponents between two and three.

    The $\,$high$\,$ interest$\,$ in$\,$ understanding$\,$ the$\,$
 topology$\,$ of $\,$complex $\,$networks$\,$
has $\,$resulted$\,$ in$\,$ the$\,$ development$\,$ of a$\,$ considerable$\,$ number $\,$of $\,$
network $\,$models \cite{BA_sci,BA_phys,m1,m2,m3,m4,r1,r2,r3,gin1,gin2}.
    Most of these are based on two mechanisms: incremental growth and preferential attachment \cite{BA_sci,BA_phys}.
    Incremental  growth captures the fact that  networks are assembled
through the addition of new nodes to the system, while preferential
 attachment encodes the hypothesis that new nodes connect with higher probability
to more connected nodes.
    Both of these mechanisms have been supported by extensive
empirical measurements \cite{newman2,zoli,pastor}, indicating that they are
 simultaneously present in many systems with scale-free network topology.


    Stochasticity is a common feature of all network models that generate
 scale-free topologies.
    That is, new nodes connect using
a probabilistic rule to the nodes already present in the system.
    This randomness present in the models, while in line with
the major features of networks seen in nature, makes it harder to gain a visual understanding of what makes them
scale-free, and how do different
nodes relate to each other.
    It would therefore be of major theoretical
interest to construct models that lead to scale-free
networks in a deterministic fashion.
    Here we present such a simple model, generating a
deterministic scale-free network using a hierarchical
construction.

\section{Model description}
\label{model}
    The construction of the model, that follows a hierarchical rule commonly used in
deterministic fractals \cite{mandel,vicsek}, is shown in Figure 1.
    The network is built in an iterative fashion, each iteration
repeating and reusing the elements generated in the previous
steps as follows:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\epsfig{figure=figure.eps,height=8.5cm,width=9.8cm}
\caption{Construction of the deterministic scale-free network,
showing the first four steps of the iterative process.}
\label{fig:fig1}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\emph{Step 0:} We start from a single node, that we designate as the 
\emph{root} of the graph.

\emph{Step 1:} We add two more nodes, and connect each of them to the root.

\emph{Step 2:} We add two units of three nodes, each unit identical
to the network created in the previous iteration (step 1), and we
 connect each of the {\it bottom}  nodes (see Figure 1) of these two units to the
 root.
 That is, the root will gain four more new links.

\emph{Step 3:} We add two units of nine nodes each, identical
to the units generated in the previous iteration, and connect all
eight bottom nodes of the two new units to the root.

These rules can be easily generalized. Indeed,  step $n$ would involve the following operation:

\emph{Step $n$:} Add two units of $3^{n-1}$ nodes each, identical
to the network created in the previous iteration (step $n-1$), and
connect each of the $2^n$ bottom nodes of these two units to the
root of the network.

\section{Analytical solution}
\label{anal}

Thanks to its deterministic and discrete nature, the model
described above can be solved exactly. To show its scale-free
nature, in the following we concentrate on the degree
distribution, $P(k)$.


    The tail of the degree distribution is determined by the most connected nodes, or hubs.
    Clearly the biggest hub is the root, and the next two hubs are the roots of the two
    units added to the network in the last step.
    Therefore, in order to capture the tail of the distribution, it is sufficient to focus
     on the hubs.

    In step $i$ the degree of the most connected hub, the root, is $2^{i+1}-2$.
     In the next iteration two
    copies of this
hub will appear in the two newly added units. As we iterate
further, in the $n$th step $3^{n-i}$ copies of this hub will be
present in the network. However,  the two newly created copies
will not increase their degree after further iterations.
  Therefore, after $n$ iterations  there are $(2/3) 3^{n-i}$
  nodes with degree  $2^{i+1}-2$. Since spaces between degrees grow with increrasing $k$,
the exponent of the degree distribution can be calculated using the cumulative degree 
disctribution. The tail of the cumulative degree distribution, determined by the hubs, follows
$$
    P_{\text{cum}}(k) \sim k^{1-\gamma} \sim k^{-\frac{\ln3}{\ln2}}.
$$
 Thus the degree exponent is $$\gamma=1+\frac{\ln3}{\ln2}.$$
    The origin of this scaling behavior can be understood by inspecting the model's construction.
    Indeed, at any moment we have a hierarchy of hubs, highly
connected nodes which are a common component of scale-free
networks.  The root is always the largest hub.
    However, at any step there are two hubs whose connectivity is roughly a half of the root's
connectivity, corresponding to the roots of the two units added at step $n-1$.
    There are six even smaller hubs, with connectivity $2^{n-1}-2$, corresponding to
the root of the units added at time $n-2$, and so on. This
hierarchy of hubs is responsible for the network's scale-free
topology. 


\section{Discussion}
\label{disc}
The model introduced above offers a deterministic construction of a scale-free network.
    One of its interesting properties is its apparent
self-similarity.
    On the other hand, while the networks generated at step $n$ and $n-1$ have an identical
large-scale topology, self-similarity is not complete.
    The special role played by the root,
the major hub in the network, violates complete self-similarity.
    Indeed, the root keeps a detailed record of the system size through the
number of links it has.
    Such global information is never present in a local element of a
fractal, the common example of a self-similar object.
    This unique feature of our construction reflects a common
property of all scale-free networks, rooted in the nonlocal growth
rule that generates scale-free systems.
       Indeed, in stochastic models the probability that a node
connects to an existing node in the system contains implicitly
the information about the whole system.
    While the connectivity of the hub in a stochastic
network is not equal to the system size, it typically varies as a simple function of $N$.
    Similarly, here the largest hub, the root of our construction, keeps track of the
       system size in a trivial way, as $2/3$ of the nodes are linked to it.


The proposed model generates a network with a fixed
$\gamma=1+\ln3/\ln2$ degree exponent.
    However, one can easily modify the model to change
the scaling exponent by varying the number of links connected to
the root at each step. 
    Similarly,  by definition the model discussed
here has a zero clustering coefficient  \cite{newman2}, as it does
not generate triangles of connected nodes. It is easy to change
the rules, without changing the scaling exponent, to obtain a
network that displays nonzero clustering. Indeed, a version in
which each two copies of the original hub 
are connected has a finite clustering coefficient. 
These and further variants of the model
  will be discussed in forthcoming publications.

    A crucial unique property of the model is its hierarchical
structure.
    It is not clear whether the hierarchy seen in this model is a unique property
of its construction, or it is an intrinsic property of all
scale-free networks.
    Uncovering the elements of the hierarchy could be an important future task in our
understanding of scale-free networks.
    The   present model explicitly builds such a hierarchical construction into
the network, as at each iteration we connect nodes to each
  other in a hierarchical fashion.


In conclusion, we introduced a simple model that allows us to construct
a deterministic scale-free network.
    We have shown that the scaling exponent characterizing
the tail of the $P(k)$ distribution can be calculated analytically.
    An important feature of the model is its hierarchical topology,
as at each iteration it combines identical elements to generate a
larger network.
    The method that lead
  to the construction of the network naturally lends itself to immediate generalizations,
  leading to structures that are similar
   in spirit, but rather different in detail,
   allowing us to generate networks with different scaling exponents and connectivity.



{\bf Acknowledgments:}

We with to thank H. Jeong for his help with the manuscript.
This research was supported by NSF-PHY-9988674.




\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}
\bibitem{reka}      Albert, R., Barab\'asi, A.L.,
            %Statistical mechanics of complex networks
                        Rev. of Mod. Phys. (2001) (in press), cond-mat/0106096.
\bibitem{alb}       Barab\'asi, A.L., Physics World, Vol. {\bf 14}, 7, (2001) 33-38.
\bibitem{dorog}     Dorogovtsev, S. N., Mendes   J. F. F., Adv. in Phys. (2001) (in press),
cond-mat/0106144.
\bibitem{amaral}    Amaral, L. A. N., A. Scala, M. Barth\'el\'emy and H. E. Stanley,
                 Proc. Nat. Acad. Sci. USA {\bf 97}, (2000) 11149.
\bibitem{newman1}   Newman, M. E. J., Proc. Nat. Acad. Sci. 98 (2001) 404-409.
\bibitem{newman2}   Newman, M. E. J., J. Stat. Phys. {\bf 101}, (2000) 819.
\bibitem{collab}    Barab\'asi, A.L., Jeong, H., N\'eda, Z., Ravasz, E.,
            Schubert, A., Vicsek, T., cond-mat/0104162 (2001).
\bibitem{falaustos} Faloutsos, M., P. Faloutsos and C. Faloutsos,
            Proc. ACM SIGCOMM, Comput. Commun. Rev. {\bf 29}, (1999) 251 .
\bibitem{attack}    Albert, R., Jeong, H., Barab\'asi, A.L.,
                %Attack and error tolerance in complex networks
            Nature {\bf 406}, (2000) 378.
\bibitem{diameter}  Albert, R., Jeong, H., Barab\'asi, A.L., Nature {\bf 401},
            (1999) 130.
\bibitem{43_bio}    Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N.,
             Barab\'asi, A.L.,
            %The large-scale organization of metabolic networks,
              Nature {\bf 407}, (2000) 651-654.
\bibitem{protein}   Jeong, H., Mason, S., Barab\'asi, A.L.,  Oltvai, Z.N.,
              Nature {\bf 411}, (2001) 41-42.
            %Lethality and centrality in protein networks,
\bibitem{BA_sci}    Barab\'asi, A.L., Albert, R., Science {\bf 286}, (1998) 509.
\bibitem{BA_phys}   Barab\'asi, A.L., Albert, R., Jeong, H., Physica A
            {\bf 272}, (1999) 173.
\bibitem{broder}    Broder, A., R. Kumar, F. Maghoul, P. Raghavan, S. Rajalopagan, R.
            Stata, A. Tomkins and J. Wiener, Comput. Netw. {\bf 33}, (2000) 309.
\bibitem{sex}       Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E.,
            %The web of human sexual contacts
            Aringberg, Y.,  Nature {\bf 411}, (2001) 907 - 908.
\bibitem{sole}      Sol\'e, R. V. and J. M. Montoya, (2000) cond-mat/0011196.
\bibitem{actor}     Albert, R. and A.-L. Barab\'asi, Phys. Rev. Lett. {\bf 85},  (2000)
5234.
\bibitem{m1}        Dorogovtsev, S. N., Mendes J. F. F., Europhys. Lett. {\bf 50}, (2000) 1.
\bibitem{m2}        Dorogovtsev, S. N., Mendes J. F. F., Phys. Rev. E {\bf
            62},  (2000) 1842.
\bibitem{m3}        Dorogovtsev, S. N., Mendes J. F. F., Europhys. Lett {\bf
            52}, (2000) 33.
\bibitem{m4}        Dorogovtsev, S. N., Mendes J. F. F.and A. N. Samukhin,
            Phys. Rev. Lett. {\bf 85}, (2000) 4633.
\bibitem{r1}       Krapivsky, P. L., Redner S., Phys. Rev. E {\bf 63}, 066123 (2001).
\bibitem{r2}        Krapivsky. P. L., Redner S., Leyvraz, F., Phys. Rev. Lett
            {\bf 85}, (2000) 4629.
\bibitem{r3}        Krapivsky, P. L., Rodgers, G.J., Redner, S., Phys. Rev. Lett. (to appear), (2001)
		 cond-mat/0012181.
\bibitem{gin1}      Bianconi, G., Barab\'asi, A.L., Europhys. Lett. {\bf 54} (4), 443-448 (2001). 
\bibitem{gin2}      Bianconi, G., Barab\'asi, A.L., Phys. Rev. Lett. {\bf 86}, 5632 (2001).
\bibitem{zoli}      Jeong, H., Z. N\'eda and A.-L. Barab\'asi, (2001) cond-mat/0104131.
\bibitem{pastor}    Pastor-Satorras, R., V\'azquez A., Vespignani, A., cond-mat/0105161.
\bibitem{mandel}    Mandelbrot, B.B., \emph{The Fractal Geometry of Nature} (Freeman, San Fransisco) 1982.
\bibitem{vicsek}    Vicsek, T., \emph{Fractal Growth Phenomena} (World Scientific, Singapore, New Jersey) 1989.

\end{thebibliography}

\end{document}

cond-mat0107419.extracted_bib
\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}
\bibitem{reka}      Albert, R., Barab\'asi, A.L.,
            %Statistical mechanics of complex networks
                        Rev. of Mod. Phys. (2001) (in press), cond-mat/0106096.
\bibitem{alb}       Barab\'asi, A.L., Physics World, Vol. {\bf 14}, 7, (2001) 33-38.
\bibitem{dorog}     Dorogovtsev, S. N., Mendes   J. F. F., Adv. in Phys. (2001) (in press),
cond-mat/0106144.
\bibitem{amaral}    Amaral, L. A. N., A. Scala, M. Barth\'el\'emy and H. E. Stanley,
                 Proc. Nat. Acad. Sci. USA {\bf 97}, (2000) 11149.
\bibitem{newman1}   Newman, M. E. J., Proc. Nat. Acad. Sci. 98 (2001) 404-409.
\bibitem{newman2}   Newman, M. E. J., J. Stat. Phys. {\bf 101}, (2000) 819.
\bibitem{collab}    Barab\'asi, A.L., Jeong, H., N\'eda, Z., Ravasz, E.,
            Schubert, A., Vicsek, T., cond-mat/0104162 (2001).
\bibitem{falaustos} Faloutsos, M., P. Faloutsos and C. Faloutsos,
            Proc. ACM SIGCOMM, Comput. Commun. Rev. {\bf 29}, (1999) 251 .
\bibitem{attack}    Albert, R., Jeong, H., Barab\'asi, A.L.,
                %Attack and error tolerance in complex networks
            Nature {\bf 406}, (2000) 378.
\bibitem{diameter}  Albert, R., Jeong, H., Barab\'asi, A.L., Nature {\bf 401},
            (1999) 130.
\bibitem{43_bio}    Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N.,
             Barab\'asi, A.L.,
            %The large-scale organization of metabolic networks,
              Nature {\bf 407}, (2000) 651-654.
\bibitem{protein}   Jeong, H., Mason, S., Barab\'asi, A.L.,  Oltvai, Z.N.,
              Nature {\bf 411}, (2001) 41-42.
            %Lethality and centrality in protein networks,
\bibitem{BA_sci}    Barab\'asi, A.L., Albert, R., Science {\bf 286}, (1998) 509.
\bibitem{BA_phys}   Barab\'asi, A.L., Albert, R., Jeong, H., Physica A
            {\bf 272}, (1999) 173.
\bibitem{broder}    Broder, A., R. Kumar, F. Maghoul, P. Raghavan, S. Rajalopagan, R.
            Stata, A. Tomkins and J. Wiener, Comput. Netw. {\bf 33}, (2000) 309.
\bibitem{sex}       Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E.,
            %The web of human sexual contacts
            Aringberg, Y.,  Nature {\bf 411}, (2001) 907 - 908.
\bibitem{sole}      Sol\'e, R. V. and J. M. Montoya, (2000) cond-mat/0011196.
\bibitem{actor}     Albert, R. and A.-L. Barab\'asi, Phys. Rev. Lett. {\bf 85},  (2000)
5234.
\bibitem{m1}        Dorogovtsev, S. N., Mendes J. F. F., Europhys. Lett. {\bf 50}, (2000) 1.
\bibitem{m2}        Dorogovtsev, S. N., Mendes J. F. F., Phys. Rev. E {\bf
            62},  (2000) 1842.
\bibitem{m3}        Dorogovtsev, S. N., Mendes J. F. F., Europhys. Lett {\bf
            52}, (2000) 33.
\bibitem{m4}        Dorogovtsev, S. N., Mendes J. F. F.and A. N. Samukhin,
            Phys. Rev. Lett. {\bf 85}, (2000) 4633.
\bibitem{r1}       Krapivsky, P. L., Redner S., Phys. Rev. E {\bf 63}, 066123 (2001).
\bibitem{r2}        Krapivsky. P. L., Redner S., Leyvraz, F., Phys. Rev. Lett
            {\bf 85}, (2000) 4629.
\bibitem{r3}        Krapivsky, P. L., Rodgers, G.J., Redner, S., Phys. Rev. Lett. (to appear), (2001)
		 cond-mat/0012181.
\bibitem{gin1}      Bianconi, G., Barab\'asi, A.L., Europhys. Lett. {\bf 54} (4), 443-448 (2001). 
\bibitem{gin2}      Bianconi, G., Barab\'asi, A.L., Phys. Rev. Lett. {\bf 86}, 5632 (2001).
\bibitem{zoli}      Jeong, H., Z. N\'eda and A.-L. Barab\'asi, (2001) cond-mat/0104131.
\bibitem{pastor}    Pastor-Satorras, R., V\'azquez A., Vespignani, A., cond-mat/0105161.
\bibitem{mandel}    Mandelbrot, B.B., \emph{The Fractal Geometry of Nature} (Freeman, San Fransisco) 1982.
\bibitem{vicsek}    Vicsek, T., \emph{Fractal Growth Phenomena} (World Scientific, Singapore, New Jersey) 1989.

\end{thebibliography}