Source author record

Fragkiskos Papadopoulos

Fragkiskos Papadopoulos appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

12works
8topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Dynamics of hot random hyperbolic graphs

We derive the most basic dynamical properties of random hyperbolic graphs (the distributions of contact and intercontact durations) in the hot regime (network temperature $T > 1$). We show that for sufficiently large networks the contact distribution decays as a power law with exponent $2+T > 3$ for durations $t > T$, while for $t < T$ it exhibits exponential-like decays. This result holds irrespective of the expected degree distribution, as long as it has a finite $T^{\text{th}}$ moment. Otherwise, the contact distribution depends on the expected degree distribution and we show that if the latter is a power law with exponent $γ\in (2, T+1]$, then the former decays as a power law with exponent $γ+1 > 3$. On the other hand, the intercontact distribution exhibits power-law decays with exponent $2-T \in (0, 1)$ for $T \in (1,2)$, while for $T > 2$ it displays linear decays with a slope that depends on the observation interval. This result holds irrespective of the expected degree distribution as long as it has a finite $T^{\text{th}}$ moment if $T \in (1,2)$, or a finite second moment if $T > 2$. Otherwise, the intercontact distribution depends on the expected degree distribution and if the latter is a power law with exponent $γ\in (2, 3)$, then the former decays as a power law with exponent $3-γ\in (0,1)$. Thus, hot random hyperbolic graphs can give rise to contact and intercontact distributions that both decay as power laws. These power laws however are unrealistic for the case of the intercontact distribution, as their exponent is always less than one. These results mean that hot random hyperbolic graphs are not adequate for modeling real temporal networks, in stark contrast to cold random hyperbolic graphs ($T < 1$). Since the configuration model emerges at $T \to \infty$, these results also suggest that this is not an adequate null temporal network model.

preprint2022arXiv

Embedding-aided network dismantling

Optimal percolation concerns the identification of the minimum-cost strategy for the destruction of any extensive connected components in a network. Solutions of such a dismantling problem are important for the design of optimal strategies of disease containment based either on immunization or social distancing. Depending on the specific variant of the problem considered, network dismantling is performed via the removal of nodes or edges, and different cost functions are associated to the removal of these microscopic elements. In this paper, we show that network representations in geometric space can be used to solve several variants of the network dismantling problem in a coherent fashion. Once a network is embedded, dismantling is implemented using intuitive geometric strategies. We demonstrate that the approach well suits both Euclidean and hyperbolic network embeddings. Our systematic analysis on synthetic and real networks demonstrates that the performance of embedding-aided techniques is comparable to, if not better than, the one of the best dismantling algorithms currently available on the market.

preprint2020arXiv

k-core structure of real multiplex networks

Multiplex networks are convenient mathematical representations for many real-world -- biological, social, and technological -- systems of interacting elements, where pairwise interactions among elements have different flavors. Previous studies pointed out that real-world multiplex networks display significant inter-layer correlations -- degree-degree correlation, edge overlap, node similarities -- able to make them robust against random and targeted failures of their individual components. Here, we show that inter-layer correlations are important also in the characterization of their $\mathbf{k}$-core structure, namely the organization in shells of nodes with increasingly high degree. Understanding $k$-core structures is important in the study of spreading processes taking place on networks, as for example in the identification of influential spreaders and the emergence of localization phenomena. We find that, if the degree distribution of the network is heterogeneous, then a strong $\mathbf{k}$-core structure is well predicted by significantly positive degree-degree correlations. However, if the network degree distribution is homogeneous, then strong $\mathbf{k}$-core structure is due to positive correlations at the level of node similarities. We reach our conclusions by analyzing different real-world multiplex networks, introducing novel techniques for controlling inter-layer correlations of networks without changing their structure, and taking advantage of synthetic network models with tunable levels of inter-layer correlations.

preprint2016arXiv

Exploiting Path Diversity in Datacenters using MPTCP-aware SDN

Recently, Multipath TCP (MPTCP) has been proposed as an alternative transport approach for datacenter networks. MPTCP provides the ability to split a flow into multiple paths thus providing better performance and resilience to failures. Usually, MPTCP is combined with flow-based Equal-Cost Multi-Path Routing (ECMP), which uses random hashing to split the MPTCP subflows over different paths. However, random hashing can be suboptimal as distinct subflows may end up using the same paths, while other available paths remain unutilized. In this paper, we explore an MPTCP-aware SDN controller that facilitates an alternative routing mechanism for the MPTCP subflows. The controller uses packet inspection to provide deterministic subflow assignment to paths. Using the controller, we show that MPTCP can deliver significantly improved performance when connections are not limited by the access links of hosts. To lessen the effect of throughput limitation due to access links, we also investigate the usage of multiple interfaces at the hosts. We demonstrate, using our modification of the MPTCP Linux Kernel, that using multiple subflows per pair of IP addresses can yield improved performance in multi-interface settings.

preprint2016arXiv

Hamiltonian Dynamics of Preferential Attachment

Prediction and control of network dynamics are grand-challenge problems in network science. The lack of understanding of fundamental laws driving the dynamics of networks is among the reasons why many practical problems of great significance remain unsolved for decades. Here we study the dynamics of networks evolving according to preferential attachment, known to approximate well the large-scale growth dynamics of a variety of real networks. We show that this dynamics is Hamiltonian, thus casting the study of complex networks dynamics to the powerful canonical formalism, in which the time evolution of a dynamical system is described by Hamilton's equations. We derive the explicit form of the Hamiltonian that governs network growth in preferential attachment. This Hamiltonian turns out to be nearly identical to graph energy in the configuration model, which shows that the ensemble of random graphs generated by preferential attachment is nearly identical to the ensemble of random graphs with scale-free degree distributions. In other words, preferential attachment generates nothing but random graphs with power-law degree distribution. The extension of the developed canonical formalism for network analysis to richer geometric network models with non-degenerate groups of symmetries may eventually lead to a system of equations describing network dynamics at small scales.

preprint2015arXiv

Network Geometry Inference using Common Neighbors

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.

preprint2014arXiv

Network Mapping by Replaying Hyperbolic Growth

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.

preprint2014arXiv

Performance Rescaling of Complex Networks

Recent progress in network topology modeling [1], [2] has shown that it is possible to create smaller-scale replicas of large complex networks, like the Internet, while simultaneously preserving several important topological properties. However, the constructed replicas do not include notions of capacities and latencies, and the fundamental question of whether smaller networks can reproduce the performance of larger networks remains unanswered. We address this question in this letter, and show that it is possible to predict the performance of larger networks from smaller replicas, as long as the right link capacities and propagation delays are assigned to the replica's links. Our procedure is inspired by techniques introduced in [2] and combines a time-downscaling argument from [3]. We show that significant computational savings can be achieved when simulating smaller-scale replicas with TCP and UDP traffic, with simulation times being reduced by up to two orders of magnitude.

preprint2013arXiv

Popularity versus Similarity in Growing Networks

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.

preprint2010arXiv

Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces

We show that complex (scale-free) network topologies naturally emerge from hyperbolic metric spaces. Hyperbolic geometry facilitates maximally efficient greedy forwarding in these networks. Greedy forwarding is topology-oblivious. Nevertheless, greedy packets find their destinations with 100% probability following almost optimal shortest paths. This remarkable efficiency sustains even in highly dynamic networks. Our findings suggest that forwarding information through complex networks, such as the Internet, is possible without the overhead of existing routing protocols, and may also find practical applications in overlay networks for tasks such as application-level routing, information sharing, and data distribution.

preprint2010arXiv

Hyperbolic Geometry of Complex Networks

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 non-interacting 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.

preprint2010arXiv

Sustaining the Internet with Hyperbolic Mapping

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. Here we present a method to map the Internet to a hyperbolic space. Guided with the constructed map, which we release with this paper, Internet routing exhibits scaling properties close to theoretically 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.