Special Feature

Growth Models of Web Networks
Masahiro Kimura†
Abstract
The World Wide Web is constantly growing through the addition of new pages and hyperlinks created by users according to their particular interests. This article introduces research on a method of statistically modeling the growth dynamics of a network such as the Web.

1. Importance of modeling network growth
The World Wide Web provides a vast repository ofinformation and continues to grow as an important
new medium of communication. The pages andhyperlinks of the Web can be viewed as nodes (vertices) and links (edges) of a network (graph). When
there is a hyperlink from one Web page to another, wecan consider that the administrator of the former Web
page recommends the latter Web page or that these
two Web pages have some relationship in the realworld. Therefore, the network structure of the Web isuseful information. For example, like the HITS
(hyperlink-induced topic search) algorithm or thePageRank algorithm of Google, this structure is used
to improve Web search engines [1].
The Web is a growing network that is constantly
evolving as a result of the addition of new pages andhyperlinks. Therefore, modeling the network growth
dynamics of the Web is an important research issue.
In particular, such a model could be useful to predict
the network structure of the Web in the future and to
deeply understand the ecology of the Web [2].
2. Scale-free networks
Recently, considerable attention has been devoted
to exploring real-world complex networks and there
has been progress in research that aims to clarify thestatistical regularities of various large-scale networks† NTT Communication Science Laboratories
Soraku-gun, 619-0237 Japan
E-mail: kimura@cslab.kecl.ntt.co.jp

24

and model their growth processes [3], [4]. A fundamental characteristic of any network is the degree distribution, which is defined as the distribution of thenumber of links for every node in the network. Figure 1(a) gives an example of the degree of a node in
a network. Recent empirical results show that for
many large-scale real-world networks, including theWeb, the degree distributions do not follow Poisson
distributions*1, which the classical random graph theory*2 expects, but possess power-law tails [2]-[4].
Figure 1(b) shows the degree distribution for the network of mp3-related Web pages*3 on a double-logarithmic scale. Here, note that the power law isexpressed by the linearity of the distribution curve.
These observations suggest that for many large-scale
real-world networks including the Web, the growth
processes cannot be completely random but may
obey certain self-organization principles. Moreover,after they have grown sufficiently, their degree distributions must have power-law tails.
*1 Poisson distribution: The probability distribution that arises whencounting the number of occurrences of a rare event such as thenumber of car accidents in one day. If the degree distribution of anetwork follows a Poisson distribution, the probability that thereexists a node with a very high degree called a hub becomes exponentially low. However, if the degree distribution has a power-law
tail, this probability cannot become too low, so hubs can exist insuch a network.
*2 Classical random graph theory: This is the mathematical theory
for the statistical properties of random graphs. Studies of it werebegun by Erdösh and Rény in about 1960. They studied the staticgraphs generated by randomly adding edges to a fixed set of vertices.
*3 mp3: MPEG 1 Audio Layer 3. A popular format for compressing
digital audio files.

NTT Technical Review

Special FeatureProbability

1) Between 2) From an old node
old nodes
to a new node1003) From a newnode to an
old node

10–1
Power-law tail10–24) Between
new nodes

Old node
New node–3

Old link

10New link

This node hasa degree of 3.

(a) Example of thedegree of a node

10–4 010101102103104
Degree(b) Degree distribution for the networkof mp3-related Web pages

Fig. 1. Degree distributions.

Albert and Barabási discovered a network growthmodel satisfying these conditions [4]. The principal
ingredient of the Barabási-Albert (BA) model is amechanism of preferential attachment, in which theprobability that an existing node gains a new link is
proportional to the number of links that it currently
has (Fig. 2(a)). However, the degree distribution of
the BA model has been proved to follow a power law
with index of –3, although large-scale real-world networks can obey various power-law distributions.
Therefore, some variants of the BA model have been
proposed to construct power-law distributions withindices other than –3 [4].
Since a system with a power law is known to havea scale-free (scale-invariant) nature, the network
growth models with power-law degree distributions
are generally referred to as scale-free models. With
the aim of constructing a more precise statisticalmodel of a real-world growing network such as theWeb, NTT Communication Science Laboratories
proposed a new scale-free model for network growththat incorporates directional attachment and community structure [5].
3. Directional attachment
When a new link is created at a time-step, there are
four ways it can be attached: 1) from an old node toan old node, 2) from an old node to a new node, 3)from a new node to an old node, or 4) from a newnode to a new node (Fig. 2(b)). Every growing network has its own bias for these four cases. Namely,
the probabilities of each of these four cases occurring
Vol. 3 No. 3 Mar. 2005

The probability that an old node
gains a new link is proportional
to the number of links that it
currently has.
(a) Preferential attachment(the BA model)

Every growing network has its
own bias for these four cases.

(b) Directional attachment

Fig. 2. Mechanism for creating new links.

can change depending on the growing network to bemodeled. The mechanism that appropriately biases
these four cases in a new link creation is referred to as
directional attachment.
Therefore, given a growing network, for example, anetwork of Web pages belonging to a certain category, we can model the growth process more precisely
by incorporating the directional attachment that isappropriate for it [5].
4. Community structure
We can consider that the community structure of a
network is the decomposition of the set of nodes into
the clusters that arise from its undirected graph structure. Namely, a community is defined as a collectionof nodes in which each member node has more links
to nodes within the community than to nodes outside
it. One characteristic of the Web is the existence of acommunity structure, and the Web grows as various
clusters are formed. Namely, the following situation
can often be observed in its growth process: anincreasing number of links are created within each
community while the links between communities
remain sparse (Fig. 3(a)). Incorporating the community structure enables us to model this sort of detailed
growth process [5].
In an effort to identify communities, there havebeen several investigations using graph-theoretic
methods. However, those investigations treated only
static networks; that is, the numbers of nodes andlinks were not allowed to increase. Therefore, introducing the community structure into network growth25

Special Feature

Community 1
Community 1
Community 1

Time-step 0

Time-step 1

Time-step 2

Community 2

Community 2(a) Example of a growing network with two communities

Time-step 0

Time-step 1

Community 2

Time-step 2(b) Example of a growing network (observable data)

Fig. 3. Network growth.

models may be a promising approach.
5. Proposed model
Here, we outline our network growth model thatincorporates directional attachment and communitystructure. The number of communities and the number of links introduced at every time-step are fixed inadvance. Now, let us describe the process of creatinga new link in a network. First, both the community towhich the originating node belongs and the community to which the target node belongs are probabilistically chosen. Next, whether the nodes are new orold is probabilistically decided according to thedirectional attachment. Next, it is probabilisticallydecided according to the mixture of preferential anduniform attachment which nodes are chosen as theoriginating node and the target node. Thus, thegrowth dynamics is mathematically modeled as a stochastic process. However, there are many parametersthat should be adjusted in this model, such as thenumber of communities.
6. Learning algorithm and evaluation
To acquire a statistical model for the short-term
growth process of a growing network such as theWeb, we must make the proposed model learn based
26on the observed data. That is, we must adjust themodel parameters. Note that the observed data is
time-series data such as that illustrated in Fig. 3(b)and that the community structure shown in Fig. 3(a)is not given. At NTT Communication Science Laboratories, we have constructed an efficient learningalgorithm for the network growth model with directional attachment and community structure andexperimentally confirmed its effectiveness [5].
Using real Web data, we experimentally investigated the effectiveness of incorporating directional
attachment and community structure [5]. Figure 4
shows experimental results for the growing networkof mp3-related Web pages for three months. The prediction error is plotted with respect to the number ofcommunities for the models with and without directional attachment. We evaluated the ability of thelearned model from the prediction performance of theprobability distribution for a new link creation at thenext time-step. Figure 4 shows that the prediction
performance can be improved by incorporating directional attachment. We also observed that although theprediction performance can be raised by increasing
the number of communities, there can be an optimal
number of communities (11 in this case). Thisimplies that the prediction performance can beimproved by incorporating the community structure.
Therefore, incorporating directional attachment and
NTT Technical Review

Prediction error

Special Featurecompetitors and to predict the future
shares of the sites based on the observations [6].
3.2

Model without directional attachment

References

Model with directional attachment

2.8

Optimal model

2.4
13579111315

Number of communitiesFig. 4. Prediction performance for the growing network of mp3-related
Web pages.

community structure into a scale-free model enables
us to acquire a more precise statistical model for theshort-term growth process of a network such as theWeb.
Moreover, for the growing network of mp3-related
Web pages, the inferred community structure with 11
communities can be regarded as the optimal community structure obtained by taking into account the network growth. Namely, the proposed method enables
us to identify Web communities by acquiring the statistical model of the network growth dynamics.
7. Future work
We described research on modeling the growth
processes of Web networks based on the statisticallearning approach. The Web data set is huge and combines many types of features such as text, hyperlinks,images, and user behavior (log data). Moreover, theWeb changes over time. From the scientific and technological points of view, mining and modeling thisrich collection of data have become important andchallenging research issues. We aim to model theWeb dynamics as precisely as possible and to extract
useful information from the Web based on theacquired models. Currently, in an effort to solve theproblem of modeling fluctuations in the number ofvisitors to Web sites that form a particular market, weare attempting to categorize the sites into groups ofVol. 3 No. 3 Mar. 2005

[1] S. Chakrabarti, B. E. Dom, S. R. Kumar, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, D. Gibson, and J. Kleinberg, “Mining the Web’s link structure,” IEEE Computer, Vol. 32, No. 8, pp. 60-67,
1999.
[2] J. Kleinberg and S. Lawrence, “The structure of theWeb,” Science, Vol. 294, pp. 1849-1850, 2001.
[3] S. H. Strogatz, “Exploring complex networks,”
Nature, Vol. 410, pp. 268-276, 2001.
[4] R. Albert and A.-L. Barabási, “Statistical mechanicsof complex networks,” Reviews of Modern Physics,Vol. 74, pp. 47-97, 2002.
[5] M. Kimura, K. Saito, and N. Ueda, “Modeling ofgrowing networks with directional attachment andcommunities,” Neural Networks, Vol. 17, pp. 975988, 2004.
[6] M. Kimura, K. Saito, and N. Ueda, “Modeling share
dynamics by extracting competition structure,”
Physica D, Vol. 198, pp. 51-73, 2004.

Masahiro Kimura
Research Scientist, Emergent Learning
Research Group, Intelligent Communication
Laboratory, NTT Communication Science Laboratories.
He received the B.S., M.S., and Ph.D. degrees
in mathematics from Osaka University, Toyonaka, Osaka in 1987, 1989, and 2000, respectively.
He joined NTT in April 1989. From April 1989
to August 1994, he worked at NTT Human Interface Laboratories, Kanagawa and Tokyo, where
he was engaged in computer graphics research.
From September 1994 to January 2000, heworked at NTT Communication Science Laboratories, Kyoto, where he was engaged in neuralnetworks research. From February 2000 to September 2001, he worked at NTT-ME Corporation, Tokyo, where he was mainly engaged indeveloping the 401k system of Japan Investor
Solution & Technologies (JIS&T) Co., Ltd.
Since October 2001, he has worked at NTT Communication Science Laboratories, Kyoto, where
he has been engaged in complex systems
research. He is a member of the MathematicalSociety of Japan, the Japanese Neural Networks
Society, the Japan Society for Industrial andApplied Mathematics, and the Institute of Electronics, Information and Communication Engineers of Japan.

27