Beyond the information stored in pages of the World Wide Web, novel types of "meta-information" are created when they connect to each other. This information is a collective effect of independent users writing and linking pages, hidden from the casual user. Accessing it and understanding the inter-relation of connectivity and content in the WWW is a challenging problem (1-4). We demonstrate here how thematic relationships can be located precisely by looking only at the graph of hyperlinks, gleaning content and context from the Web without having to read what is in the pages. We begin by noting that reciprocal links (co-links) between pages signal a mutual recognition of authors, and then focus on triangles containing such links, since triangles indicate a transitive relation. The importance of triangles is quantified by the clustering coefficient (5) which we interpret as a curvature (6, 7). This defines a Web-landscape whose connected regions of high curvature characterize a common topic. We show experimentally that reciprocity and curvature, when combined, accurately capture this meta-information for a wide variety of topics. As an example of future directions we analyze the neural network of C. elegans (8,9), using the same methods. The Web is a graph (10, 11) that is continuously being expanded by an enormous number of independent agents. Millions of users add pages in an uncoordinated way, but in doing so they must obey clear rules on how to address other pages (12). Beyond the information placed by the users directly in individual pages, their unified action creates a cooperative meta-information whose locus is in the connectivity of the network. By meta-information we mean here information that is based solely on the graph structure of the WWW, and which reveals strong contextual group- * Dépt. ing. This type of information should be contrasted to that of a very informative but secluded page, that is an archive of information (a "wise hermit"). Further on, we will compare our new meta-information to earlier work. The billions of pages and links of the WWW create a maze of confusing and almost unmanageable complexity. To navigate through it and to find pages of interest, users rely on the help of search engines (13). These send out small, automated programs (robots) that roam the Web, retrieve links and note keywords as they create a mirror image of the Web that can be stored within one room of storage data, ready for easy access. The Web remains intelligible to its human users precisely because it is constantly analyzed and monitored by these automatic agents. Robot activity dominates Web traffic and accounts for up to 70% of the total queries made at certain sites we studied. Because of the breadth of their search, robots obtain a clearer view of the Web than the common user. It is therefore useful to adopt the perspective of robots, without having to define meaning or content, looking only at the identification tag of pages (URL addresses) and their links (14) . To avoid the difficulty of having to know the complete Web graph we use robots which explore some locally visible pieces that can be found by starting from a given page and progressing along its links. An analogy may be drawn with classical neurobiology (15), where a neuron takes up dye which then traces out its connections. Having defined our aim of revealing meta-information in the form of hidden thematic structures, we implement it by a novel combination of a number of key ideas: Clustering, co-links, triangles, and curvature. The clustering regroups a "home" page with the pages in its sub-directories. The co-links are then the result of independent agents linking their pages. Triangles capture transitivity, which we measure by the associated notion of curvature. Using it, we show that practically all the connective information depends on co-links. Thus, our method reveals a new geometric view of the locus of information in networks, which is not "put there" but "happens" as a collective effect.
REF approached the Web community issue in a Web graph from a local perspective.
Curvature of co-links uncovers hidden thematic layers in the World Wide Web
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Physics Computer Science Medicine