Source-linked AI summary
Random hypergraphs and their applications
Gourab Ghoshal, Vinko Zlatic, Guido Caldarelli, M. E. J. Newman
TL;DR
Emerging folksonomies need models that preserve links among users, resources, and tags, which simpler graph representations do not fully capture. The paper develops a random tripartite-hypergraph model with analytic predictions and tests it on Flickr. Agreement is mixed, but improves substantially after removing multiple-tagging structures, suggesting those structures are the primary nonrandom behavior detected.
Problem
Folksonomies contain three-way user–resource–tag relationships that existing unipartite, bipartite, and limited tripartite representations fail to capture fully.
Method
The paper represents folksonomies as tripartite hypergraphs, develops a random model with analytic predictions, and compares those predictions with Flickr data.
Results
Agreement with Flickr observations is good in some cases and poorer in others, but becomes significantly better after multiple-tagging instances are removed.
Takeaways & Limitations
The disagreement is primarily associated with multiple tagging, while the remaining Flickr network is suggested to be close to a random graph in other respects.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Folksonomies require a network representation that preserves the three-way relation among resources, tags, and users. The paper models these structures as tripartite hypergraphs, develops analytic predictions, and compares them with Flickr data.
- Motivation: Folksonomies are collaborative annotations in which users apply tags to resources such as photographs.Flickr exemplifies this structure, with users describing photos using short tags.
- Motivation: Existing unipartite, bipartite, and limited tripartite representations omit structural elements and constrain subsequent network analysis.
- Representation: Each folksonomy hyperedge joins exactly one resource, one tag, and one user, representing a user applying a tag to a resource.
- Approach: The paper studies tripartite graph properties, develops a random graph model with analytic predictions, and tests those predictions against Flickr.
- Findings: The model agrees well with Flickr observations in some cases but not all.
II. TRIPARTITE GRAPHS
Tripartite graphs contain three vertex types joined by three-way hyperedges, and they support multiple degree and projection definitions. These alternatives retain or selectively discard relationships among vertex types.
- Structure: Tripartite networks contain red, green, and blue vertices connected by three-way hyperedges, each joining one vertex of every type.For folksonomies, these types correspond to resources, tags, and users.
- Degree: Hypergraph degree is defined as the number of hyperedges attached to a vertex, while the three mean degrees are linked by their shared hyperedge count.
- Degree: The network has separate degree distributions p_r(k), p_g(k), and p_b(k) for the three vertex types.
- Projections: Projections can preserve a red–green or other two-color relation by retaining pairs joined by an original hyperedge.Such projections can represent photos and their tags while dropping which users applied the tags.
- Projections: Red-vertex projections can connect vertices sharing a green neighbor, a blue neighbor, or either kind of neighbor.
III. RANDOM TRIPARTITE GRAPHS
The paper develops random tripartite hypergraphs with prescribed degree distributions as analytically tractable models of real tripartite networks.
- Random tripartite graphs: The model specifies degree distributions for random tripartite hypergraphs and uses them to derive analytic network properties.
A. The model
The configuration-style model assigns vertex degrees, matches equal stub totals across colors, and randomly groups one stub of each color into every hyperedge. Its sparse limit is locally tree-like, enabling analytic treatment.
- A. The model: Each vertex receives a degree represented by stubs, with equal total stubs for red, green, and blue vertices and total hyperedge count m.
- A. The model: The model creates m hyperedges by uniformly choosing one red, one green, and one blue stub for each hyperedge.
- A. The model: A specific red/green/blue trio with degrees k_i, k_j, and k_k has hyperedge probability k_i k_j k_k / m^2.
- A. The model: A specified red/green pair has hyperedge probability k_i k_j / m, and in sparse graphs these probabilities vanish as 1/m.
- A. The model: Because small-loop probabilities vanish with network size, the model is locally tree-like.This property is important for the subsequent analysis.
- A. The model: The model can sample degree distributions for each color, subject to the constraint that the three stub totals agree.A redraw procedure can enforce the constraint when generating example networks.
- A. The model: Following a random hyperedge reaches vertices according to degree-weighted distributions rather than the ordinary vertex degree distributions.The corresponding excess degree is one less than total degree.
B. Generating functions
Probability generating functions are introduced for the tripartite random graph’s degree and excess-degree distributions, providing tools for calculating their moments and related properties.
- The model uses probability generating functions as its fundamental tools for calculating properties of the random tripartite graph.
- Generating functions are defined for the degree distributions of the three vertex colors.
- The means of the degree distributions can be calculated directly from the generating functions.
- Higher moments are also straightforward to obtain from these generating functions.
- Corresponding generating functions are defined for the excess-degree distributions.
C. Projections
The paper derives generating-function descriptions for several projections of the tripartite graph, including projections based on shared neighbors of one or more colors.
- The red-only projection joins red vertices that share a green neighbor, with its degree distribution derived from red and green degree distributions.
- The paper also derives the degree distribution and generating function for a red projection in which vertices share either a green or blue neighbor.
- The resulting generating-function expression permits calculation of the average degree in the projected network.
- The projection results are later used to compare random-graph predictions with real-world networks.
D. Formation and size of the giant component
The paper characterizes giant-component formation and size in the tripartite model using connectivity probabilities, yielding an explicit threshold condition and vertex-count formulas.
- Formation and size of the giant component: In sufficiently sparse networks, vertices remain in small components; above a connectivity threshold, a fraction joins one giant component.
- Formation and size of the giant component: A component is a set of vertices connected through hyperedge paths so every vertex is reachable from every other.
- Formation and size of the giant component: The probabilities u_r, u_g, and u_b describe whether a randomly chosen hyperedge fails to connect to the giant component through each vertex color.
- Formation and size of the giant component: The giant-component probability for a randomly chosen hyperedge is 1 − u_r u_g u_b.
- Formation and size of the giant component: S_r is the fraction of red vertices in the giant component, whose total size across colors is n_rS_r + n_gS_g + n_bS_b.
- Formation and size of the giant component: The probabilities u_r, u_g, and u_b are generally obtained numerically by iterative solution rather than in closed form.
- Formation and size of the giant component: A giant component exists if and only if all three probabilities u_r, u_g, and u_b are less than 1.
- Formation and size of the giant component: The phase transition occurs when 2r g b + r g + g b + b r crosses 1, with a giant component when it exceeds 1.
E. Other types of components
The paper considers components formed when traversal is restricted to two vertex colors, deriving a distinct threshold and showing that different color-pair projections can undergo transitions separately.
- Other types of components: Privacy constraints can prevent traversal through user connections, restricting surfing to a two-color network such as photos and tags.
- Other types of components: For a two-color network, the transition is obtained by solving the corresponding connectivity equations and linearizing around u_r = u_g = 1.
- Other types of components: A giant component exists in the red-green network if and only if r g > 1.
- Other types of components: Because the two-color criterion is not symmetric across color permutations, giant components for different color pairs can appear at different transitions.
F. Percolation
The paper extends percolation analysis to tripartite networks by modeling vertex removal and deriving conditions for a giant component. The framework also accommodates more complicated removal schemes.
- Percolation asks whether the remaining tripartite network possesses a giant component after vertices are removed.The framework describes vertex occupation and nonoccupation through probabilities associated with the three vertex types.
- More complicated schemes, including removal of multiple vertex types or nonuniform removal, can be studied with similar methods.The paper explicitly identifies different removal probabilities and nonuniform removal as extensions of the framework.
- With red-vertex occupation fraction φ, the paper defines u_r as the probability that a red vertex reached by a random hyperedge is outside the giant cluster.The red vertex can fail to belong to the giant cluster through two distinct mechanisms, developed in the surrounding derivation.
- The probabilities u_g and u_b follow coupled generating-function relations, and S_r, S_g, and S_b give the fractions of each vertex type in the giant percolation cluster.The reported expressions are u_g = g_1(u_bu_r), u_b = b_1(u_ru_g), with component fractions defined in Eqs. (29a)–(29c).
- The percolation transition occurs at φ = φ_c, where φ_c satisfies 2φrgb + φrg + gb + φbr = 1.The threshold is obtained by perturbing around u_r = u_g = u_b = 1, corresponding to no giant cluster.
G. Simulations
The authors validate analytic predictions for random tripartite networks against computer simulations. The predicted projected degree distribution and giant-cluster behavior agree excellently with direct measurements.
- The simulations first compare analytic calculations with computer-generated random tripartite graphs before real-world network analysis.This establishes a simulation check for the random-graph calculations.
- For Poisson degree distributions, generating functions are used to derive the degree distribution of a projection onto red vertices.Two red vertices are connected in the projection when they share either a green or a blue neighbor.
- The projected degree distribution is obtained by expanding its generating function in powers of z, with ρ_gb(k) denoting the probability of exactly k projected neighbors.The derivation also uses Stirling numbers of the second kind to count partitions into nonempty sets.
- Excellent agreement is observed between the analytic projected degree distribution and simulations for c_r = 3, c_g = 10, c_b = 6.The simulated networks use n_r = 100 000, n_g = 30 000, and n_b = 50 000, with the same degree distributions.
- Excellent agreement is also found for the giant-cluster size under red-vertex percolation across occupation probability φ.The comparison uses numerical solutions of Eqs. (28)–(29) and direct measurements on simulated networks.
IV. COMPARISON WITH REAL-WORLD DATA
The tripartite random graph model is compared with Flickr projections and degree distributions. Agreement improves substantially after pruning multiple-tagging patterns, indicating that these loops account for much of the model–data discrepancy.
- Flickr data: The Flickr dataset contains 266 198 photos from 2007, with highly right-skewed degree distributions across photos, tags, and users.The distributions have many low-degree vertices and a small number of very high-degree vertices, without power-law forms as described in the omitted continuation.
- Analytic predictions: The model’s projected degree-distribution calculations use generating functions and numerical contour integration to obtain coefficients.Cauchy’s integral formula avoids noise problems from direct numerical differentiation, and the unit circle works well as the integration contour.
- Raw-data comparison: On raw Flickr data, model and observed photo-projection distributions have the same general shape but only moderately good agreement.The model agrees qualitatively but not quantitatively with the raw network, indicating effects not captured by simple random hyperedges.
- Effect of multiple tagging: Pruning multiple tagging makes agreement quite good for photo projections and significantly better for user projections.The pruning removes trivial short loops created when users apply many tags to photos or the same tags to photo sets, and model predictions are recalculated after pruning.
- Interpretation: The results identify multiple tagging as the primary nonrandom behavior, while supporting a near-random structure in other respects.The model therefore serves as a null model for detecting when observed network structure departs from random expectations.
V. CONCLUSIONS
The paper proposes and analyzes random tripartite hypergraphs, deriving projected-network properties and testing them against simulated and Flickr data. Flickr agreement improves significantly after removing multiple-tagging instances, suggesting these structures account for most observed disagreement.
- The paper proposes a random tripartite hypergraph model and calculates degree distributions, projections, and statistical properties in the large-network limit.
- Flickr comparisons show moderately good agreement in some projected degree distributions and poorer agreement in others.
- Agreement becomes significantly better after removing multiple-tagging instances, suggesting disagreement primarily reflects relatively trivial structures rather than subtle or large-scale social effects.