WebRelievo is a system for browsing and analyzing the evolution of the web graph structure based on link analysis. This system enables us to answer historical questions, and to detect changes in topics on the Web. WebRelievo extracts web pages related to a focused page using link analysis, and visualizes the evolution of their relationships with a time series of graphs. This visualization enables us to understand when related pages appeared, and how their relationships have evolved over time. The user can interactively browse those related pages by changing the focused page and by changing layouts of graphs. WebRelievo is implemented on six Japanese web archives crawled from 1999 to 2003.
The Web has been growing and changing its structure by reflecting real social activities. For example, when important events such as war and terrorism occur in the real world, many web pages about these events are created, and become connected by hyperlinks. Since hyperlinks represent attention of page authors to the destination pages, we could detect changes in trends on the Web from the evolution of the hyperlink structure. Now, it becomes an important issue to track structural changes in the web.
We propose the WebRelievo system for browsing and analyzing the evolution of the web structure based on a series of large web archives. Currently, we use six web archives of Japanese web pages crawled from 1999 to 2003. This system allows us to answer historical questions, and to detect changes in topics on the Web. Figure 1 shows a screen snapshot of WebRelievo. Six graphs represent the same part of those six web archives. In those graphs, each node represents the URL, and each edge represents the relationship between URLs extracted by link analysis. These graphs are aligned from left to right then top to bottom by their time. Positions of URLs are synchronized over time, so that the user can easily recognize the changes in graphs.
To visualize the structure of the web, we do not use directly the web graph, in which nodes are web pages and edges are hyperlinks. It is because the web graph itself is too complicated to understand and to visualize its structure. Since, famous web pages are linked to by thousands of other pages, it is difficult to display even a subgraph of the web in limited screen space.
Therefore, WebRelievo visualizes relationships between web pages calculated by a link analysis technique,
and show the evolution of their relationships. To calculate relationships, we use a related page algorithm
(RPA) based on HITS [
For all web archives, WebRelievo makes derivation graphs around a focused page given by the user, then align these graphs as shown in Figure 1. The direction of each edge is shown by its thickness at each ends. That is, each edge starts at the thick end, and goes to the thin end.
This visualization enables the user to understand when related pages appeared and disappeared, and how their relationships have changed over time. In addition, the user can interactively browse those related pages by changing the focused page and by dragging nodes.
The rest of this paper is organized as follows. Section 2 shows some related work. Section 3 explains details of the derivation graph. Section 4 describes how to visualize the evolution and how the user can interact with WebRelievo. Section 5 shows some evolution examples with WebRelievo. The system architecture and implementation are described in Section 6. Finally, we conclude in Section 7. 2 2.1
There have been some work on visualizing evolution of information structure [
Our previous work [
WebRelievo uses a related page algorithm (RPA) that takes a seed page as an input, and outputs related
pages to the seed. We adopt a RPA based on the notion of authorities and hubs proposed by Kleinberg [
RPA first builds a subgraph of the Web near the seed, and extracts densely connected authorities and
hubs in the graph using HITS. Then authorities are returned as related pages. There are some variants
of RPA based on HITS, such as Companion [6]. Since existing RPAs provide insufficient precision, we use
an improved algorithm Companion– [
There are also some RPAs that are not based on HITS. Lempel and Moran [
In this section, we first introduce the notion of derivation graph proposed in [
Since the structure of the web graph is too complicated to visualize and to understand, we simplify the web graph using a related page algorithm (RPA) that returns related pages to a given page. That is, we visualize how each page derives other pages by RPA. To represent such relationships, we use a notion of derivation graph DG = (V; E). Each node v 2 V represents a page. Each directed edge e 2 E from a node p to another node q, represents that p derives q as one of the top N related pages.
An appropriate value of N would differ according to the focused topic. By changing the parameter N , we can change the density of the derivation graph. When N becomes smaller, DG only connects more densely connected authorities, and becomes sparser. When N becomes larger, DG connects less densely connected authorities, and DG becomes denser. Note that the notion of DG does not depend on a specific RPA. We can use any RPAs, such as HITS, Companion, and SALSA, for building DG.
When a DG is still complicated to understand, we can make the DG more simple by extracting mutually
connected nodes by derivations in DG. That is, p derives q and vice versa. Using a HITS based RPA,
we found that such nodes are closely related in our previous work[
WebRelievo shows the evolution, using a time series of derivation graphs built from a time series of web archives: fDGt = (Vt; Et)j1 · t · T g. The subscript t denotes the time when each archive crawled (1 is the first time and T is the last time). Since each DGt is too large to browse in a single screen, WebRelievo extracts and shows subgraphs of DGs around a given focused node p: fDGt(p) = (Vt(p); Et(p))j1 · t · T g.
To show appearance and disappearance of all nodes related to p over time, we extract pages related to p for each time, and track all of these pages. The following is the process to build a time series of those subgraphs: 1. For each time t, extract a set Rt(p) of nodes related to p. It means that each node in Rt(p) is pointed to by p in DGt. 2. For each DGt(p), Vt(p) = Vt \ ([tRt(p)).
3. For each DGt(p), Et(p) = f(u; v) 2 Etju; v 2 Vt(p)g. 4
WebRelievo visualizes a time series of DG using an automatic and dynamic graph layout algorithm based
on a kind of force-directed model [
² The same node should be located at the same position over multiple DGs.
² Changes in nodes and edges of neighboring DGs should be easily recognized. 4.1
To satisfy the first requirement, we modify the force-directed model by adding the feature to synchronize the position of the same node in multiple DGs. The force-directed model considers a graph as a physical system, in which attractive forces Fa are exerted on all pairs of connected nodes, and repulsive forces Fr are exerted on all pairs of nodes. In WebRelievo, Fa and Fr is defined as a function of the distance d between two nodes as follows:
Fa(d) = d2=k2; Fr(d) = ¡k=d
The synchronization of node positions is performed between neighboring DGs. That is, each node in each DG is attracted to the position of the same node in the previous and next DGs. We add the following two forces for each node.
Fprev(dp) = dp=2; Fnext(dn) = dn=2 In these equations, dp and dn are the distances from the node to the same node in the previous and next DG, respectively. These distances are zero, when the same node does not exist in the neighboring DGs.
Initially, nodes are randomly located in each panel, then each nodes are iteratively moved by those forces. The layout is fixed, when the total movement of nodes become less than a threshold. This iterative layout is shown by animation in WebRelievo. 4.2
For the second requirement, nodes and edges are colored by their types of changes. For example, if a node or an edge appeared at time t, we use a red color for it. In this way, the user can see what kinds of changes have occurred and will occur on each node and edge.
Each DGt(p) is compared with the previous one DGt¡1(p), and the next one DGt+1(p), then changes in each node (or edge) are classified into four types and colored as follows: Stay–Stay When the node (or edge) exists in both DGt¡1 and DGt+1, it is colored black to show its stability.
Stay–Disappear When the node (or edge) exists in DGt¡1, but does not exist in DGt+1, it is colored light gray to show its stay from t ¡ 1 and disappearance at t + 1.
Appear–Stay When the node (or edge) does not exist in DGt¡1, and exists in DGt+1, it is colored red to show its appearance and stay to t + 1.
Appear–Disappear When the node (or edge) exists neither in DGt¡1 and in DGt+1, it is colored light red to show its volatility. 4.3
WebRelievo supports the following user interaction.
² The user can designate the focused URL by typing the URL in the input box, which is in the topleft of Figure 1. Then all derivation graphs around the URL are built and displayed. When the user designate another URL in the input box, graphs are built for the another URL, and merged to existing graphs. The same operation can be done on existing URL using a pop-up menu. ² The user can scroll and zoom into graphs. These kinds of changes in a graph are immediately propagated to all graphs for keeping layouts synchronized. Nodes in all graphs can be moved by dragging. When the user dragged a node in a graph, the node with the same URL is moved to the same position in each graphs. Layouts of all graphs are re-calculated and animated by the force-directed model, simultaneously. The user can easily keep track of the evolution after those operations. ² The user can examine the effect of parameter N in Section 3, by dynamically changing N with the slider that is in the top-center of Figure 1. When N is changed by the user, all graphs are immediately changed using N . ² The user can choose visualization of graphs from DG and SDG (See Section 3). When SDG is chosen, the user can reveal asymmetric edges around a selected URL using the pop-up menu of the URL. This change is also propagated to all graphs. 5
In this section, we show two evolution examples with WebRelievo. The first example in Figure 2 shows the evolution of P2P file sharing systems. In this case, the user wants to know the history of P2P systems, and designates the URL of a famous P2P system Kazaa (www.kazaa.com). Figure 2 shows the evolution by SDG (Figure 1 uses DG). From this result, the user can see that the first P2P system is Napster, and then various systems appeared such as Gnutella (2000), WinMX (2001), and Kazaa (2001). Famous systems became densely connected, and formed an almost clique. Year 1999 2000 2001 2002 2003 2003
The second example shows the evolution of search engines for mobile phone internet services (mainly for the i-mode service of NTT DoCoMo). In this case, the user want to know how the trend of those search engines has changed, and designate a famous search engine (mobile.yahoo.co.jp). In Figure 3, we can clearly see the changes in the trend of i-mode search engines. In 1999, search engines for i-mode were mainly provided by small companies, and they formed a clique. In 2000, major companies such as Yahoo! and Lycos began to provide i-mode search engines, and gradually the clique moved to these major companies. In 2003, the clique in 1999 was disappeared. 6
The architecture overview of WebRelievo is shown in Figure 4. WebRelievo is based on three databases built from web archives. We use six web archives of Japanese web pages crawled from 1999 to 2003 (See Table 1). Our crawler collected pages in the breadth-first order. From 2001, the number of pages became more than twice of the 2000 archive, since we improved the crawling rate. Until 2002, we collected pages in only .jp domain. From 2003, we began to collect pages in other domains, such as .com, if they are written in Japanese. Those collected documents are stored in the document archive on the right-bottom of Figure 4. Each document can be retrieved by its URL and the time of crawling.
From each archive, we built a link database (on the right-center of Figure 4) with URLs and links by extracting anchors from all pages in the archive. Our link database included not only URLs inside the archive, but also URLs outside pointed to by inside URLs. As a result, the graph included URLs outside .jp domain, such as .com and .edu. Table 1 also shows the number of links and the total URLs. For efficient link analysis, each link database is implemented as a main-memory database that provided out-links and in-links of a given URL. Its implementation was similar to the connectivity server [1].
The related page database on the right-top of Figure 4 is used to speed up the retrieval of derivation graphs. It stores pre-calculated results of RPA for popular URLs. The popularity of a URL is determined by the number of in-links. In our implementation, we pre-calculate related pages for URLs that have three or more in-links from other web servers.
The related page manager, in the center of Figure 4, provides information of derivation graphs to the evolution viewer on the top-left of Figure 4. This manager builds subgraphs of DGs for the focused URL using the related page database. When required URLs are not stored in the related page database, it calculates related pages by RPA using the link database. The RPA used by the manager can be changed to any RPA based on link analysis. In that case, the related page database should be also replaced.
The evolution viewer is the user interface of WebRelievo. The viewer displays DGs provided by the
related page manager. We use the TouchGraph [
WebRelievo can detect detailed changes in relationships of pages. However, it is difficult to see the global changes in the Web. Now we are implementing clustering of web pages for showing larger areas of derivation graphs. We also plan to crawl the web more frequently, and visualize more continuous evolution of the web. [1] Krishna Bharat, Andrei Broder, Monika Henzinger, Puneet Kumar, and Suresh Venkatasubramanian.
The Connectivity Server: fast access to linkage information on the Web. In Proceedings of the 7th International World Wide Web Conference, pages 14–18, 1998. [2] Krishna Bharat and Monika Henzinger. Improved Algorithms for Topic Distillation in a Hyperlinked
Environment. In Proceedings of ACM SIGIR ’98, pages 104–111, 1998. [3] Chaomei Chen and Leslie Carr. Visualizing the evolution of a subject domain: A case study. In David Ebert, Markus Gross, and Bernd Hamann, editors, IEEE Visualization ’99, pages 449–452, San Francisco, 1999. [4] Chaomei Chen and Steven Morris. Visualizing Evolving Networks: Minimum Spanning Trees versus
Pathfinder Networks. In IEEE Visualization 2003, pages 67–74, 2003. [5] Ed H. Chi, James Pitkow, Jock D. Mackinlay, Peter Pirolli, Rich Gossweiler, and Stuart K. Card.
Visualizing the Evolution of Web Ecologies. In Proceedings of ACM SIGCHI ’98, pages 400–407, 1998. [6] Jeffrey Dean and Monika R. Henzinger. Finding related pages in the World Wide Web. In Proceedings of the 8th World-Wide Web Conference, pages 389–401, 1999. [7] Gary W. Flake, Steve Lawrence, and C. Lee Giles. Efficient Identification of Web Communities. In Proceedings of KDD 2000, pages 150–160, 2000. Companion– takes a seed page as an input, then outputs related pages to the seed. It first builds a subgraph of the Web around the seed, and extracts authorities from the subgraph as related pages.
First, it builds a vicinity graph of a given seed, which is a subgraph of the web around the seed. A vicinity graph is a directed graph, (V; E), where nodes in V represent web pages, and edges in E represent links between these pages. V consists of the seed, a set of nodes pointing to the seed (B), and an another set of nodes pointed to by nodes in B (BF). When following outgoing links from each node in B, the order of links in the node is considered. Not all the links are followed but only R links immediately preceding the link pointing to the seed, and R links immediately succeeding the link. This is based on an observation that links to related pages are gathered in a small portion of a page.
To each edge, it assigns two kinds of weights, an authority weight and a hub weight for decreasing the influence of a single server. The authority weight is used for calculating an authority score of each node, and the hub weight is used for calculating a hub score of each node. Companion– uses the following weighting method proposed by Bharat and Henzinger [2]: (1) If two nodes of an edge are in the same server, the edge has the value 0 for both weights; (2) If a node has n incoming edges from the same server, the authority weight of each edge is 1=n; and (3) If a node has m outgoing edges to the same server, the hub weight of each edge is 1=m.
Then it calculates a hub score, h(n) and an authority score, a(n) for each node n in V . The following is the process of the calculation, where aw(n; m) and hw(n; m) represent the authority weight and the hub weight of the edge from n to m, respectively.
Step 2. Repeat the following calculation until h(n) and a(n) have converged for each node n.
For all node n in V , h(n) Ã P(n;m)2E a(m) £ hw(n; m) For all node n in V , a(n) Ã P(m;n)2E h(m) £ aw(m; n) Normalize h(n), so that the sum of squares to be 1.
Normalize a(n), so that the sum of squares to be 1.