Decoding the structure of the WWW: facts versus sampling biases

@misc{citeulike:387386, abstract = {The understanding of the immense and intricate topological structure of the World Wide Web (WWW) is a major scientific and technological challenge. This has been tackled recently by characterizing the properties of its representative graphs in which vertices and directed edges are identified with web-pages and hyperlinks, respectively. Data gathered in large scale crawls have been analyzed by several groups resulting in a general picture of the WWW that encompasses many of the complex properties typical of rapidly evolving networks. In this paper, we report a detailed statistical analysis of the topological properties of four different WWW graphs obtained with different crawlers. We find that, despite the very large size of the samples, the statistical measures characterizing these graphs differ quantitatively, and in some cases qualitatively, depending on the domain analyzed and the crawl used for gathering the data. This spurs the issue of the presence of sampling biases and structural differences of Web domains that might induce properties not representative of the actual global underlying graph. In order to provide a more accurate characterization of the Web graph and identify observables which are clearly discriminating with respect to the sampling process, we study the behavior of degree-degree correlation functions and the statistics of reciprocal connections. The latter appears to enclose the relevant correlations of the WWW graph and carry most of the topological information of theWeb. The analysis of this quantity is also of major interest in relation to the navigability and searchability of the Web.}, author = {Serrano, Angeles M. and Maguitman, Ana and Boguna, Marian and Fortunato, Santo and Vespignani, Alessandro }, citeulike-article-id = {387386}, eprint = {cs.NI/0511035}, keywords = {pagerank, webir}, month = {Nov}, posted-at = {2006-04-03 13:18:25}, priority = {2}, title = {Decoding the structure of the WWW: facts versus sampling biases}, url = {http://arxiv.org/abs/cs.NI/0511035}, year = {2005} }

TY - ELEC ID - citeulike:387386 L3 - citeulike-article-id:387386 TI - Decoding the structure of the WWW: facts versus sampling biases N2 - The understanding of the immense and intricate topological structure of the World Wide Web (WWW) is a major scientific and technological challenge. This has been tackled recently by characterizing the properties of its representative graphs in which vertices and directed edges are identified with web-pages and hyperlinks, respectively. Data gathered in large scale crawls have been analyzed by several groups resulting in a general picture of the WWW that encompasses many of the complex properties typical of rapidly evolving networks. In this paper, we report a detailed statistical analysis of the topological properties of four different WWW graphs obtained with different crawlers. We find that, despite the very large size of the samples, the statistical measures characterizing these graphs differ quantitatively, and in some cases qualitatively, depending on the domain analyzed and the crawl used for gathering the data. This spurs the issue of the presence of sampling biases and structural differences of Web domains that might induce properties not representative of the actual global underlying graph. In order to provide a more accurate characterization of the Web graph and identify observables which are clearly discriminating with respect to the sampling process, we study the behavior of degree-degree correlation functions and the statistics of reciprocal connections. The latter appears to enclose the relevant correlations of the WWW graph and carry most of the topological information of theWeb. The analysis of this quantity is also of major interest in relation to the navigability and searchability of the Web. KW - pagerank KW - webir AU - Serrano, Angeles AU - Maguitman, Ana AU - Boguna, Marian AU - Fortunato, Santo AU - Vespignani, Alessandro PY - 2005/Nov/08/ UR - http://arxiv.org/abs/cs.NI/0511035 ER -