Decomposing the Web Graph into Parameterized Connected Components

Tomonari MASADA; Atsuhiro TAKASU; Jun ADACHI

Decomposing the Web Graph into Parameterized Connected Components

Tomonari MASADA, Atsuhiro TAKASU, Jun ADACHI

Full Text Views

0

Share
Cite this

Summary :

We propose a novel method for Web page grouping based only on hyperlink information. Because of the explosive growth of the World Wide Web, page grouping is expected to provide a general grasp of the Web for effective information search and netsurfing. The Web can be regarded as a gigantic digraph where pages are vertices and links are arcs. Our grouping method is a generalization of decomposition into strongly connected components, in which each group is constructed as a subset of a strongly connected component. Moreover, group sizes can be controlled by adjusting a parameter, called the threshold parameter. We call the resulting groups parameterized connected components (PCCs). The algorithm is simple and admits parallelization. Notably, we apply Dijkstra's shortest path algorithm in our grouping method. This paper also includes experimental results for 15 million Web pages, which show the contribution of our method to efficient Web surfer navigation.

Publication: IEICE TRANSACTIONS on Information Vol.E87-D No.2 pp.380-388

Publication Date: 2004/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Information Processing Technology for Web Utilization)

Category

Cite this

Copy

Tomonari MASADA, Atsuhiro TAKASU, Jun ADACHI, "Decomposing the Web Graph into Parameterized Connected Components" in IEICE TRANSACTIONS on Information, vol. E87-D, no. 2, pp. 380-388, February 2004, doi: .
Abstract: We propose a novel method for Web page grouping based only on hyperlink information. Because of the explosive growth of the World Wide Web, page grouping is expected to provide a general grasp of the Web for effective information search and netsurfing. The Web can be regarded as a gigantic digraph where pages are vertices and links are arcs. Our grouping method is a generalization of decomposition into strongly connected components, in which each group is constructed as a subset of a strongly connected component. Moreover, group sizes can be controlled by adjusting a parameter, called the threshold parameter. We call the resulting groups parameterized connected components (PCCs). The algorithm is simple and admits parallelization. Notably, we apply Dijkstra's shortest path algorithm in our grouping method. This paper also includes experimental results for 15 million Web pages, which show the contribution of our method to efficient Web surfer navigation.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e87-d_2_380/_p

Copy

@ARTICLE{e87-d_2_380,
author={Tomonari MASADA, Atsuhiro TAKASU, Jun ADACHI, },
journal={IEICE TRANSACTIONS on Information},
title={Decomposing the Web Graph into Parameterized Connected Components},
year={2004},
volume={E87-D},
number={2},
pages={380-388},
abstract={We propose a novel method for Web page grouping based only on hyperlink information. Because of the explosive growth of the World Wide Web, page grouping is expected to provide a general grasp of the Web for effective information search and netsurfing. The Web can be regarded as a gigantic digraph where pages are vertices and links are arcs. Our grouping method is a generalization of decomposition into strongly connected components, in which each group is constructed as a subset of a strongly connected component. Moreover, group sizes can be controlled by adjusting a parameter, called the threshold parameter. We call the resulting groups parameterized connected components (PCCs). The algorithm is simple and admits parallelization. Notably, we apply Dijkstra's shortest path algorithm in our grouping method. This paper also includes experimental results for 15 million Web pages, which show the contribution of our method to efficient Web surfer navigation.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Decomposing the Web Graph into Parameterized Connected Components
T2 - IEICE TRANSACTIONS on Information
SP - 380
EP - 388
AU - Tomonari MASADA
AU - Atsuhiro TAKASU
AU - Jun ADACHI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2004
AB - We propose a novel method for Web page grouping based only on hyperlink information. Because of the explosive growth of the World Wide Web, page grouping is expected to provide a general grasp of the Web for effective information search and netsurfing. The Web can be regarded as a gigantic digraph where pages are vertices and links are arcs. Our grouping method is a generalization of decomposition into strongly connected components, in which each group is constructed as a subset of a strongly connected component. Moreover, group sizes can be controlled by adjusting a parameter, called the threshold parameter. We call the resulting groups parameterized connected components (PCCs). The algorithm is simple and admits parallelization. Notably, we apply Dijkstra's shortest path algorithm in our grouping method. This paper also includes experimental results for 15 million Web pages, which show the contribution of our method to efficient Web surfer navigation.
ER -