Evolution of the Web Structure
Center for Web ResearchR, CS Dept., Univ. of Chile
Blanco Encalada 2120
Barbara J. Poblete
Center for Web Research, CS Dept., Univ. of Chile
Blanco Encalada 2120
In this paper we present the evolution of the structure of the Chilean Web between 2000 and 2002. Our results show that although the Web grows as expected, also a significant part of it disappears. In addition, some components are much more stable than others.
The Web is highly dynamic and little is known about its evolution. There are models that predict when a page will change, but that differs a lot from site to site. At a higher level, new websites appear and others disappear, but little is know how this happens. In this paper we present the evolution of the structure of the Chilean Web at the site and domain level, based on data gathered from a search engine targeted to this web domain, TodoCL.cl, between 2000 and 2002.
We define the Chilean Web as all the .cl sites plus all other sites found by crawling that have an IP belonging to a Chilean ISP. The first year the crawl started from an initial sample of sites, but subsequent years started from all .cl domains thanks to NIC Chile. Hence, the number of unconnected sites was low the first year. Also, the last crawl contains more dynamic pages, but this does not change the Web structure. Table 1 shows the sizes of the data used.
Our results present how the structure evolves, how sites migrate from one component to another component, and where sites appear and disappear. The changes are dramatic, corroborating that perhaps we are trying to study a process that is still in a transient phase, or that cannot be modeled in detail. This is a first step to measure and follow the evolution of part of the Web structure.
2. Web Structure
The most complete study of the Web structure  focus on page connectivity. One problem with this is that a page is not a logical unit (for example, a page can describe several documents and one document can be stored in several pages.) Hence, we decided to study the structure of how websites were connected, as websites are closer to be real logical units. Not surprisingly, we found in  that the structure in Chile at the website level was similar to the global Web, and hence we use the same notation of . The components are:
- MAIN, sites that are in the strong connected component of the connectivity graph of sites (that is, we can navigate from any site to any other site in this component);
- IN, sites that can reach MAIN but cannot be reached from MAIN;
- OUT, sites that can be reached from MAIN, but there is no path to go back to MAIN;
- ISLANDS, sites or group of sites that are not connect with MAIN; and
- other sites that can be reached from IN (T.IN, where T is an abbreviation for tentacles), sites in paths between IN and OUT (TUNNEL), and sites that only reach OUT (T.OUT).
In  we analyzed the data for year 2000 and we extended this notation by dividing the MAIN component into four parts:
- MAIN-MAIN, which are sites that can be reached directly from the IN component and can reach directly the OUT component;
- MAIN-IN, which are sites that can be reached directly from the IN component but are not in MAIN-MAIN;
- MAIN-OUT, which are sites that can reach directly the OUT component, but are not in MAIN-MAIN;
- MAIN-NORM, which are sites not belonging to the previously defined subcomponents.
Figure 1 shows all these components.
In Table 2 we give the relative size of each component. Notice the size of ISLANDS, which is near 50% of the Chilean Web sites. These sites are usually recent, and the main growth of the Web is in that component. The average update age of pages and sites, and their relation to structure and link ranking techniques is studied in  for the first two collections (2000 and 2001). We also considered domains in our study, although domains may contain sites that are quite different (for example, web hosting in an ISP provider using a common second-level domain).
|Component||Size (%) 2001||Size (%) 2002|
3. Evolution of the Structure
Web sites evolve inside the structure. First, a typical Web site starts as part of ISLANDS or IN (depending if it links or not a good Web site). If the site becomes popular and they also link known sites, it migrates to MAIN. If links are not well chosen or updated, they go to OUT. Table 3 shows the number of sites and domains that have appeared and disappeared from year to year.
In tables 4 and 5 we show the migration of sites among the components and domains, respectively. There are two ways of reading these tables. By columns we have from which component comes the sites/domains in each component. By rows, we see where are today the sites/domains of the components in the previous year. The last column and row represent the sites/domains that that do not longer exist (GONE) and the new sites/domains (NEW), respectively.
Notice that OUT and MAIN are stable components, because about 25% of the sites stay there. Is also interesting that MAIN grows from OUT by 20%, and that ISLANDS is the component with largest growth, but also death (see Table 5), followed by OUT.
Figures 2 and 3 show graphically the migration of sites and domains among the different components, using lighter colors to identify from where the sites came.
The overall number of sites of the Chilean Web is almost duplicating each year. However, that is the result of more than a 115% increase plus a 25% death. In addition, many sites, sometimes because of ignorance, do not allow crawlers to enter. For example, in 2001, 56% of the domains and 54% of the sites seem to had only one page. In fact, more than 25% of them had an initial Flash page or called a program.
We are currently studying the change at the level of pages related to the structure. For example, the largest 20 sites (in pages) in 2002 are all different from the largest sites in 2001. We are also analyzing the transitions over two years, to try to understand the time needed for the transitions.
We acknowledge the support of Millenium Nucleus Grant P01-029-F from Mideplan, Chile.
R.Kumar, F.Maghoul, P.Raghavan, S.Rajagopalan, R.Stata, and
Graph structure in the Web: Experiments and models.
In 9th World Wide Web Conference, 2000.
Baeza-Yates and Carlos Castillo.
Relating Web characteristics with link analysis.
In String Processing and Information Retrieval. IEEE ComputerScience Press, 2001.
- Ricardo Baeza-Yates, Felipe
Saint-Jean, and Carlos Castillo.
Web dynamics, structure, and link ranking.
In String Processing and Information Retrieval. Lecture Notes in CS, Springer, 2002.