Ktisis Cyprus University of Technologyhttps://ktisis.cut.ac.cyThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sun, 31 May 2020 02:00:57 GMT2020-05-31T02:00:57Z5061- Network geometry inference using common neighborshttps://ktisis.cut.ac.cy/handle/10488/9363Title: Network geometry inference using common neighbors
Authors: Papadopoulos, Fragkiskos; Aldecoa, Rodrigo; Krioukov, Dmitri
Abstract: We introduce and explore a new method for inferring hidden geometric
coordinates of nodes in complex networks based on the number of common
neighbors between the nodes. We compare this approach to the HyperMap method,
which is based only on the connections (and disconnections) between the nodes,
i.e., on the links that the nodes have (or do not have). We find that for high
degree nodes the common-neighbors approach yields a more accurate inference
than the link-based method, unless heuristic periodic adjustments (or
"correction steps") are used in the latter. The common-neighbors approach is
computationally intensive, requiring $O(t^4)$ running time to map a network of
$t$ nodes, versus $O(t^3)$ in the link-based method. But we also develop a
hybrid method with $O(t^3)$ running time, which combines the common-neighbors
and link-based approaches, and explore a heuristic that reduces its running
time further to $O(t^2)$, without significant reduction in the mapping
accuracy. We apply this method to the Autonomous Systems (AS) Internet, and
reveal how soft communities of ASes evolve over time in the similarity space.
We further demonstrate the method's predictive power by forecasting future
links between ASes. Taken altogether, our results advance our understanding of
how to efficiently and accurately map real networks to their latent geometric
spaces, which is an important necessary step towards understanding the laws
that govern the dynamics of nodes in these spaces, and the fine-grained
dynamics of network connections.
Thu, 19 Feb 2015 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/93632015-02-19T00:00:00Z
- Network Mapping by Replaying Hyperbolic Growthhttps://ktisis.cut.ac.cy/handle/10488/9386Title: Network Mapping by Replaying Hyperbolic Growth
Authors: Papadopoulos, Fragkiskos; Psomas, Constantinos; Krioukov, Dmitri
Abstract: 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.
Sun, 01 Feb 2015 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/93862015-02-01T00:00:00Z
- Curvature and temperature of complex networkshttps://ktisis.cut.ac.cy/handle/10488/13910Title: Curvature and temperature of complex networks
Authors: Boguñá, Marián; Papadopoulos, Fragkiskos; Vahdat, Amin; Krioukov, Dmitri
Abstract: We show that heterogeneous degree distributions in observed scale-free topologies of complex networks can emerge as a consequence of the exponential expansion of hidden hyperbolic space. Fermi-Dirac statistics provides a physical interpretation of hyperbolic distances as energies of links. The hidden space curvature affects the heterogeneity of the degree distribution, while clustering is a function of temperature. We embed the internet into the hyperbolic plane and find a remarkable congruency between the embedding and our hyperbolic model. Besides proving our model realistic, this embedding may be used for routing with only local information, which holds significant promise for improving the performance of internet routing. © 2009 The American Physical Society.
Wed, 23 Sep 2009 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/139102009-09-23T00:00:00Z
- Popularity Versus Similarity in Growing Networkshttps://ktisis.cut.ac.cy/handle/10488/5831Title: Popularity Versus Similarity in Growing Networks
Authors: Papadopoulos, Fragkiskos; Kitsak, Maksim; Serrano, Angeles M.; Boguna, Marian; Krioukov, Dmitri
Abstract: The principle that popularity is attractive underlies preferential attachment, which is a common 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 possessed by nodes follows power laws as observed in many real networks. Preferential attachment has been directly validated for some real networks (including the Internet), and can 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 in which new connections optimize certain trade-offs between popularity and similarity, instead of simply preferring popular nodes. The framework has a geometric interpretation in which popularity preference emerges from local optimization. As opposed to preferential attachment, our optimization framework accurately describes the large-scale evolution of technological (the Internet), social (trust relationships between people) and biological (Escherichia coli metabolic) networks, predicting the probability of new links with high precision. The framework that we have developed can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.
Wed, 12 Sep 2012 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/58312012-09-12T00:00:00Z
- Sustaining the Internet with hyperbolic mappinghttps://ktisis.cut.ac.cy/handle/10488/13893Title: Sustaining the Internet with hyperbolic mapping
Authors: Boguñá, Marián; Papadopoulos, Fragkiskos; Krioukov, Dmitri
Abstract: The Internet infrastructure is severely stressed. Rapidly growing overheads associated with the primary function of the Internet - routing information packets between any two computers in the world - cause concerns among Internet experts that the existing Internet routing architecture may not sustain even another decade. In this paper, we present a method to map the Internet to a hyperbolic space. Guided by a constructed map, which we release with this paper, Internet routing exhibits scaling properties that are theoretically close to the best possible, thus resolving serious scaling limitations that the Internet faces today. Besides this immediate practical viability, our network mapping method can provide a different perspective on the community structure in complex networks. © 2010 Macmillan Publishers Limited. All rights reserved.
Mon, 20 Dec 2010 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/138932010-12-20T00:00:00Z
- Hyperbolic geometry of complex networkshttps://ktisis.cut.ac.cy/handle/10488/13900Title: Hyperbolic geometry of complex networks
Authors: Krioukov, Dmitri; Boguñá, Marián; Vahdat, Amin; Papadopoulos, Fragkiskos; Kitsak, Maksim A.
Abstract: We develop a geometric framework to study the structure and function of complex networks. We assume that hyperbolic geometry underlies these networks, and we show that with this assumption, heterogeneous degree distributions and strong clustering in complex networks emerge naturally as simple reflections of the negative curvature and metric property of the underlying hyperbolic geometry. Conversely, we show that if a network has some metric structure, and if the network degree distribution is heterogeneous, then the network has an effective hyperbolic geometry underneath. We then establish a mapping between our geometric framework and statistical mechanics of complex networks. This mapping interprets edges in a network as noninteracting fermions whose energies are hyperbolic distances between nodes, while the auxiliary fields coupled to edges are linear functions of these energies or distances. The geometric network ensemble subsumes the standard configuration model and classical random graphs as two limiting cases with degenerate geometric structures. Finally, we show that targeted transport processes without global topology knowledge, made possible by our geometric framework, are maximally efficient, according to all efficiency measures, in networks with strongest heterogeneity and clustering, and that this efficiency is remarkably robust with respect to even catastrophic disturbances and damages to the network structure. © 2010 The American Physical Society.
Thu, 09 Sep 2010 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/139002010-09-09T00:00:00Z