P. Borgnat
| joint-work with Patrice Abry & Guillaume Dewaele (ENS de Lyon, CNRS),
Kensuke Fukuda (NII, Tokyo) and Kenjiro Cho (IIJ, Tokyo)
| | Internet Traffic: Analysis, Modeling and the Real-world
| | Progresses made in Internet Traffic Measurement in the past ten years
have led to a better knowledge of what is really transported over the
Internet. Analysis and Modeling of Internet Traffic will be discussed
(mostly at the level of TCP/IP traffic on links), presenting first the
ubiquitous statistical properties found in traffic such as Long Range
Dependence or Heavy-Tailness, that are used in models of traffic, and
their experimental evidences. Then we will explain how and why
advanced statistical methods of analysis are necessary to understand
even simple features of Internet traffic when dealing with traces from
the real-world, considered that they usually consist of large data
with varying compositions of traffic and many anomalies. On some
examples, we will show how methods such as random projections
(sketches) combined with multi-resolution analysis provide
practitioners with efficient and robust tools to disentangle actual
features and evolutions from time localized events such as anomalies
and link congestions. Finally, for traffic classification and anomaly
detection, we will discuss methods adaptable to operational
constraints of traffic monitoring, that rely on a statistical
characterisation of hosts in the traffic.
|
|
C. Castellano
| Nonequilibrium dynamics on complex topologies: models for epidemics and opinions
| | Dynamical processes are strongly affected by the topology of the
subtrate where they take place.
In the past decade the recognition that, in many fields,
the interaction patterns are described by complex networks
has generated a widespread interest about the relation between
structure and dynamics. New, nontrivial behavior may arise from the
interplay between simple dynamical rules and disordered topologies.
In this talk I will present some recent results on very simple
models for epidemics, such as the contact process and the
susceptible-infected-susceptible model.
I will discuss the existence of finite thresholds,
the behavior on finite networks and the role of quenched disorder.
I will then consider the voter model,
a model for opinion dynamics (and several other phenomena)
and discuss its nontrivial behavior on complex topologies.
A common theme will be the approach to these problems by mean-field-type
methods, with the identifications of their strenghts and limitations.
|
|
S. Fortunato
| Community detection algorithms: a comparative analysis
| | Uncovering the community structure exhibited by real networks is a
crucial step towards an understanding
of complex systems that goes beyond the local organization of their
constituents. Many algorithms have
been proposed so far, but none of them has been subjected to strict
tests to evaluate their performance.
Here we test several methods against a recently introduced class of
realistic benchmark graphs, with heterogeneous distributions of
degree and community size. The methods are also tested against the
benchmark by Girvan and Newman
and on random graphs. As a result of our analysis, three recent
algorithms introduced by Rosvall and Bergstrom,
Blondel et al. and Ronhovde and Nussinov, respectively, have an
excellent performance, with the additional
advantage of low computational complexity, which enables one to
analyze large systems.
|
|
D. Krioukov
| Optimal routing in a hyperbolically mapped Internet
| | We establish a connection between the scale-free topology of complex
networks, and the hyperbolic geometry of hidden metric spaces
underlying these networks. Given a hyperbolic space, networks
topologies with scale-free degree distributions and strong
clustering naturally emerge on top of the space as topological
reflections of its hyperbolic geometry. Conversely, for any
scale-free network with strong clustering, there is an effective
hyperbolic space underlying the network. The underlying hyperbolic
geometry enables greedy routing with optimal efficiency. Greedy
routing does not require any global information about network
topology to navigate the network. At each hop, greedy routing
selects as the next hop the current hop neighbor closest to the
destination in the underlying hyperbolic space. We show that in
complex networks mapped to their hyperbolic spaces, greedy routing
always succeeds reaching the destination, following the
topologically shortest paths. Furthermore, we show that even without
re-mapping the network or changing any node coordinates, this
navigation efficiency is remarkably robust with respect to rapid
network dynamics, and catastrophic levels of network damage. We map
the real Internet AS-level topology to its hyperbolic space, and
find that greedy routing using this map exhibits similar efficiency.
These results effectively deliver a solution for Internet
interdomain routing with theoretically best possible scaling
properties. Not only routing table sizes and stretch are as small as
possible, but also routing communication overhead is reduced to
zero.
|
|
| D. Peleg
|
joint with Shiri Chechik, Michael Langberg and Liam Roditty
| Competitive fault tolerant Distance Oracles and Routing Schemes
| | An f-competitive fault-tolerant distance oracle for a weighted undirected
graph G(V,E) is a data structure capable of answering restricted distance
queries between vertex pairs, i.e., calculating distances on a subgraph
avoiding some failed edges. This talk will present an efficiently
constructible f-competitive fault-tolerant distance oracle that given a
triplet (s,t,F), where s and t are vertices and F is a set of failed edges,
returns an estimate of the distance between s and t in G(V,E-F). For an
integer parameter k>0, the size of the data structure is
O(kn^{1+(8(f+1))/(k+2(f+1))} log(nW)), where W is the heaviest edge in G,
the stretch (approximation ratio) of the returned distance is 2k-1, and the
query time is O(|F| log^2n loglog n loglog d), where d is the distance
between s and t in G(V,E-F).
The talk will also consider f-competitive fault-tolerant compact routing
schemes, namely, routing schemes that avoid a given set of failed edges. It
will present a scheme capable of withstanding up to two edge failures. Given
a message M destined to t at a source vertex s, in the presence of a failed
edge set F of size |F| <= 2 (unknown to s), our scheme routes M from s to t
in a distributed manner, over a path of length at most O(k) times the length
of the optimal path (avoiding F). The total amount of information stored in
vertices of G is O(k n^{1+1/k} log(nW) logn).
|
|
| M. A. Serrano
|
| Self-similarity of complex networks and hidden metric spaces
|
| Self-similarity and scale invariance are traditionally known as
characteristics of certain geometric objects, such as fractals, or of field
theories describing system
dynamics near critical points of phase transitions. In these cases, objects
or physical systems are intrinsically embedded in metric spaces and distance
scales in these spaces are natural scaling factors. In complex networks, it
is difficult to define self-similarity and scale invariance in a proper
geometric sense because many networks are not explicitly embedded in any
physical space and they lack any metric structure except the topological one
given by the collection of lengths of shortest paths between nodes, which is
a poor source of length-based scaling factors since it does not have large
lengths as it usually exhibits the small-world property. We demonstrate that
hidden metric spaces underlying the observed topologies of some complex
networks --in particular the BGP map of the Internet at the autonomous
system level and the PGP social web of trust-- appear to provide a plausible
explanation of the observed self-similarity of their main topological
characteristics รณ-degree distributions, degree-degree correlations, and
clustering-- with respect to a simple degree-thresholding renormalization
scheme which produces a hierarchy of nested subgraphs. If we take the most
generic interpretation of hidden distances as measures of either structural
or functional similarity between nodes, and admit that more similar nodes
are more likely to be connected, then the hidden and observable forms of
transitivity become clearly related. Hidden metric spaces may find
far-reaching applications, for instance in the design of efficient routing
and searching algorithms for communication and social networks.
|
