The Web as a Graph: Measurements, Models, and Methods
The Web as a Graph: Measurements, Models, and Methods
复制标题
DOI：
10.1007/3-540-48686-0_1
复制
发表时间：
1999-07
影响因子：
6.4
通讯作者：
J. Kleinberg;Ravi Kumar;P. Raghavan;S. Rajagopalan;A. Tomkins
中科院分区：
文献类型：
--
作者：
J. Kleinberg;Ravi Kumar;P. Raghavan;S. Rajagopalan;A. Tomkins
万维网的页面和超链接可以看作是有向图中的节点和边。这张图是一个令人着迷的研究对象：它现在有数亿个节点，超过10亿个链接，并且似乎随着时间呈指数级增长。有很多理由——数学的、社会学的和商业的——来研究这个图表的演变。在本文中，我们首先描述了在Web图上运行的两种算法，解决了Web搜索和自动社区发现的问题。然后，当我们在Web上运行这些算法时，我们报告了这个图的一些度量值和属性。最后，我们观察到传统的随机图模型不能解释这些观察结果，我们提出了一个新的随机图模型族。这些模型指出了随机图研究的一个丰富的新子领域，并提出了关于网络上图算法分析的问题。
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons — mathematical, sociological, and commercial — for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.