Hierarchical structure and the prediction of missing links in networks

Abstract

Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (protein interaction networks, metabolic networks, or genetic regulatory networks), or communities in social networks. Here we present a general technique for inferring hierarchical structure from network data and demonstrate that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right-skewed degree distributions, high clustering coefficients, and short path lengths. We further show that knowledge of hierarchical structure can be used to predict missing connections in partially known networks with high accuracy, and for more general network structures than competing techniques. Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.

8 pages, 7 figures, 1 table, includes Supplementary Information

References in corpus (15)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Hierarchical organization of modularity in metabolic networks
• Functional cartography of complex metabolic networks
• Defining and identifying communities in networks
• Identity and Search in Social Networks
• Extracting the hierarchical organization of complex systems
• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Hierarchy and Feedback in the Evolution of the E. coli Transcription Network

Cited by in corpus (389)

• Community detection in graphs
• Link Prediction in Complex Networks: A Survey
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Predicting Missing Links via Local Information
• Finding statistically significant communities in networks
• Hyperbolic Geometry of Complex Networks
• The performance of modularity maximization in practical contexts
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• The map equation
• Scale-free networks are rare
• Consensus clustering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Finding overlapping communities in networks by label propagation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Kronecker Graphs: An Approach to Modeling Networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Popularity versus Similarity in Growing Networks
• Robustness and resilience of complex networks
• Link Prediction Based on Local Random Walk
• Simplicial Closure and higher-order link prediction
• Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
• Navigability of Complex Networks
• The ground truth about metadata and community detection in networks
• Robust Detection of Dynamic Community Structure in Networks
• Understanding brain networks and brain organization
• Spectral methods for network community detection and graph partitioning
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• An efficient and principled method for detecting communities in networks
• Structure and inference in annotated networks
• Uncovering the Temporal Dynamics of Diffusion Networks
• A Tutorial in Connectome Analysis: Topological and Spatial Features of Brain Networks
• Temporal Link Prediction using Matrix and Tensor Factorizations
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Fundamental structures of dynamic social networks
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• A Classification for Community Discovery Methods in Complex Networks
• Evaluating Link Prediction Methods
• Hyperbolic Graph Convolutional Neural Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Learning Latent Block Structure in Weighted Networks
• A sequential algorithm for fast clique percolation
• Personalized Recommendation via Integrated Diffusion on User-Item-Tag Tripartite Graphs
• Network structure from rich but noisy data
• Assessing the relevance of node features for network structure
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Community detection, link prediction, and layer interdependence in multilayer networks
• Identification of core-periphery structure in networks
• Link prediction in complex networks: a local na\"ıve Bayes model
• Random graphs containing arbitrary distributions of subgraphs
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• 20 years of network community detection
• Efficiently inferring community structure in bipartite networks
• Community extraction for social networks
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• On the Origins of Hierarchy in Complex Networks
• Poincaré Embeddings for Learning Hierarchical Representations
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Combining complex networks and data mining: why and how
• Tag-Aware Recommender Systems: A State-of-the-art Survey
• Network Mapping by Replaying Hyperbolic Growth
• A Scalable Generative Graph Model with Community Structure
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Topological data analysis of contagion maps for examining spreading processes on networks
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Topological Principles of Control in Dynamical Network Systems
• Random graph models for dynamic networks
• Hidden geometric correlations in real multiplex networks
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Systemic risk analysis in reconstructed economic and financial networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• Potential Theory for Directed Networks
• Progresses and Challenges in Link Prediction
• Superlinear Scaling for Innovation in Cities
• Curvature and temperature of complex networks
• Link Prediction with Node Clustering Coefficient
• Large-scale structure of a nation-wide production network
• Supervised Random Walks: Predicting and Recommending Links in Social Networks
• Predicting missing links and their weights via reliable-route-based method
• Bayesian stochastic blockmodeling
• Community detection and graph partitioning
• Link Prediction via Matrix Completion
• Structure and Response in the World Trade Network
• Link prediction via linear optimization
• Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model
• Model Selection for Degree-corrected Block Models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Influence Maximization in Continuous Time Diffusion Networks
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• The dynamical structure of political corruption networks
• Estimating network structure from unreliable measurements
• Multifractal Network Generator
• Spectral tripartitioning of networks
• Origin of the Scaling Law in Human Mobility: Hierarchical Organization of Traffic Systems
• Reconstructing networks with unknown and heterogeneous errors
• Bootstrapping topology and systemic risk of complex network using the fitness model
• Non-parametric Bayesian modeling of complex networks
• Link Prediction in Multiplex Networks based on Interlayer Similarity
• Mapping the evolution of scientific fields
• Removing spurious interactions in complex networks
• Cover time for random walks on arbitrary complex networks
• Finding missing edges in networks based on their community structure
• Reconstructing commuters network using machine learning and urban indicators
• Information filtering based on transferring similarity
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Link Prediction in Complex Networks: A Clustering Perspective
• Bayesian inference of network structure from unreliable data
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Consistencies and inconsistencies between model selection and link prediction in networks
• Exploring the structural regularities in networks
• Structural inference for uncertain networks
• Local dominance unveils clusters in networks
• Consistency of community structure in complex networks
• Protein-Interaction-Networks: More than mere modules
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Drug-therapy networks and the predictions of novel drug targets
• Mining Missing Hyperlinks from Human Navigation Traces: A Case Study of Wikipedia
• Link prediction based on path entropy
• Scalable Text and Link Analysis with Mixed-Topic Link Models
• Adapting the Stochastic Block Model to Edge-Weighted Networks
• Estimating topological properties of weighted networks from limited information
• Continuous Hierarchical Representations with Poincaré Variational Auto-Encoders
• Communities in Networks
• Is stochastic thermodynamics the key to understanding the energy costs of computation?
• Matching-centrality decomposition and the forecasting of new links in networks
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Review on Learning and Extracting Graph Features for Link Prediction
• Network structure, metadata and the prediction of missing nodes and annotations
• Detection of node group membership in networks with group overlap
• Predictability of real temporal networks
• Submodular Inference of Diffusion Networks from Multiple Trees
• On the basic computational structure of gene regulatory networks
• A testing based extraction algorithm for identifying significant communities in networks
• A universal data based method for reconstructing complex networks with binary-state dynamics
• Structural preferential attachment: Network organization beyond the link
• Revealing consensus and dissensus between network partitions
• Average distance in a hierarchical scale-free network: an exact solution
• Stochastic block model and exploratory analysis in signed networks
• Identifying communities by influence dynamics in social networks
• Disentangling homophily, community structure and triadic closure in networks
• An Empirical Study of the Relation Between Community Structure and Transitivity
• Hierarchical Graph Clustering using Node Pair Sampling
• Reconstructing networks
• Nested hierarchies in planar graphs
• Credit Default Swaps Drawup Networks: Too Tied To Be Stable?
• Significant communities in large sparse networks
• An improved HeatS+ProbS hybrid recommendation algorithm based on heterogeneous initial resource configurations
• Universality of the stochastic block model
• Super-resolution community detection for layer-aggregated multilayer networks
• Accuracy Test for Link Prediction in terms of Similarity Index: The Case of WS and BA Models
• Hypergraph reconstruction from dynamics
• Prediction of scientific collaborations through multiplex interaction networks
• Hierarchical self-organization of non-cooperating individuals
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks
• Emergence of dynamic properties in network hyper-motifs
• Link prediction in multiplex networks via triadic closure
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• Hierarchical networks of scientific journals
• Link Prediction via Generalized Coupled Tensor Factorisation
• Universal structural estimator and dynamics approximator for complex networks
• Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?
• Extracting tag hierarchies
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Profiling of a network behind an infectious disease outbreak
• The maximum capability of a topological feature in link prediction
• Predicting link directions via a recursive subgraph-based ranking
• Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades
• Occams Razor for Big Data? On Detecting Quality in Large Unstructured Datasets
• Bounded link prediction for very large networks
• Strong associations between microbe phenotypes and their network architecture
• A framework for statistical network modeling
• Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee
• Graph Geometry Interaction Learning
• Assortativity and leadership emergence from anti-preferential attachment in heterogeneous networks
• The Infinite Degree Corrected Stochastic Block Model
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• Multilayer Networks for Text Analysis with Multiple Data Types
• Mining and Forecasting Career Trajectories of Music Artists
• Evolution of the Chinese Guarantee Network under Financial Crisis and Stimulus Program
• Finding missing edges and communities in incomplete networks
• Hyperlink communities in higher-order networks
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• A framework for second order eigenvector centralities and clustering coefficients
• Cycle and flow trusses in directed networks
• Analysis of centrality measures under differential privacy models
• Planar unclustered scale-free graphs as models for technological and biological networks
• Link Prediction via Graph Attention Network
• Multi-attribute community detection in International Trade Network
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Measuring the Hierarchy of Feedforward Networks
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Time evolution of the hierarchical networks between PubMed MeSH terms
• A Stochastic Block Model Approach for the Analysis of Multilevel Networks: an Application to the Sociology of Organizations
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Clustering for epidemics on networks: a geometric approach
• Collaborative Filtering Approach to Link Prediction
• Local degree blocking model for link prediction in complex networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Hyperbolic Graph Attention Network
• Hyperbolic Node Embedding for Signed Networks
• Hierarchical core-periphery structure in networks
• Learning in Hierarchical Social Networks
• A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
• Faster way to agony: Discovering hierarchies in directed graphs
• Inference for graphs and networks: Extending classical tools to modern data
• Structural Analysis of Criminal Network and Predicting Hidden Links using Machine Learning
• Predicting the evolution of complex networks via local information
• Estimating the outcome of spreading processes on networks with incomplete information: a mesoscale approach
• Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Glassy nature of hierarchical organizations
• Growing networks of overlapping communities with internal structure
• Overlapping modularity at the critical point of k-clique percolation
• Node discovery problem for a social network
• Diffusion on hierarchical systems of weakly-coupled networks
• Substance graphs are optimal simple-graph representations of metabolism
• Complex networks as an emerging property of hierarchical preferential attachment
• Resampling effects on significance analysis of network clustering and ranking
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Convexity in complex networks
• Critical Phenomena and Strategy Ordering with Hub Centrality Approach in the Aspiration-based Coordination Game
• Generalized linear models with low rank effects for network data
• Measures of Tipping Points, Robustness, and Path Dependence
• Rewiring hierarchical scale-free networks: Influence on synchronizability and topology
• Matrix Completion with Hierarchical Graph Side Information
• Hierarchical community detection by recursive partitioning
• Generating global network structures by triad types
• Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization
• Finite size analysis of the detectability limit of the stochastic block model
• Predicting Anchor Links between Heterogeneous Social Networks
• Real-Space Renormalization Group for Spectral Properties of Hierarchical Networks
• Gravity Effects on Information Filtering and Network Evolving
• Detecting the optimal number of communities in complex networks
• Reflective visualization and verbalization of unconscious preference
• Semi-supervised network inference using simulated gene expression dynamics
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Knowledge Acquisition by Networks of Interacting Agents in the Presence of Observation Errors
• Inference of Edge Correlations in Multilayer Networks
• Graph link prediction in computer networks using Poisson matrix factorisation
• A novel similarity measure for mining missing links in long-path networks
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• A hierarchy index for networks in the brain reveals a complex entangled organizational structure
• Shadow networks: Discovering hidden nodes with models of information flow
• Performance of Local Information Based Link Prediction: A Sampling Perspective
• Generalized network community detection
• Benchmarking Graph Neural Networks on Link Prediction
• Missing links as a source of seemingly variable constants in complex reaction networks
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• Diffusion-Aware Sampling and Estimation in Information Diffusion Networks
• Reconstructing topological properties of complex networks using the fitness model
• Topological estimation of the latent geometry of a complex network
• Complex networks with scale-free nature and hierarchical modularity
• Network-based confidence scoring system for genome-scale metabolic reconstructions
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Criterions for locally dense subgraphs
• Modeling multi-scale data via a network of networks
• Dynamics of interacting information waves in networks
• Average Distance, Diameter, and Clustering in Social Networks with Homophily
• No Silk Road for Online Gamers!: Using Social Network Analysis to Unveil Black Markets in Online Games
• Comparing the hierarchy of keywords in on-line news portals
• Asymmetry of social interactions and its role in link predictability: the case of coauthorship networks
• Sampling from Diffusion Networks
• The art of community detection
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• Descriptive evaluation of students using fuzzy approximate reasoning
• War pact model of shrinking networks
• A Hyperbolic-to-Hyperbolic Graph Convolutional Network
• Local multiresolution order in community detection
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Nonparametric Bayesian models of hierarchical structure in complex networks
• Greedy routing optimisation in hyperbolic networks
• Cliques in complex networks reveal link formation and community evolution
• "Conjectural" links in complex networks
• Spectral and Dynamic Consequences of Network Specialization
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Detecting Friendship Within Dynamic Online Interaction Networks
• Emergence of leader-follower hierarchy among players in an on-line experiment
• Automatic Discovery of Families of Network Generative Processes
• Semi-supervised Graph Embedding Approach to Dynamic Link Prediction
• The Impact of Imperfect Information on Network Attack
• Clustering in networks with the collapsed Stochastic Block Model
• Multi-Scale Link Prediction
• Active Learning for Hidden Attributes in Networks
• Consistency between ordering and clustering methods for graphs
• Collapsed Variational Bayes Inference of Infinite Relational Model
• Revisiting Non-Progressive Influence Models: Scalable Influence Maximization
• Generating Hierarchically Modular Networks via Link Switching
• Network Diffusions via Neural Mean-Field Dynamics
• Link Prediction via controlling the leading eigenvector
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Stability of similarity measurements for bipartite networks
• DeepHGCN: Toward Deeper Hyperbolic Graph Convolutional Networks
• Fast Hierarchy Construction for Dense Subgraphs
• Constructing Laplacian matrices with Soules vectors: inverse eigenvalue problem and applications
• Adaptive Gaussian Processes on Graphs via Spectral Graph Wavelets
• Dynamic patterns of knowledge flows across technological domains: empirical results and link prediction
• Network analysis with quantum dynamics clarifies why photosystem II exploits both chlorophyll a and b
• Predicting missing links via correlation between nodes
• Exploring Hierarchies in Online Social Networks
• Leveraging Sociological Models for Predictive Analytics
• Node metadata can produce predictability transitions in network inference problems
• Sandpile cascades on interacting tree-like networks
• Node discovery in a networked organization
• Variational Inference For Probabilistic Latent Tensor Factorization with KL Divergence
• Single-trajectory map equation
• Learning common structures in a collection of networks. An application to food webs
• Extracting hierarchical backbones from bipartite networks
• Synthetic graphs for link prediction benchmarking
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Applications of information geometry to spiking neural network behavior
• Stability of Maximum likelihood based clustering methods: exploring the backbone of classifications (Who is keeping you in that community?)
• Analytically solvable processes on networks
• Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
• Intuitive visualization of the intelligence for the run-down of terrorist wire-pullers
• On the Role of Triadic Substructures in Complex Networks
• The Mont Blanc of Twitter: Identifying Hierarchies of Outstanding Peaks in Social Networks
• Generalized chordality, vertex separators and hyperbolicity on graphs
• Community detection and tracking on networks from a data fusion perspective
• On the categorization of scientific citation profiles in computer sciences
• Lorentzian Graph Convolutional Networks
• DINE: A Framework for Deep Incomplete Network Embedding
• A multilevel network approach to revealing patterns of online political selective exposure
• Networks of plants: how to measure similarity in vegetable species
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Reconstructing propagation networks with temporal similarity metrics
• SimBins: An information-theoretic approach to link prediction in real multiplex networks
• Missing Data as Part of the Social Behavior in Real-World Financial Complex Systems
• A decaying factor accounts for contained activity in neuronal networks with no need of hierarchical or modular organization
• Chordality properties and hyperbolicity on graphs
• Multiscale Analysis and Optimisation of Photosynthetic Solar Energy Systems
• HSR: Hyperbolic Social Recommender
• Data reliability in complex directed networks
• Measuring complexity
• Hybrid evolving clique-networks and their communicability
• Simple estimation of hierarchical positions and uncertainty in networks of asymmetric interactions
• Network Growth with Feedback
• Reconstruction of multiplex networks with correlated layers
• Effect of Degree Distribution on Evolutionary Search
• A Method for Geodesic Distance on Subdivision of Trees with Arbitrary Orders and Their Applications
• Fast link prediction for large networks using spectral embedding
• Error Detection in a Large-Scale Lexical Taxonomy
• Comparing the hierarchy of author given tags and repository given tags in a large document archive
• Co-embedding of Nodes and Edges with Graph Neural Networks
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Drug-disease networks and drug repurposing
• Impacts of Data Splitting Strategies on Parameterized Link Prediction Algorithms
• SoK: Practical Aspects of Releasing Differentially Private Graphs
• A Text-based Approach For Link Prediction on Wikipedia Articles
• Tracing Milky Way substructure with an RR Lyrae hierarchical clustering forest
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
• DSSLP: A Distributed Framework for Semi-supervised Link Prediction
• Influence Estimation and Maximization via Neural Mean-Field Dynamics
• Graph Embedding with Hierarchical Attentive Membership
• On Privacy of Socially Contagious Attributes
• Multi-Scale Games: Representing and Solving Games on Networks with Group Structure
• Emergent hierarchy through conductance-based node constraints
• Inset Edges Effect and Average Distance of Trees
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods
• Generalized Eigenvectors of Isospectral Transformations,Spectral Equivalence and Reconstruction of Original Networks
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Hyperlink Regression via Bregman Divergence
• A baseline for content-based blog classification
• Predicting protein-protein interactions based on rotation of proteins in 3D-space
• Robustness of link prediction under network attacks
• Hidden space reconstruction inspires link prediction in complex networks
• A study on the performance of similarity indices and its relationship with link prediction: a two-state random network case
• Hierarchical Hyperlink Prediction for the WWW
• Opinion Divergence Reveals the Hierarchical and Overlapping Community Structure in Networks
• Beyond the network of plants volatile organic compounds
• Extensions and Applications of Equitable Decompositions for Graphs with Symmetries
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• Link prediction for interdisciplinary collaboration via co-authorship network
• On Attractors of Isospectral Compressions of Networks
• Multiplex Structures: Patterns of Complexity in Real-World Networks
• Role of Weak Ties in Link Prediction of Complex Networks
• From Cities to Series: Complex Networks and Deep Learning for Improved Spatial and Temporal Analytics*