Source-linked AI summary
Popularity versus Similarity in Growing Networks
Fragkiskos Papadopoulos, Maksim Kitsak, M. Angeles Serrano, Marian Boguna, Dmitri Krioukov
TL;DR
The paper asks whether attractiveness in growing networks is governed by popularity alone or also by similarity, an issue relevant to explaining and predicting new links. It develops a geometric popularity×similarity optimization framework and maps real networks into that space. The framework accurately describes link probabilities in technological, biological, and social networks, while its validation is limited by the difficulty of directly validating similarity mechanisms and by networks whose links reflect other processes.
Problem
The paper addresses the limited direct validation of network evolution mechanisms and asks whether similarity, alongside popularity, shapes link formation.
Method
The framework maps network nodes to radial popularity and angular similarity coordinates, inferring coordinates by likelihood-based MCMC methods.
Results
Empirical new-old connection probabilities in the Internet, E.coli metabolic network, and PGP web of trust follow the framework’s theoretical predictions, while logarithmic losses are lower than with randomized coordinates.
Takeaways & Limitations
Popularity is an emergent effect of local optimization that also accounts for similarity, providing a framework for predicting new links in evolving networks.
Takeaways & Limitations
Direct validation of modeled similarity mechanisms is difficult because many similarity measures exist and their appropriate choice is often unclear.
Abstract
from arXiv · showhide
Popularity is attractive -- this is the formula underlying preferential attachment, a popular explanation for the emergence of scaling in growing networks. If new connections are made preferentially to more popular nodes, then the resulting distribution of the number of connections that nodes have follows power laws observed in many real networks. Preferential attachment has been directly validated for some real networks, including the Internet. Preferential attachment can also be a consequence of different underlying processes based on node fitness, ranking, optimization, random walks, or duplication. Here we show that popularity is just one dimension of attractiveness. Another dimension is similarity. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which popularity preference emerges from local optimization. As opposed to preferential attachment, the optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.
Methods Summary
The mapping method infers popularity and similarity coordinates for evolving networks, then tests whether observed links follow the framework’s predicted connection probabilities. It is applied to technological, biological, and social networks using likelihood-based coordinate inference and temporal snapshots.
- Mapping method: Radial coordinates encode popularity from node degree, while angular coordinates encode similarity inferred by maximizing the model likelihood.The radial relation uses k_s(t) ∼ e^(r_t−r_s), and angular coordinates are optimized with Metropolis-Hastings.
- Mapping method: The likelihood uses hyperbolic distances and a temperature-dependent connection probability, with parameters determined from network statistics such as average degree and clustering.The model probability is p(x_ij) = 1/[1+e^(x_ij−R)/T].
- Data and networks: The study validates popularity×similarity optimization on Internet, E.coli metabolic, and PGP web-of-trust networks from technology, biology, and society.The datasets include AS Internet snapshots, a bipartite E.coli metabolism representation, and temporal PGP web-of-trust snapshots.
- Mapping method: The method infers coordinates through repeated likelihood updates, accepting higher-likelihood moves and probabilistically accepting lower-likelihood moves.This is the Metropolis-Hastings procedure used to optimize angular coordinates.
- Validation: Figure 3 finds that empirical new-old connection probabilities in all three networks follow the theoretical predictions of popularity×similarity optimization.The result supports the claim that new connections in these networks are established as the framework predicts.
III. DISCUSSION OF THE MAPPING METHOD
The mapping method is evaluated for interpretability, overfitting, and predictive quality. Inferred coordinates align with network-specific attributes, improve logarithmic loss over randomized coordinates, and distinguish networks that fit the model from one that does not.
- Meaningful coordinates: Inferred coordinates correlate with network-specific attributes, including geographic or country-based clustering in Internet and PGP maps and biochemical organization in metabolism.Country-code PGP certificates cluster angularly while generic .net certificates are widespread; metabolites in shared reactions map close together.
- Overfitting: The mapping uses t angular parameters to make O(t^2) pairwise link-probability predictions, reducing concern that its fit is merely overfitting.For subsequent snapshots, Δt inferred parameters make O(tΔt) new-old predictions.
- Logarithmic loss: Logarithmic loss is computed from all predicted pairwise probabilities and is lower for inferred coordinates than for randomized angular coordinates.The metric is the absolute logarithm of the probability that the network is generated by the model given the inferred coordinates.
- Logarithmic loss: New-old logarithmic losses are also significantly smaller with inferred coordinates than with randomized coordinates, supporting predictive descriptions of new connections.This comparison is reported for the Internet, E.coli metabolic network, and PGP web of trust.
C. Example of a network that is not well described by the model
The actor network is poorly described by popularity×similarity optimization because large film crews create connections among many dissimilar and unpopular actors. This mismatch is reflected in the model’s unfavorable likelihood comparison.
- 44,936 actors formed the largest connected 2000 actor-network component, with average degree 13.6.
- The inferred-coordinate model had logarithmic loss L = 6.0×10^6, exceeding the randomized baseline Lrand = 3.8×10^6.
- Large film crews create fully connected subgraphs containing many dissimilar actors, producing an abundance of large cliques.
- Even relatively unpopular actors can connect across countries in these crews, so popularity×similarity optimization does not describe their links well.
A. Degree distribution
The popularity×similarity models reproduce preferential-attachment degree statistics while deriving link attraction from hyperbolic proximity and tunable connection rules. Their degree distributions match PA power laws, including a well-defined γ = 2 case.
- The model connects new nodes to hyperbolically close existing nodes, with Model2 using a distance-dependent probability and radius Rt calibrated to average degree.
- PA’s degree-conditioned attraction probability uses m links, initial attractiveness A = (γ−2)m, and target exponent γ.
- The model’s link-attraction probability and degree distribution match preferential attachment when β = 1/(γ−1), yielding the same power law.
- γ = 2 is well defined in Model1 and corresponds to β = 1, where nodes do not move.
- At T → 0, Model2 becomes Model1 by restricting each new node to its m hyperbolically closest existing nodes.
- Simulations validate the theoretical predictions for Model2 and Model1 across the reported degree-attraction and degree-distribution results.
B. Clustering
Hyperbolic geometry produces strong clustering because proximity is transitive through the triangle inequality. Temperature controls this effect, with clustering decreasing toward zero as temperature approaches one.
- The geometry’s triangle inequality makes mutually close nodes likely to form triangular subgraphs.
- Average clustering decreases with temperature, reaching its maximum at T = 0 and tending to zero as T → 1.
1. Analysis
The clustering analysis decomposes triangles around nodes into those formed when a node appears and those formed later. Its integral expressions show that temperature governs clustering, which is maximal at zero temperature and vanishes as T approaches one.
- 1. Analysis: Node clustering is computed from expected triangle counts divided by expected degree-based normalization, with triangles split into old and new contributions.
- 1. Analysis: The average clustering in optimization networks is 0.83, compared with 0.12 in PA networks.
- 1. Analysis: For Model2, pairwise connection probability is determined by hyperbolic distance through p(xst), with temperature entering the distance kernel.
- 1. Analysis: The triangle calculation fixes one node’s angular coordinate and integrates over the other nodes’ angular separations.
- 1. Analysis: The resulting clustering equations lack a closed form but imply that clustering vanishes as T → 1 and is maximized as T → 0.
- 1. Analysis: At zero temperature, the smallest-degree node has asymptotic clustering near one, although power-law degree constraints prevent clustering from equaling one for every degree.
2. Simulations
Simulations support the model’s predictions about clustering, link-attraction probabilities, and degree distributions, while extensions show how temperature and connection radius control clustering and densification.
- Clustering decreases as temperature T increases and vanishes as T approaches 1; smaller γ produces stronger clustering.
- Model2′ connects each existing node independently, so its number of new links converges to a Poisson distribution with mean m and variance m.
- At T = 0, Model2′ produces maximum possible clustering, while its average number of connections remains m.
- Setting Rt = rt causes network densification, with average degree increasing with network size.
- For δ > 1 and γ →2, average degree grows as k(t) ∼t^(δ−1) ln t, while average shortest-path distance and effective diameter decrease.
V. CONNECTION TO THE FITNESS MODEL
The geometric optimization framework can represent fitness-based competition by letting nodes drift radially at fitness-dependent speeds. Under a suitable mapping, it reproduces the fitness model’s attraction probabilities and degree distributions.
- Fitness affects link attraction through both a node’s current degree and its fixed parameter ηs, drawn from a distribution ρ(η).
- The geometric model incorporates fitness by assigning each node a radial drift speed β(ηs), allowing popularity to change differently over time.
- With β(η) = mη/(AC), the attraction probability in Model3 equals that of the fitness model, yielding the same degree distribution.
- The resulting degree distribution is a weighted sum of power laws, and β(ηs) remains bounded between 0 and 1.
- When all nodes have equal fitness, the model reduces to standard preferential attachment with degree-distribution exponent γ.
VI. EXTENSIONS FOR ANY CURVATURE AND TEMPERATURE
The model extends to arbitrary negative curvature by rescaling radial coordinates and connection probabilities. Temperature T = 1 is a phase transition, and clustering becomes asymptotically zero above it.
- For curvature K = −ζ^2, hyperbolic distance is defined between radial-angular node coordinates using the curvature parameter ζ.
- The arbitrary-curvature extension replaces rt = ln t with rt = 2ζ^−1 ln t and rescales the connection probability’s distance-temperature term.
- At T = 1, the approximation for pairwise connection probability changes because the relevant integral diverges.
- For T > 1, the model can recover the low-temperature attraction probability and degree distribution after changing the initial radial coordinate.
- For any T > 1, clustering is asymptotically zero, including when ζ and T jointly tend to infinity.
VII. CONNECTIONS TO PREFERENTIAL ATTACHMENT, GROWING RANDOM GRAPHS, AND GROWING RANDOM GEOMETRIC GRAPHS
Preferential attachment, growing random graphs, and growing random geometric graphs arise as limiting cases of popularity×similarity optimization, depending on curvature, temperature, and popularity dynamics.
- The framework therefore treats preferential attachment, growing random graphs, and growing random geometric graphs as limiting degenerate cases of one optimization model.
- Standard preferential attachment emerges when curvature tends to minus infinity, eliminating the angular similarity term from hyperbolic distance.
- In this limit, the degree distribution follows a power law with exponent γ = 1 + 1/β, while clustering is zero as T tends to infinity.
- When β tends to 0, all nodes become equally popular and the model degenerates to growing random graphs with exponential degree distributions.
- At β = 0 and low temperatures, similarity still determines connections, producing growing random geometric graphs with finite clustering.
VIII. EXTENSION WITH INTERNAL LINKS
The model is extended to create internal links between existing disconnected nodes, while preserving preferential-attachment-like degree behavior and allowing topology to change in other ways.
- Internal-link model: The extension adds L internal links between existing disconnected node pairs alongside the m external links introduced by each new node.Candidate pairs are selected randomly and connected with probability p(xij) based on hyperbolic distance.
- Internal-link model: Internal-link attraction is analogous to external-link attraction, differing mainly by a prefactor of 2L instead of m.
- Consequences: Internal links do not affect the degree distribution when parameters are matched, but they can alter other topological properties such as average network distance.
- Consequences: Preferential attachment emerges for internal links as well because attraction probability is proportional to current degree.
- Consequences: Lower temperature increases the probability that hyperbolically close disconnected node pairs form internal connections.
IX. PROPERTIES OF REAL-WORLD VERSUS MODELED NETWORKS
The evaluation compares real and modeled networks using local and global structural properties, including degree correlations that distinguish assortative from disassortative organization.
- Evaluation properties: The comparison evaluates degree distribution, degree-dependent clustering, degree-dependent neighbor degree, shortest-path distance distribution, and degree-dependent betweenness.
- Degree correlations: Average neighbor degree reveals degree correlations: increasing values indicate assortativity, whereas decreasing values indicate disassortativity.
- Local and global structure: The first three properties are local one-hop statistics, while distance distribution and betweenness characterize global network structure.
A. Internet
The framework is tested against technological, biological, and social networks by matching their sizes and selected structural parameters, with modeled networks reproducing diverse observed properties.
- A. Internet: The AS Internet benchmark contains 23,748 nodes with γ = 2.1, average degree approximately 5, and average clustering 0.61.
- A. Internet: The E.coli metabolic benchmark contains 1,010 nodes with γ = 2.5, average degree 6.5, and average clustering 0.48.
- A. Internet: The PGP web-of-trust snapshot has 14,367 nodes, average degree 5.3, average clustering 0.47, and a degree distribution deviating from a clean power law.
- A. Internet: For PGP, the model uses inferred fitness-related radial dynamics and angular coordinates because the network has non-power-law degrees and nonuniform angular distances.
- A. Internet: The modeled PGP network matches the real network across degree distribution, clustering, degree correlations, distances, and betweenness.
- A. Internet: Across the three domains, the model captures both disassortative and assortative networks and networks with either clean or non-power-law degree distributions.
X. RELATED WORK
Related work addresses similarity, spatial structure, hidden variables, clustering, and emergent preferential attachment, while this framework combines geometric modeling, analytic treatment, direct validation, and structural reproduction.
- Related models: Prior models augment preferential attachment with document similarity or spatial information, often producing clustering when connection probability declines sufficiently with distance.
- Related models: Hidden-variable models generate links from node attributes and can produce power-law degree distributions through suitable variable and connection-probability choices.
- Clustering mechanisms: Random walks strengthen clustering by concentrating new links within the attachment node’s local neighborhood.
- Problems with PA: Standard preferential attachment lacks clustering and generally requires global degree information, motivating mechanisms in which preferential attachment emerges from local processes.
- Validation: The paper directly validates its evolution mechanism by inferring node coordinates and comparing real linking probabilities as functions of similarity-space distance with model predictions.
- Contribution: The approach combines a simple geometric model, complete analytic treatment, direct validation across different domains, reproduction of structural properties, and emergent preferential attachment.