PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Mapping by Replaying Hyperbolic Growth

Fragkiskos Papadopoulos, Constantinos Psomas, Dmitri Krioukov

arXiv:1205.4384v3cs.SIcond-mat.stat-mechcs.NIphysics.soc-ph

TL;DR

The paper addresses the lack of a simple, reliable, and fast method for inferring latent geometric coordinates in real networks. It introduces HyperMap, which replays hyperbolic growth and estimates coordinates by maximizing model likelihood; on the AS Internet, the resulting map identifies geographic soft communities, predicts missing links with high precision, and supports highly successful low-stretch greedy routing.

  • Problem

    Real networks need a simple, reliable, and fast method to infer latent geometric coordinates for practical uses such as community detection, link prediction, and navigation.

  • Method

    HyperMap maps a network to hyperbolic space by replaying its geometric growth and maximizing the E-PSO likelihood for node coordinates.

  • Results

    On the AS Internet, HyperMap identifies geographic soft communities, predicts missing links with high precision, and yields greedy routing with more than 90% success probability and low stretch.

  • Takeaways & Limitations

    The resulting Internet map is meaningful, predictive for missing links, and highly navigable within the paper’s evaluated setting.

  • Takeaways & Limitations

    Inference of the angular coordinates of the first few nodes is not exact, leaving improvement of early-node estimation as an open question.

Abstract

from arXiv · show

Recent years have shown a promising progress in understanding geometric underpinnings behind the structure, function, and dynamics of many complex networks in nature and society. However these promises cannot be readily fulfilled and lead to important practical applications, without a simple, reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network. Here we present HyperMap, a simple method to map a given real network to its hyperbolic space. The method utilizes a recent geometric theory of complex networks modeled as random geometric graphs in hyperbolic spaces. The method replays the network's geometric growth, estimating at each time step the hyperbolic coordinates of new nodes in a growing network by maximizing the likelihood of the network snapshot in the model. We apply HyperMap to the AS Internet, and find that: 1) the method produces meaningful results, identifying soft communities of ASs belonging to the same geographic region; 2) the method has a remarkable predictive power: using the resulting map, we can predict missing links in the Internet with high precision, outperforming popular existing methods; and 3) the resulting map is highly navigable, meaning that a vast majority of greedy geometric routing paths are successful and low-stretch. Even though the method is not without limitations, and is open for improvement, it occupies a unique attractive position in the space of trade-offs between simplicity, accuracy, and computational complexity.

I. INTRODUCTION

The paper asks whether a real network can be embedded in hyperbolic space by reversing the PSO model’s synthesis and whether the resulting map supports practical applications. It introduces HyperMap, which replays geometric growth and estimates node coordinates by likelihood maximization.

  • I. INTRODUCTION: The paper evaluates whether the inferred geometry yields meaningful soft communities, accurate missing-link prediction, and navigable routing.These applications motivate reversing the synthetic-network construction process.
  • I. INTRODUCTION: HyperMap reverses the PSO model by replaying a network’s geometric growth and estimating node coordinates at successive appearance times.The method maps a given network into hyperbolic space using maximum-likelihood estimation under a growing-network model.
  • I. INTRODUCTION: The PSO model represents popularity through radial coordinates and similarity through angular distance, combining both in hyperbolic distance.Smaller radial coordinates indicate greater popularity, while smaller angular distances indicate greater similarity and higher connection likelihood.
  • I. INTRODUCTION: The generalized PSO model extends basic growth by allowing internal links between existing nodes, with average degree determined by both external and internal link rates.The external rate is m, while L specifies the rate of internal links.

III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.

The E-PSO model modifies PSO so that new nodes use time-dependent expected connection counts while retaining a power-law degree structure. Its simulated networks closely match multiple structural and dynamical properties of the AS Internet.

  • III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.: E-PSO assigns time-dependent expected external connections rather than forcing every new node to connect to the same average number m.When L = 0, E-PSO degenerates to the basic PSO model.
  • III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.: The AS Internet dataset contains 25,910 AS nodes, degree exponent γ = 2.1, average degree approximately 5, and average clustering 0.61.The simulated E-PSO network is grown to the same size and matched parameter settings.
  • III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.: E-PSO accurately matches the AS Internet across degree distribution, clustering, neighbor degree, path lengths, and betweenness using external links only.The comparison covers five local and global network properties, whereas the generalized PSO model uses both external and internal links for the same matching task.
  • III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.: The model’s average-degree and birth-time relationships are validated against the twelve-year evolution of the AS Internet.The validation uses observed AS appearance times and degrees over the measurement period.
  • III. E-PSO: GROWING NETWORKS USING EXTERNAL LINKS ONLY.: Because E-PSO produces synthetic networks resembling the AS Internet, the paper next reverses this synthesis to embed the real topology in hyperbolic space.This motivates applying HyperMap to the observed network.

IV. HYPERMAP: NETWORK MAPPING BY REPLAYING HYPERBOLIC GROWTH

HyperMap maps a network into hyperbolic space by estimating radial and angular coordinates through maximum-likelihood inference under the E-PSO model.

  • IV. HYPERMAP: NETWORK MAPPING BY REPLAYING HYPERBOLIC GROWTH: HyperMap computes radial and angular coordinates for every node by maximizing the likelihood that the observed adjacency matrix was generated by E-PSO.The method’s mapping quality depends on how well E-PSO describes the given network.
  • IV. HYPERMAP: NETWORK MAPPING BY REPLAYING HYPERBOLIC GROWTH: The method treats node numbering in its mapping procedure as unrelated to the network’s order of appearance.The section distinguishes arbitrary node labels from inferred appearance times used in the replay.
  • IV. HYPERMAP: NETWORK MAPPING BY REPLAYING HYPERBOLIC GROWTH: HyperMap’s output is a set of radial and angular coordinates for all nodes in the input network.The input is represented by a symmetric adjacency matrix indicating whether node pairs are linked.

A. Definitions and Likelihood

The likelihood framework defines node-coordinate distributions and connection probabilities in E-PSO, then formulates the probability of coordinates given the observed network and model parameters.

  • A. Definitions and Likelihood: E-PSO assigns angular coordinates uniformly and derives a radial-coordinate density at network size t.The joint coordinate probability follows from the independence of node coordinates.
  • A. Definitions and Likelihood: The framework distinguishes global connection probability over node pairs at a given final distance from local probability for a specific pair at its earlier appearance time.The local probability uses the pair’s hyperbolic distance when the younger node appears.
  • A. Definitions and Likelihood: The likelihood L1 is defined as the probability of a particular set of node coordinates given the adjacency matrix and E-PSO parameters.The formulation uses Bayes’ rule to rewrite this conditional likelihood.

3) Global likelihood

The method formulates network embedding through global and local likelihoods, then avoids direct angular maximization by replaying growth and maximizing each new node’s local likelihood.

  • HyperMap seeks coordinates that maximize the network likelihood under the E-PSO model, equivalently maximizing its logarithm.
  • The global likelihood factors over independent edges and non-edges, with probabilities determined by hyperbolic distances between node pairs.
  • Direct angular maximization is analytically unavailable, while generic numerical methods lack reasonable performance guarantees and can have exponential worst-case running times.
  • HyperMap instead estimates node appearance order and radial coordinates, then replays growth while choosing each new node’s angle by maximizing its local likelihood.
  • Maximizing local likelihood at each time is equivalent to maximizing the final global likelihood, while providing a guaranteed running time.

C. MLE of node appearance times

The appearance-time MLE is derived from the relationship between actual and expected degree, yielding a degree-based ordering that supplies the sequence for HyperMap’s growth replay.

  • The likelihood condition compares each node’s actual degree k_i with its expected degree under the model.
  • Using a mean-field approximation removes angular dependence from expected degree and enables an analytic estimate of node appearance times.
  • For γ > 1, higher-degree nodes receive earlier maximum-likelihood appearance times.
  • HyperMap therefore sorts nodes by decreasing degree and assigns appearance times in that order, breaking ties arbitrarily.
  • These estimated appearance times determine initial radial coordinates before the method computes angular coordinates during growth replay.
  • The algorithm takes the adjacency matrix and model parameters as input and computes radial and angular coordinates for every node.

2. Since, to compute Li

The angular-coordinate search is computationally tractable but approximate, and practical accuracy depends on parameter choices and selectively applied correction steps.

  • O(t^3) running time maps a network of t nodes because each angular maximization evaluates connection probabilities against existing nodes.
  • Mean-field degree estimation and discrete angular sampling make HyperMap an approximate maximum-likelihood algorithm.
  • For the AS Internet, the reported parameters include m ≈ 1.5, L ≈ 1, γ = 2.1, and T ≈ 0.8; the algorithm is deterministic when the first node’s angle is fixed.
  • Correction steps update existing angular coordinates and can improve accuracy, but are most beneficial early and may not justify their cost after a few hundred nodes.
  • Mapping quality is assessed by comparing empirical and theoretical connection probabilities and by logarithmic loss relative to random angular coordinates.
  • In synthetic networks, inferred-coordinate logarithmic loss is substantially below random-coordinate loss and close to the loss from real coordinates.

C. Insensitivity to Input Temperature

HyperMap is largely insensitive to input temperature values at or below the network’s true temperature, while AS Internet validation shows strong geometric agreement and predictive power.

  • C. Insensitivity to Input Temperature: The inferred connection probability is virtually unchanged for input temperatures T ≤ T_real in synthetic networks.Networks generated with T_real = 0.5 were remapped using T values from 0.1 to 0.9.
  • C. Insensitivity to Input Temperature: For the AS Internet, the temperature-inference procedure yields T ≈ 0.8.The value is obtained by matching inferred and theoretical connection probabilities after convergence.
  • VI. APPLYING HYPERMAP TO THE AS INTERNET: The AS Internet’s inferred connection probability closely matches the theoretical prediction, with rLL = e^250000.The reported logarithmic losses are LL_inf = 24 × 10^4 and LL_rand = 49 × 10^4.
  • VI. APPLYING HYPERMAP TO THE AS INTERNET: HyperMap places ASs from the same country in soft angular communities despite using no geographic information.The mapping attributes this pattern to denser within-country connectivity and attraction among connected nodes.
  • VI. APPLYING HYPERMAP TO THE AS INTERNET: Average geographic distance tends to increase with angular distance below 60° and with hyperbolic distance.At large angular distances, geographic and angular distance show no correlation.
  • B. Performance of HyperMap: With 10%, 20%, and 30% of links missing, HyperMap achieves AUC values of 0.963, 0.962, and 0.955, respectively.These values exceed the corresponding geographic-distance baselines of 0.758, 0.751, and 0.741.

C. Comparison to Classical Link-Prediction Techniques

HyperMap outperforms classical link-prediction methods especially on difficult missing links, where observable-topology heuristics lose their advantage. Its performance reflects inferred latent angular similarity rather than only directly observed network structure.

  • C. Comparison to Classical Link-Prediction Techniques: AUC = 0.87 for node pairs with no common neighbors, versus CN’s AUC = 0.5, showing HyperMap’s advantage on hard-to-predict links.Across all pairs, CN reaches AUC = 0.95 and HyperMap AUC = 0.96, but 82% of pairs have no common neighbors.
  • C. Comparison to Classical Link-Prediction Techniques: AUC = 0.86 for pairs whose nodes both have degree less than 6, versus DP’s AUC = 0.59.These low-degree pairs comprise 42% of node pairs.
  • C. Comparison to Classical Link-Prediction Techniques: Classical methods use observable topology-based similarity, whereas HyperMap infers hidden spatial distances between all nodes under a latent-space model.This provides a model-based explanation for why HyperMap is more accurate on difficult disconnected pairs.
  • VIII. APPLICATION TO NETWORK NAVIGATION: Greedy routing uses node coordinates and neighbor addresses to forward packets toward their destinations, dropping them at local minima or when routing backtracks.The evaluation uses hyperbolic coordinates inferred by HyperMap for synthetic networks and the AS Internet.

IX. DISCUSSION AND CONCLUSION

The discussion positions HyperMap as a simple, noninteractive alternative for embedding growing networks, while identifying accuracy–runtime trade-offs in likelihood maximization. Early-node angles and sampled likelihood landscapes remain open improvement targets, although the method is accurate overall and may extend beyond the AS Internet.

  • IX. DISCUSSION AND CONCLUSION: The first few nodes can have poorly determined angular coordinates because they are highly interconnected, but this affects only a small initial set.The condition holds for the first 33 nodes in one synthetic setting, 21 in another, and 38 in the AS Internet.
  • IX. DISCUSSION AND CONCLUSION: Correction steps can improve early-node estimates, but they do not guarantee exact angular inference.The method becomes extremely precise as inference time increases, whereas early-time inference is not exact.
  • IX. DISCUSSION AND CONCLUSION: Sampling may miss the true global likelihood maximum, because HyperMap estimates each new node’s angle from sampled likelihood values.The authors identify the maximization procedure as another aspect open for improvement.
  • IX. DISCUSSION AND CONCLUSION: Finer angular sampling can improve accuracy but increases runtime, creating an open trade-off between computational complexity and embedding accuracy.More sophisticated global-maximum methods may improve performance, but the most efficient option remains unresolved.
  • IX. DISCUSSION AND CONCLUSION: HyperMap avoids Metropolis-Hastings, guiding heuristics, and manual intervention by replaying the hyperbolic growth of a model for growing networks.The authors contrast this with an earlier static-network embedding procedure that required localized MCMC and manually selected degree thresholds.
  • IX. DISCUSSION AND CONCLUSION: HyperMap is presented as potentially applicable to other real networks and to predicting future links in evolving networks, beyond the AS Internet case studied here.The paper frames these extensions as possibilities rather than demonstrated results.

APPENDIX

The appendix derives expected degrees, radial-coordinate densities, and global connection probabilities for the E-PSO model, with approximations stated for large networks. It shows that the model retains power-law degree distributions and gives conditions under which the connection-probability approximation is most accurate.

  • The appendix derives expressions for expected node degree, radial-coordinate density, and global connection probability in a network grown to t nodes.
  • The E-PSO model retains a power-law degree distribution P(k) ∝ k^-γ with γ = 1 + 1/β ≥ 2.
  • The derivations rely on large-t or large-index approximations, including treating radial coordinates as continuous and approximating I_i by I_t.
  • The radial-coordinate density is obtained by differentiating the cumulative fraction of nodes with radial coordinate at most r, using r_i(t) = βr_i + (1 − β)r_t.
  • The connection analysis relates node distances at the current time to their distances when the younger node appeared, then removes the age condition to obtain a global probability.
  • The Taylor-series approximation for the global connection probability is most accurate when γ ≤ 3, a condition stated to hold in the AS Internet.
Loading 1205.4384v3…