Curvature of co-links uncovers hidden thematic layers in the World Wide Web

By Jean-Pierre Eckmann, Elisha Moses. Proceedings of the National Academy of Sciences of the United States of America, 2001

324 citations recorded by the source corpus.

Beyond the information stored in pages of the World Wide Web, novel types of “meta-information” are created when pages connect to each other. Such meta-information is a collective effect of independent agents writing and linking pages, hidden from the casual user. Accessing it and understanding the interrelation between connectivity and content in the World Wide Web is a challenging problem [Botafogo, R. A. & Shneiderman, B. (1991) in Proceedings of Hypertext (Assoc. Comput. Mach., New York), pp. 63–77 and Albert, R. & Barabási, A.-L. (2002) Rev. Mod. Phys. 74, 47–97]. 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, because triangles indicate a transitive relation. The importance of triangles is quantified by the clustering coefficient [Watts, D. J. & Strogatz, S. H. (1999) Nature (London) 393, 440–442], which we interpret as a curvature [Bridson, M. R. & Haefliger, A. (1999) Metric Spaces of Non-Positive Curvature (Springer, Berlin)]. This curvature defines a World Wide 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 Caenorhabditis elegans, using the same methods.

Subfields: Cognitive Neuroscience, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/ac2c76b806c531ec6345f4ca11341d3883090900

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cognitive Neuroscience

In Sociology and Political Science

Citations in the corpus

Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, background): “maximum-flow/min-cut theorem and in [231] groups of connect ed pages with high curvature (a geometrical interpretation of the clustering coefficien t) were associated with specific topics.”
Community Structure in Graphs (2007, methodology): “This is another method where communities are deﬁned based on a local criterion [89].”
Community detection in graphs (2009, methodology): “Anothermethod, where communities are defined based on a local criterion, was presented by Eckmann andMoses [334].”
Functional topology in a network of protein interactions (2004, background): “Complex biological and artificial networks show graph properties that relate to the function these networks carry (Milo et al., 2002; Yook et al., 2002; Tu, 2000; Williams et al., 2002; Eckmann and Moses, 2002; Girvan and Newman, 2002; Stelling et al., 2002).”
Wedge sampling for computing clustering coefficients and triangle counts on large graphs † (2013, methodology): “Triangles have also been used in graph mining applications such as spam detection and finding common topics on the WWW [6,7].”
Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case (2011, background): “g application of polynomial concentration is the problem of counting the number of triangles in a very large undirected graph which has applications in ﬁnding the hidden thematic structure of the web [5] and usage as a feature to assist the classiﬁcation of web activity as spamming or not [3]. Tsour”
Comparing community structure identification (2005, background): “om a node to one of its neighbours is necessarily 1, this is not generally true for a random walker, which could easily make a 16 (a) (b) Figure 5: How clustering is related to curvature according to [13]. For a node i, the shortest path distance between any of its neighbours will be either 1, if th”
There exist graphs with super-exponential Ramsey multiplicity constant (2008, background): “First, it is easily observed that the complete graph is positively curved by the intuitive clustering coe‐cient deflnition of [ 8 ].”
Statistical mechanics of networks. (2004, background): “Behavior of this kind is seen, for example, in the world wide web, email networks, and neural and metabolic networks [33, 34, 35].”
DOULION: counting triangles in massive graphs with a coin (2009, background): “Eckman and Moses in [13] showed how triangles can be used to uncover the hidden thematic structure of the web.”
The Structure and Function of Complex Networks (2003, background): “Examples include the Internet, the World Wide Web, social networks of acquaintance or other connections between individuals, organizational networks and networks of business relations between companies, neural networks, metabolic networks, food webs, distribution networks such as blood vessels or po”
Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, background): “Computing the clustering and the distribution of triangles are important to quantitatively assess the community structure of social networks [29] or the thematic structure of large, hyperlinked document collections, such as the Web [16].”