Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
arXiv:cond-mat/0110338 · doi:10.1073/pnas.032093399
Abstract
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. 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 (Watts) which we interpret as a curvature (Gromov,Bridson-Haefliger). 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 (White, Wood), using the same methods.
8 pages, 5 figures, expanded version of earlier submission with more examples
References in corpus (1)
Cited by in corpus (77)
- The structure and function of complex networks
- Community detection in graphs
- Near linear time algorithm to detect community structures in large-scale networks
- Evolution of networks
- Comparing community structure identification
- Hierarchical Organization in Complex Networks
- Community detection in complex networks using Extremal Optimization
- Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
- The statistical mechanics of networks
- The topological relationship between the large-scale attributes and local interaction patterns of complex networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Detecting communities in large networks
- Networks and Cities: An Information Perspective
- Subgraphs in random networks
- Local modularity measure for network clusterizations
- Forman curvature for complex networks
- The Large Scale Curvature of Networks
- Triadic Measures on Graphs: The Power of Wedge Sampling
- Percolation in living neural networks
- Comparative analysis of two discretizations of Ricci curvature for complex networks
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- Structural transitions in scale-free networks
- Emergence of Soft Communities from Geometric Preferential Attachment
- Evolving networks with distance preferences
- Predictability of conversation partners
- Subgraphs and network motifs in geometric networks
- Hide and seek on complex networks
- Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
- Subgraph Networks with Application to Structural Feature Space Expansion
- Using Curvature and Markov Clustering in Graphs for Lexical Acquisition and Word Sense Discrimination
- Coexistence of opposite opinions in a network with communities
- Accuracy and Precision of Methods for Community Identification in Weighted Networks
- Modeling Dynamics of Information Networks
- Systematic evaluation of a new combinatorial curvature for complex networks
- Discrete Ricci curvatures for directed networks
- Degree Relations of Triangles in Real-world Networks and Models
- Ollivier-Ricci curvature convergence in random geometric graphs
- Approximately Counting Triangles in Sublinear Time
- ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
- The Number of Large Graphs with a Positive Density of Triangles
- Approximate Triangle Counting
- Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning
- A simpler sublinear algorithm for approximating the triangle count
- Inference for graphs and networks: Extending classical tools to modern data
- A Method for Group Extraction and Analysis in Multilayer Social Networks
- Graph Contrastive Learning with Cohesive Subgraph Awareness
- Short Cycles Connectivity
- Mathematical and Algorithmic Analysis of Network and Biological Data
- Random graph model with power-law distributed triangle subgraphs
- Nonlinear Diffusion Through Large Complex Networks Containing Regular Subgraphs
- Evolution of Directed Triangle Motifs in the Google+ OSN
- A Hierarchy of Graph Neural Networks Based on Learnable Local Features
- Decoding the structure of the WWW: facts versus sampling biases
- Network Community Detection on Metric Space
- Engineering a Distributed-Memory Triangle Counting Algorithm
- Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case
- On Approximating the Number of -cliques in Sublinear Time
- Distributed-Memory Parallel Algorithms for Counting and Listing Triangles in Big Graphs
- Active Community Detection in Massive Graphs
- Sampling Subgraph Network with Application to Graph Classification
- Region Detection in Markov Random Fields: Gaussian Case
- Parallel Triangle Counting in Massive Streaming Graphs
- Forman-Ricci flow for change detection in large dynamic data sets
- Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
- Nearest Neighbor search in Complex Network for Community Detection
- Ricci Curvature Based Volumetric Segmentation of the Auditory Ossicles
- Gromov Centrality: A Multi-Scale Measure of Network Centrality Using Triangle Inequality Excess
- Negatively Curved Graphs
- Si nano-VINe: Electrical Percolation in Quantum-Confined nc-Si:SiO2 Systems
- Ground state energy of -state Potts model: the minimum modularity
- A space efficient streaming algorithm for triangle counting using the birthday paradox
- Spectral analysis of communication networks using Dirichlet eigenvalues
- How Hard is Counting Triangles in the Streaming Model
- EqRank: A Self-Consistent Equivalence Relation on Graph Vertexes
- A quantitative analysis of concepts and semantic structure in written language: Long range correlations in dynamics of texts
- Clustering SPIRES with EqRank
- REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel