- O. Evnin and D. Krioukov,
Ensemble Inequivalence and Phase Transitions in Unlabeled Networks,
arXiv,
One-sentence abstract: The unlabeled Erdős–Rényi graphs with bounded average degree do not exist in the thermodynamic limit.
- H. Stepanyants, A. Beardon, J. Paton, and D. Krioukov,
Computing Distances on Riemann Surfaces,
Journal of Physics A: Mathematical and Theoretical, v.57, n.34, p.345201, 2024
(DOI, arXiv),
One-sentence abstract: The first-ever computable formula and algorithm to find the distance between a pair of points on compact Riemann surfaces.
- M. Boguna and D. Krioukov,
Measuring Spatial Distances in Causal Sets via Causal Overlaps,
Physical Review D, v.110, 024008, 2024
(DOI,
arXiv),
One-sentence abstract: A method to measure spacelike distances in causal sets all the way down to the Planck scale.
- H. Stepanyants, A. Beardon, J. Paton, and D. Krioukov,
Diameter of Compact Riemann Surfaces,
Computational Methods and Function Theory, 2024
(DOI, arXiv),
One-sentence abstract: The first-ever exact result for the diameter of a compact hyperbolic manifold.
- G. Budel, M. Kitsak, R. Aldecoa, K. Zuev, and D. Krioukov,
Random Hyperbolic Graphs in d+1 Dimensions,
Physical Review E, v.109, 054131, 2024
(DOI,
arXiv),
One-sentence abstract: A generalization of the random hyperbolic graph model to any dimension.
- I.A. Kasyanov, P. van der Hoorn, D. Krioukov, and M.V. Tamm,
Nearest-Neighbor Directed Random Hyperbolic Graphs,
Physical Review E, v.108, 054310, 2023
(DOI,
arXiv),
One-sentence abstract: A directed version of random hyperbolic graphs.
- P. van der Hoorn, G. Lippner, C. Trugenberger, and D. Krioukov,
Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of their Riemannian Manifolds,
Discrete & Computational Geometry, v.70(3), p.671-712, 2023
(DOI, arXiv),
One-sentence abstract: The proofs of the results announced here.
- J. Paton, H. Hartle, H. Stepanyants, P. van der Hoorn, and D. Krioukov,
Entropy of Labeled versus Unlabeled Networks,
Physical Review E, v.106, 054308, 2022
(DOI,
arXiv),
One-sentence abstract: In sparse labeled networks, the noise of meaningless labeling can overpower the network-structural signal, as demonstrated by the comparison of the entropies of labeled and unlabeled random geometric graphs.
- O. Bobrowski and D. Krioukov,
Random Simplicial Complexes: Models and Phenomena
(DOI, arXiv),
In Higher-Order Systems (F. Battiston and G. Petri (edt.)),
Springer International Publishing, Cham, Switzerland, 2022
(DOI, Amazon),
One-sentence abstract: A review of canonical models of random simplicial complexes and their most exciting features.
- H. Hartle, F. Papadopoulos, and D. Krioukov,
Dynamic Hidden-Variable Network Models,
Physical Review E, v.103, 052307, 2021
(DOI,
arXiv),
One-sentence abstract: A generalization of network models with hidden variables to dynamic hidden variables and dynamic links.
- P. van der Hoorn, W. Cunningham, G. Lippner, C. Trugenberger, and D. Krioukov,
Ollivier-Ricci Curvature Convergence in Random Geometric Graphs,
Physical Review Research, v.3, 013211, 2021
(DOI,
arXiv,
software),
One-sentence abstract: Ollivier curvature of random geometric graphs in any Riemannian manifold converges to Ricci curvature of the manifold in the continuum limit.
- M. Boguna, I. Bonamassa, M. De Domenico, S. Havlin, D. Krioukov, M. Angeles Serrano,
Network Geometry,
Nature Reviews Physics, v.3, 114-135, 2021
(DOI,
arXiv),
One-sentence abstract: Network geometry review.
- I. Voitalov, P. van der Hoorn, M. Kitsak, F. Papadopoulos, and D. Krioukov,
Weighted Hypersoft Configuration Model,
Physical Review Research, v.2, 043157, 2020
(DOI,
arXiv,
software),
One-sentence abstract: The maximum entropy model of weighted networks with a given joint distribution of degrees and strengths.
- D. Krioukov and I. Voitalov,
Geohyperbolic Routing and Addressing Schemes for Networks,
USPTO Patent No. US 10,812,365 B2, 2020
(USPTO),
One-sentence abstract: Patent on super-scalable routing in telecommunication networks.
- M. Kitsak, I. Voitalov, and D. Krioukov,
Link Prediction with Hyperbolic Geometry,
Physical Review Research, v.2, 043113, 2020
(DOI,
arXiv,
software),
One-sentence abstract: The harder a link to predict, the better off the hyperbolic geometry is at predicting it.
- F. Radicchi, D. Krioukov, H. Hartle, and G. Bianconi,
Classical Information Theory of Networks,
Journal of Physics: Complexity, v.1, 025001, 2020
(DOI,
arXiv),
One-sentence abstract: Heterogeneity emerges from the maximum entropy principle.
- M. Boguna, D. Krioukov, P. Almagro, and M. Angeles Serrano,
Small Worlds and Clustering in Spatial Networks,
Physical Review Research, v.2, 023040, 2020
(DOI,
arXiv),
One-sentence abstract: Necessary and sufficient conditions for small worldness and nonvanishing clustering in homogeneous and heterogeneous soft random geometric graphs.
- P. van der Hoorn, I. Voitalov, R. van der Hofstad, and D. Krioukov,
Problems with Classification, Hypothesis Testing, and Estimator Convergence in the Analysis of Degree Distributions in Networks,
arXiv,
One-sentence abstract: Some comments about that scale-free networks are rare.
- I. Voitalov, P. van der Hoorn, R. van der Hofstad, and D. Krioukov,
Scale-Free Networks Well Done,
Physical Review Research, v.1, 033034, 2019
(DOI,
arXiv,
software and data),
Press: TU/e,
One-sentence abstract: A proper way to deal with power laws in network science.
- M. Mitrovic Dankulov, G. Caldarelli, S. Fortunato, and D. Krioukov,
Classifying Networks with dk-series
(DOI),
In Multiplex and Multilevel Networks (S. Battiston, G. Caldarelli, and A. Garas (edt.)),
Oxford University Press, Oxford, UK, 2019
(DOI, Amazon),
One-sentence abstract: A generalization of dk-series to multiplex and multilayer networks.
- J. Carifio, W. Cunningham, J. Halverson, D. Krioukov, C. Long, and B. Nelson,
Vacuum Selection from Cosmology on Networks of String Geometries,
Physical Review Letters, v.121, 101602, 2018
(DOI, arXiv),
Press: NU,
One-sentence abstract: String theory landscape networks of string geometries provide new tools to study the vacuum selection problem in cosmology in the context of eternal inflation.
- W. Cunningham and D. Krioukov,
Causal Set Generator and Action Computer,
Computer Physics Communications, v.233, p.123-133, 2018
(DOI,
arXiv,
software),
One-sentence abstract: An optimized software package to generate causal sets sprinkled over Lorentzian manifolds, and to compute their Benincasa-Dowker action.
- A. Kartun-Giles, D. Krioukov, J.P. Gleeson, Y. Moreno, and G. Bianconi,
Sparse Power-Law Network Model for Reliable Statistical Predictions Based on Sampled Data,
Entropy, v.20, n.4, p.257, 2018
(DOI, arXiv),
One-sentence abstract: A projective but not exchangeable formulation of the hypersoft configuration model.
- M. Kitsak, A. Ganin, D. Eisenberg, P. Krapivsky, D. Krioukov, D. Alderson, and I. Linkov,
Stability of a Giant Connected Component in a Complex Network,
Physical Review E, v.97, 012309, 2018
(DOI, arXiv),
One-sentence abstract: The higher the node degree, the higher the probability that it belongs to the giant connected component in bond percolation.
- W. Cunningham, D. Rideout, J. Halverson, and D. Krioukov,
Exact Geodesic Distances in FLRW Spacetimes,
Physical Review D, v.96, 103538, 2017
(DOI, arXiv),
One-sentence abstract: An exact formula for the geodesic distance between a pair of points in any spatially flat FLRW spacetime.
- P. van der Hoorn, G. Lippner, and D. Krioukov,
Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution,
Journal of Statistical Physics, v.173(3), p.806-844, 2018 (DOI, arXiv),
One-sentence abstract: The hypersoft configuration model maximizes graph entropy under the power-law degree distribution constraint in the large-graph limit.
- J. Carifio, J. Halverson, D. Krioukov, and B. Nelson,
Machine Learning in the String Landscape,
Journal of High Energy Physics (JHEP), v.2017, p.157, 2017
(DOI, arXiv),
Press:
Science Trends,
One-sentence abstract: Machine learning can be used for numeric predictions and for suggesting new rigorous results in string landscapes.
- I. Voitalov, R. Aldecoa, L. Wang, and D. Krioukov,
Geohyperbolic Routing and Addressing Schemes,
ACM SIGCOMM Computer Communication Review (CCR), v.47, n.3, p.11-18, 2017
(DOI, arXiv,
software and data),
One-sentence abstract: Geohyperbolic addressing and network design schemes, combining geographic and centrality addressing into hyperbolic addressing, allow for maximally scalable, efficient and robust routing in dynamic networks.
- W. Cunningham, K. Zuev, and D. Krioukov,
Navigability of Random Geometric Graphs in the Universe and Other Spacetimes,
Nature Scientific Reports, v.7, p.8699, 2017 (DOI, arXiv),
One-sentence abstract: A universe is navigable only if contains dark energy.
- M. Kitsak, F. Papadopoulos, and D. Krioukov,
Latent Geometry of Bipartite Networks,
Physical Review E, v.95, 032309, 2017
(DOI, arXiv),
One-sentence abstract: Strong bipartite clustering and power-law distributions of the number of common neighbors are signature of latent geometry in bipartite networks, which can be inferred using the common neighbor statistics.
- V. Lehman, A. Gawande, B. Zhang, L. Zhang, R. Aldecoa, D. Krioukov, and L. Wang,
An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN,
IEEE/ACM 24th International Symposium on Quality of Service (IWQoS), p.1-10, 2016
(DOI, arXiv),
One-sentence abstract: Packet-level emulations of hyperbolic routing show that its routing control message overhead is nearly a constant function of the network size, yielding orders of magnitude higher scalability than in traditional routing protocols.
- D. Krioukov,
Clustering Implies Geometry in Networks,
Physical Review Letters, v.116, 208302, 2016
(DOI, arXiv),
One-sentence abstract: Networks with strong homogeneous clustering are geometric.
- K. Zuev, F. Papadopoulos, and D. Krioukov,
Hamiltonian Dynamics of Preferential Attachment,
Journal of Physics A: Mathematical and Theoretical, v.49, n.10, p.105001, 2016
(DOI, arXiv),
One-sentence abstract: Soft preferential attachment and soft configuration model are the same ensembles of random graphs with the same Hamiltonian appearing in Hamilton's equations describing preferential attachment dynamics of networks.
- M. Kitsak, A. Elmokashfi, S. Havlin, and D. Krioukov,
Long-Range Correlations and Memory in the Dynamics of Internet Interdomain Routing,
PLOS ONE 10(11): e0141481, 2015 (DOI, arXiv,
data),
One-sentence abstract: Time series of BGP updates are characterized by power laws, long-range correlations, and memory effects.
- K. Zuev, O. Eisenberg, and D. Krioukov,
Exponential Random Simplicial Complexes,
Journal of Physics A: Mathematical and Theoretical, v.48, n.46, p.465002,
2015 (DOI, arXiv,
JPA issue cover image),
One-sentence abstract: Generalization of edge-independent exponential random graph models to simplicial complexes.
- C. Orsini, M. Mitrovic Dankulov, P. Colomer-de-Simon, A. Jamakovic, P. Mahadevan, A. Vahdat, K. Bassler, Z. Toroczkai, M. Boguna, G. Caldarelli, S. Fortunato, and D. Krioukov,
Quantifying Randomness in Real Networks,
Nature Communications, v.6, p.8627, 2015 (DOI,
arXiv,
software),
One-sentence abstract: Many real networks are 2.5k-random, where 2.5k = degrees + correlations + clustering.
- A. Jamakovic, P. Mahadevan, A. Vahdat, M. Boguna, and D. Krioukov,
How Small Are Building Blocks of Complex Networks,
arXiv,
One-sentence abstract: The global structure of
complex networks is statistically determined by the probability of the
presence of links between node triples, once this probability accounts
for the degree of the individual nodes.
- R. Aldecoa, C. Orsini, and D. Krioukov,
Hyperbolic Graph Generator,
Computer Physics Communications, v.196, p.492-296, 2015
(DOI,
arXiv,
software),
One-sentence abstract: A description of the software package to generate
hyperbolic and other random graphs.
- F. Papadopoulos, R. Aldecoa, and D. Krioukov,
Network Geometry Inference using Common Neighbors,
Physical Review E, v.92, 022807, 2015
(DOI,
arXiv,
software),
One-sentence abstract: The common neighbor similarity statistics allows to infer hyperbolic geometry from network structure even more accurately.
- A. Gulyas, J. Biro, A. Korosi, G. Retvari, and D. Krioukov,
Navigable Networks as Nash Equilibria of Navigation Games,
Nature Communications, v.6, p.7651, 2015 (DOI, arXiv),
Press:
NU,
NU2,
U.S. News & World Report,
International Business Times,
R&D Magazine,
redOrbit,
PhysOrg,
Scicasts,
BPoD,
index,
Tendencias21,
Espectador,
...
One-sentence abstract: Nash equilibrium networks that have the smallest possible number of links required to maintain 100% navigability, form skeletons of real networks and share with them their basic structural properties.
- K. Zuev, M. Boguna, G. Bianconi, and D. Krioukov,
Emergence of Soft Communities from Geometric Preferential Attachment,
Nature Scientific Reports, v.5, p.9421, 2015 (DOI, arXiv),
One-sentence abstract: Scale-free degree distributions, strong clustering, and soft community structure emerge from geometric preferential attachment, similar to inflation models in cosmology.
- F. Papadopoulos, C. Psomas, and D. Krioukov,
Network Mapping by Replaying Hyperbolic Growth,
IEEE/ACM Transactions on Networking (ToN), v.23, n.1, p.198-211, 2015
(DOI,
arXiv,
software),
One-sentence abstract: A simple and accurate method to map complex
networks to their hyperbolic spaces.
- C. Orsini, E. Gregori, L. Lenzini, and D. Krioukov,
Evolution of the Internet
k-dense structure,
IEEE/ACM Transactions on Networking (ToN), v.22, n.6, p.1769-1780, 2014
(DOI,
arXiv),
One-sentence abstract: The normalized
k-dense decomposition of the
Internet is time-invariant.
- D. Krioukov,
Brain Theory,
Frontiers in Computational Neuroscience, v.8, 114, 2014
(DOI),
One-sentence abstract: Compared to fundamental sciences, our understanding of complex systems is still in its infancy.
- M. Boguna, M. Kitsak, and D. Krioukov,
Cosmological Networks,
New Journal of Physics, v.16, 093031, 2014
(DOI,
arXiv),
One-sentence abstract: A network of causal connections among stationary
observers randomly distributed in any open homogeneous and isotropic FLRW
universe is a growing power-law graph.
- K. Anand, D. Krioukov, and G. Bianconi,
Entropy distribution and condensation in random networks with a given degree distribution,
Physical Review E, v.89, 062807, 2014
(DOI,
arXiv),
One-sentence abstract: Entropy of scale-free networks is self-averaging.
- D. Krioukov and M. Ostilli,
Duality between equilibrium and growing networks,
Physical Review E, v.88, 022808, 2013
(DOI,
arXiv),
One-sentence abstract: Under certain conditions, satisfied in random
geometric graphs, causal sets, and some real networks, equilibrium and growing network models are exactly identical.
- F. Papadopoulos, C. Psomas, and D. Krioukov,
Replaying the Geometric Growth of Complex Networks and Application to the AS
Internet,
ACM SIGMETRICS Performance Evaluation Review, v.40, n.3, p.104-106, 2012 (DOI,
arXiv),
One-sentence abstract: Replaying the historical growth of complex
networks using popularity*similarity optimization maps them accurately to their
hyperbolic spaces, and predicts missing links.
- D. Krioukov, M. Kitsak, R. Sinkovits, D. Rideout, D. Meyer, and M. Boguna,
Network Cosmology,
Nature Scientific Reports, v.2, p.793, 2012 (DOI,
arXiv,
data),
Press:
UCSD,
SDSC,
Space,
Time,
TheRegister,
CBS,
HuffingtonPost,
HuffingtonPostUK,
PopularScience,
LiveScience,
Slashdot,
Robots.Net,
SanFranciscoChronicle,
PhysOrg,
ScienceDaily,
TGDaily,
DigitalJournal,
Vesti,
MK,
LifeNews,
theRunet, ...
One-sentence abstract: The large-scale structure and dynamics of complex networks and the universe are asymptotically identical.
- F. Papadopoulos, M. Kitsak, M. Angeles Serrano, M. Boguna, and D. Krioukov,
Popularity versus Similarity in Growing Networks,
Nature, v.489, p.537, 2012 (DOI,
arXiv,
data),
Press:
UCSD,
SDSC,
Nature,
Nature Physics,
PhysOrg,
ScienceDaily,
AMS,
Le Scienze,
STRF,
Elsevier, ...
One-sentence abstract: Trade-offs between popularity and similarity shape
the structure and dynamics of growing complex networks, with preferential
attachment emerging from local optimization processes, casting these networks as
random geometric graphs growing in hyperbolic spaces.
- D. Krioukov,
The Proof of Innocence,
Annals of Improbable Research, v.18, n.4, p.12, 2012 (AIR,
arXiv),
Press:
a top physics newsmaker of 2012, appearing at all major news, TV, and radio channels worldwide,
such as
ABC,
ABC Science,
BBC,
CBS,
CNET,
CNN,
CNN International,
Compulenta,
Corriere,
Daily Mail,
Echo of
Moscow,
Fox News,
KPBS,
LA Times,
LentaRu,
MSN,
NBC,
NewsRu,
NPR,
CarTalk,
Physics Central,
Salon,
Science,
Slashdot,
The Star,
Union Tribune,
Wired,
Yahoo, ...
One-sentence abstract: A way to fight your traffic tickets.
- M. Kitsak and D. Krioukov,
Hidden Variables in Bipartite Networks,
Physical Review E, v.84, 026114, 2011
(DOI,
arXiv),
One-sentence abstract: The hidden variable framework is extended to
bipartite networks.
- M. Angeles Serrano, D. Krioukov, and M. Boguna,
Percolation in Self-Similar Networks,
Physical Review Letters, v.106, 048701, 2011 (DOI,
arXiv),
One-sentence abstract: Self-similar networks have zero percolation threshold.
- D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguna,
Hyperbolic Geometry of Complex Networks,
Physical Review E, v.82, 036106, 2010 (DOI,
arXiv)
One-sentence abstract: A framework to study the
structure and function of complex networks in purely geometric terms.
- M. Boguna, F. Papadopoulos, and D. Krioukov,
Sustaining the Internet with Hyperbolic Mapping,
Nature Communications, v.1, p.62, 2010 (DOI,
arXiv,
data),
Press:
UCSD,
SDSC,
U.
Barcelona,
Nature,
New
Scientist,
IEEE
Spectrum,
Communications
of the ACM,
Computerworld,
MIT Scope,
The
Register,
CBC,
El
Pais,
TOVIMA,
Electronics
Weekly,
PhysOrg,
ACMEscience,
Science
Daily,
I
Programmer,
ISPreview,
PC
Pro,
R&D
Mag,
EnterTheGrid,
CNews,
Compulenta,
Daily
UA,
CyprusMail,
...
One-sentence abstract: Mapping the Internet to
its underlying hyperbolic space enables optimal routing in the Internet.
- F. Papadopoulos, D. Krioukov, M. Boguna, and A. Vahdat,
Greedy Forwarding in Dynamic Scale-Free Networks Embedded
in Hyperbolic Metric Spaces,
INFOCOM 2010 (DOI,
arXiv),
One-sentence abstract: Almost all greedy-routing
paths reach their destinations and follow shortest paths in scale-free
networks growing on the hyperbolic plane.
- S. Shakkottai, M. Fomenkov, R. Koga, D. Krioukov, and kc
claffy,
Evolution of the Internet AS-Level Ecosystem,
European Physical Journal B, v.74, p.271-278, 2010
(DOI,
arXiv),
COMPLEX 2009 (DOI,
arXiv),
One-sentence abstract: A customer-provider-based
modification of preferential attachment explains Internet topology
evolution.
- X. Dimitropoulos, D. Krioukov, A. Vahdat, and G. Riley,
Graph Annotations in Modeling Complex Network Topologies,
ACM Transactions on Modeling and Computer Simulation,
v.19, n.4, p.17, 2009 (DOI,
arXiv),
One-sentence abstract: How to model, analyze,
and generate complex network topologies using the correlations among
network-specific annotations ("types") of links and nodes.
- D. Krioukov, F. Papadopoulos, A. Vahdat, and M. Boguna,
Curvature and Temperature of Complex Networks,
Physical Review E, v.80, 035101(R), 2009 (DOI,
arXiv),
One-sentence abstract: Hidden hyperbolic
geometries, which are abstractions of the hierarchical (community)
structure of complex networks, underlie and explain their observed
scale-free topologies.
- D. Krioukov, F. Papadopoulos, M. Boguna, and A. Vahdat,
Greedy Forwarding in Scale-Free Networks Embedded in
Hyperbolic Metric Spaces,
ACM SIGMETRICS Performance Evaluation Review, v.37, n.2,
p.15-17, 2009 (DOI,
arXiv),
One-sentence abstract: Greedy forwarding in
synthetic scale-free networks emerging on underlying hyperbolic metric
spaces is remarkably efficient and robust with respect to link failures.
- kc claffy, Y. Hyun, K. Keys, M. Fomenkov, and D. Krioukov,
Internet Mapping: From Art to Science,
CATCH 2009 (DOI),
One-sentence abstract: Introducing Ark,
CAIDA's new Internet measurement infrastructure.
- M. Boguna and D. Krioukov,
Navigating Ultrasmall Worlds in Ultrashort Time,
Physical Review Letters, v.102, 058701, 2009 (DOI,
arXiv),
Press:
Nature,
NewScientist,
PhysOrg,
One-sentence abstract: Greedy-routing paths are
asymptotically shortest paths in scale-free, strongly clustered
networks.
- M. Boguna, D. Krioukov, and kc claffy,
Navigability of Complex Networks,
Nature Physics, v.5, p.74-80, 2009 (DOI,
arXiv),
Press:
UCSD,
Nature,
DailyTech,
Science
Daily,
Voice
of San Deigo, Technology
Review,
news:lite,
Lenta.ru,
...
One-sentence abstract: Complex networks have
navigable topologies.
- P. Krapivsky and D. Krioukov,
Scale-Free Networks as Preasymptotic Regimes of
Superlinear Preferential Attachment,
Physical Review E, v.78, 026114, 2008 (DOI,
arXiv),
One-sentence abstract: Even super-linear
preferential attachment can produce scale-free networks, although it
can do so only in its vast pre-asymptotic regimes, which bring up the
question what if observed power laws are actually pre-asymptotic
effects?
- X. Dimitropoulos, M. Angeles Serrano, and D. Krioukov,
On Cycles in AS Relationships,
ACM SIGCOMM Computer Communication Review (CCR), v.38,
n.3, p.103-104, 2008 (DOI,
arXiv),
One-sentence abstract: Cycles induced by
business relationships among ASs are expected.
- M. Angeles Serrano, D. Krioukov, and M. Boguna,
Self-Similarity of Complex Networks and Hidden Metric
Spaces,
Physical Review Letters, v.100, 078701, 2008 (DOI,
arXiv),
One-sentence abstract: Self-similarity of
clustering in real complex networks provides a strong empirical
evidence that hidden metric spaces underlie these networks.
- P. Mahadevan, C. Hubble, D. Krioukov, B. Huffaker, and A. Vahdat,
Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies,
SIGCOMM 2007 (DOI, software),
One-sentence abstract: Network topology generator inspired by the dK-series.
- D. Krioukov, kc claffy, K. Fall, and A. Brady,
On Compact Routing for the Internet,
ACM SIGCOMM Computer Communication Review (CCR), v.37,
n.3, 2007 (DOI,
arXiv),
One-sentence abstract: Compact routing generally
assumes the full global knowledge of the network topology, and
therefore it cannot help with communication overhead/convergence
scaling problems in Internet routing.
- D. Krioukov, F. Chung, kc claffy, M. Fomenkov, A.
Vespignani, and W. Willinger,
The Workshop on Internet Topology (WIT) Report,
ACM SIGCOMM Computer Communication Review (CCR), v.37,
n.1, 2007 (DOI,
arXiv),
One-sentence abstract: Some agreements about the
Internet topology among researchers from different communities are
reported; there are more disagreements, of course!
- X. Dimitropoulos, D. Krioukov, M. Fomenkov, B. Huffaker, Y.
Hyun, kc claffy, and G. Riley,
AS Relationships: Inference and Validation,
ACM SIGCOMM Computer Communication Review (CCR), v.37,
n.1, 2007 (DOI,
arXiv,
data),
One-sentence abstract: Infer the AS
relationships using our best-of-breed heuristics, validate their
results via a questionnaire to network operators, adjust the code to
run automatically once a week, and make the data publicly available.
- P. Mahadevan, D. Krioukov, K. Fall, and A. Vahdat,
Systematic Topology Analysis and Generation Using Degree
Correlations,
SIGCOMM 2006 (DOI,
arXiv),
One-sentence abstract:
dK-series
is a series of degree correlations in small graphs on increasing size d,
which does not have to be large: reproducing the 2K-correlations
for the AS Internet topology reproduces its global structure, while d=3
is enough even for "very designed, non-random" graphs.
- X. Dimitropoulos, D. Krioukov, G. Riley, and kc claffy,
Revealing the Autonomous System Taxonomy: The Machine
Learning Approach,
PAM 2006 (best paper award) (PAM,
arXiv,
data),
One-sentence abstract: All you wish to know
about the AS-level Internet topology: ASs are classified into AS types
using a series of AS attributes, and all the data is made publicly
available, along with AS links classified by AS business relationships.
- P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X.
Dimitropoulos, kc claffy, and A. Vahdat,
The Internet AS-Level Topology: Three Data Sources and One
Definitive Metric,
ACM SIGCOMM Computer Communication Review (CCR), v.36,
n.1, 2006 (DOI,
arXiv,
data),
Lessons from Three Views of the Internet Topology,
Technical report CAIDA-TR-2005-02, 2005 (CAIDA,
arXiv),
One-sentence abstract: Extract the Internet AS
topology from BGP routing tables and updates, traceroutes (skitter),
and WHOIS databases, compute the most popular metrics for all the
extracted topologies, and make all the resulting data (graphs and
computed metrics) publicly available.
- X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and
G. Riley,
Inferring AS Relationships: Dead End or Lively Beginning,
WEA 2005; LNCS 3503:113-125, April 2005 (DOI,
arXiv),
One-sentence abstract: Yet another AS business
relationship inference heuristic combining the best features of the
best existing heuristics.
- X. Dimitropoulos, D. Krioukov, and G. Riley,
Revisiting Internet AS-Level Topology Discovery,
PAM 2005; LNCS 3431:177-188, March 2005 (DOI,
arXiv),
One-sentence abstract: In the BGP updates data
the number of unique AS links grows linearly with the observation time,
while the topological properties of BGP-updates- and BGP-tables-derived
AS graphs are similar.
- D. Krioukov, K. Fall, and X. Yang,
Compact Routing on Internet-Like Graphs,
INFOCOM 2004 (DOI,
INFOCOM),
Technical report
IRB-TR-03-10 (arXiv),
One-sentence abstract: Compact routing on
scale-free networks yields essentially the best possible trade-off
between the average stretch (optimality of paths) and size of routing
tables (memory requirements per node).
