Random hypergraphs and their applications

Abstract

In the last few years we have witnessed the emergence, primarily in on-line communities, of new types of social networks that require for their representation more complex graph structures than have been employed in the past. One example is the folksonomy, a tripartite structure of users, resources, and tags -- labels collaboratively applied by the users to the resources in order to impart meaningful structure on an otherwise undifferentiated database. Here we propose a mathematical model of such tripartite structures which represents them as random hypergraphs. We show that it is possible to calculate many properties of this model exactly in the limit of large network size and we compare the results against observations of a real folksonomy, that of the on-line photography web site Flickr. We show that in some cases the model matches the properties of the observed network well, while in others there are significant differences, which we find to be attributable to the practice of multiple tagging, i.e., the application by a single user of many tags to one resource, or one tag to many resources.

11 pages, 7 figures

References in corpus (6)

• The structure and function of complex networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Exact solution of site and bond percolation on small-world networks
• Finite size scaling for the core of large random hypergraphs
• Fundamental statistical features and self-similar properties of tagged networks

Cited by in corpus (87)

• Multilayer Networks
• The structure and dynamics of multilayer networks
• Networks beyond pairwise interactions: structure and dynamics
• The Kuramoto model in complex networks
• Recommender Systems
• Simplicial models of social contagion
• What are higher-order networks?
• Percolation on complex networks: Theory and application
• Random walks on hypergraphs
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Multiorder Laplacian for synchronization in higher-order networks
• Emergent Hyperbolic Network Geometry
• Tag-Aware Recommender Systems: A State-of-the-art Survey
• Simplicial complexes and complex systems
• Network geometry with flavor: from complexity to quantum geometry
• Higher-order percolation processes on multiplex hypergraphs
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Simplicial SIS model in scale-free uniform hypergraph
• Hypergraph topological quantities for tagged social networks
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Hypergraph model of social tagging networks
• Weighted Growing Simplicial Complexes
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Intralayer and interlayer synchronization in multiplex network with higher-order interactions
• Covering Problems and Core Percolations on Hypergraphs
• Topological Percolation on Hyperbolic Simplicial Complexes
• Network Geometry and Complexity
• A Survey of Hybrid Human-Artificial Intelligence for Social Computing
• Betweenness centrality of teams in social networks
• Modelling Non-Linear Consensus Dynamics on Hypergraphs
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• The Aging Effect in Evolving Scientific Citation Networks
• Latent geometry of bipartite networks
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• A class of models for random hypergraphs
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• General and exact approach to percolation on random graphs
• Bond percolation on a class of correlated and clustered random graphs
• Hierarchical networks of scientific journals
• Brand effect versus competitiveness in hypernetworks
• Extracting tag hierarchies
• Edge-based analysis of networks: Curvatures of graphs and hypergraphs
• Phase Transition of Random Non-Uniform Hypergraphs
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Multiplex measures for higher-order networks
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
• Self-organization in social tagging systems
• Atomic subgraphs and the statistical mechanics of networks
• Testing Community Structures for Hypergraphs
• Complex hypergraphs
• Random Recursive Hypergraphs
• Extraction of Temporal Networks from Term Co-occurrences in Online Textual Sources
• Entropy-based models to randomize real-world hypergraphs
• Predicting Multi-actor collaborations using Hypergraphs
• Structure of international trade hypergraphs
• Weighted projected networks: mapping hypergraphs to networks
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Comparing the hierarchy of keywords in on-line news portals
• Modeling temporal hypergraphs
• Ontologies and tag-statistics
• Mathematics of Digital Hyperspace
• Prevalence of multistability and nonstationarity in driven chemical networks
• Impact of directionality on the emergence of Turing patterns on m-directed higher-order structures
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Eigenvector localization in hypergraphs: pair-wise vs higher-order links
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Realizing interdependent couplings as thermal or higher-order interactions
• A Generative Hypergraph Model for Double Heterogeneity
• The distribution of the number of node neighbors in random hypergraphs
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Temporal networks with node-specific memory: unbiased inference of transition probabilities, relaxation times and structural breaks
• Random Preferential Attachment Hypergraphs
• Clustering of tag-induced sub-graphs in complex networks
• Skewness of local logarithmic exports
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Phase transition in a power-law uniform hypergraph
• Convergence law for hyper-graphs with prescribed degree sequences
• Limit theorems for dependent combinatorial data, with applications in statistical inference
• Synchronization of an evolving complex hyper-network
• Effective Personalized Recommendation in Collaborative Tagging Systems
• Efficient inference of rankings from multi-body comparisons
• Edge corona product as an approach to modeling complex simplical networks
• Competing spreading dynamics in simplicial complex
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Computing Eigenvalues of Large Scale Sparse Tensors Arising from a Hypergraph
• High-order joint embedding for multi-level link prediction