Ktisis Cyprus University of Technologyhttps://ktisis.cut.ac.cyThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 21 Nov 2019 08:55:20 GMT2019-11-21T08:55:20Z5031Popularity 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.
Sun, 01 Jan 2012 00:00:00 GMThttps://ktisis.cut.ac.cy/handle/10488/58312012-01-01T00:00:00ZNetwork 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:00ZNetwork 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