• View
• Edit
• History
• Print

2011-2012

Gupta and Kumar showed that in a network of $n$ stationary nodes, network capacity scales as order of \sqrt{\frac{n}{\log n}} and packet delivery delay is almost negligible as packets are relayed like 'hot potatoes'.
Later, Grossglauser and Tse showed that if nodes are allowed to move, network capacity can rise to order of $n$ but delay will also increase to the order of \sqrt{n}. Our aim is to increase the network capacity quasi linearly with n while keeping the average delay bounded. In this talk, I will discuss a georouting scheme in a network of n mobile nodes and present the scaling properties its capacity and delay.
In our model, mobile nodes move according to an i.i.d. random walk with velocity $v$ and transmit packets to randomly chosen destinations. The average packet delivery delay of our scheme is of order 1/v and it achieves the network capacity of order \frac{n}{\log n \log \log n}. This shows a practical throughput-delay trade-off, in particular when compared with the seminal results of Gupta and Kumar, and Grossglauser and Tse. The foundation of our improved capacity and delay trade-off relies on the fact that we use a mobility model that contains free space motion, a model that we consider more realistic than classic brownian motions.

This talk will discuss distributed algorithms for separable convex optimization by multiple cooperating agents. Specifically, we will describe a class of algorithms, recently proposed in the literature, for approximating the minimum of a separable convex function. These algorithms are fully distributed, require no centralized supervision, and are robust to unpredictable link and node failures. This makes them particularly useful in distributed control applications, such as formation control and coverage control.
A key subroutine used by these algorithms is a distributed scheme for computing the average of a collection of numbers stored throughout the network. This scheme involves each node taking repeated linear combinations of the values of its neighbors, and over time, as information diffuses through these linear combination, each node's value approaches the average. By designing the best known scheme for such "diffusive" averaging, we derive the best known convergence time for separable distributed optimization, which is our main result. We also describe an application of our methods to the design of coverage control algorithms.

Rationality of consumers supports the most important results in Economic Theory. Traditionally, this feature is understood as an ability to maximize a personal utility function. However, from Optimization Theory we know that the optimization problems are very difficult even for powerful computers (unsolvable, in general). Hence, the rationality assumption needs justification both for the concept of utility function and for the algorithms in use.
This topic was intensively discussed in economic literature during decades (mainly in a verbal form). In this talk we will try to address these questions using the recent advances in numerical methods for large-scale optimization problems. We justify the possibility of rational human behavior on three levels: intuitive individual rationality, rational group activity in stochastic environment, and unintentionally rational individual consumption. In all situations, the consumer behavior corresponds to a known optimization procedure with certain global rate of convergence. We show that very often rationality is naturally induced by appropriate economic environment rather than egoistic will of amoral consumer.

TBA.

Subway networks shape, to some extent, the structure of movements of individuals across a city; similarly, they are being partially shaped by the presence of these individuals in the city. This talk will present two complementary studies describing the dynamic processes which subway networks both host and undergo.
The first analysis focuses on dynamics processes occurring on the subway network of a large city (London) in terms of its commuting patterns. It uses the large scale, real-time electronic ticketing data from the Oyster Card system, introduced less than a decade ago, to reveal a part of the structure and organization of the city. More precisely, this study shows that patterns of intraurban movement are strongly heterogeneous in terms of volume, but not in terms of distance travelled, and that there is a polycentric structure composed of large flows organized around a limited number of activity centers. For smaller flows, the pattern of connections becomes richer and more complex and is not strictly hierarchical since it mixes different levels consisting of different orders of magnitude.
The second study investigates the temporal evolution of the major subway networks in the world over the last century. The main result is that most of these networks tend to converge to a shape which shares some generic features, despite their geographical and economical differences. These features include a core with branches radiating from it to cover about twice the average radial extension of the core. The core generally includes about 60% of the network stations and exhibits an average degree of order 2.5. Interestingly, core and branches define two distinct and universal regimes in terms of the number of stations at a given distance from the barycenter. This result which was difficult to interpret in the framework of fractal geometry finds here a natural explanation.
More broadly, these two types of studies open the way to more integrated analyses of the coevolution between the dynamics on and of subway networks.

Primitive matrices play an important role in the Perron-Frobenius theory and have many applications in the study of Markov chains, page ranking, graphs, optimization, etc. Let us recall that a nonnegative matrix is called primitive if some of its powers is strictly positive. This concept have been extended in the literature to families of nonnegative matrices in many different ways (eventual positivity, m-primitivity, etc.) In contrast to the case of one matrix, when we have a comprehensive description of primitive matrices, the classification of primitive families is usually much more difficult. We introduce the concept of almost primitive families. The family of nonnegative matrices is called almost primitive if there is at least one strictly positive product of these matrices. We show that this concept is quite natural for applications and that many results of the Perron-Frobenius theory can be extended for such families. In particular, almost primitive families can be explicitly classified, and the problem of existence of a positive product is decidable by a polynomial algorithm. The total complexity of the algorithm is md^3, where m is the number of matrices and d is the dimension.

A major challenge in single-particle cryo electron-microscopy is to establish a reliable ab-initio 3D reconstruction using only 2D images without knowing their viewing directions. Reconstruction methods based on common-lines can determine the orientations of images without additional geometric information. However, such reconstruction methods may fail when the common-lines detection rate is low due to the high-level noise in the images. We present an algorithm for determining the viewing direction of all cryo-EM images at once, which is robust to high levels of noise. The algorithm is based on formulating the problem as a synchronization problem, that is, we estimate the relative spatial configuration of pairs of images, and then estimate a global assignment of orientations that satisfies all the pairwise relations. These noisy pairwise relations are combined into a single consistent assignment of orientations by constructing a matrix whose entries encode the pairwise relations. This matrix is shown to have rank 3, and its non-trivial eigenspace is shown to reveal the projection orientation of each image. In particular, we show that the non-trivial eigenvectors encode the rotation matrix that corresponds to each image.

In the IBCN-department at Ghent University, our group called DNA (Design of Networking Algorithms) focuses on theoretical developments with practical applications. Recently, we finished a project on dynamic and stochastic routing in networks, which will be highlighted in this talk: industrially driven, the problem-setting crystallizes to some nice datastructures and algorithms, which were then implemented in a production environment, and now deployed by our partner-company. Apart from that, we will also discuss some other topics on interest and ongoing work at our group.

Distributed computing systems are becoming increasingly large, complex and - at the same time - more and more important for our everyday lives. Designing, managing and reasoning about the structure and dynamics of the underlying communication infrastructures poses enormous challenges in terms of scalability, manageability and robustness. At the same time, the surge of interest in the modeling of large networks and dynamical processes unfolding within them provides valuable insights into the organization of complex systems in nature and society. In this seminar we will discuss how the resulting findings and abstractions can be used constructively in the stochastic management of overlay topologies as well as in the provision of simple decentralized schemes facilitating synchronization and spreading in P2P systems.

Damien Denayer (advisor: Paul Van Dooren): Role models for complex networks

Gaëtan Klein (advisor: Jean-Charles Delvenne): Détection de communautés dans les graphes évolutifs

Jean van der Vaeren (promoteur Vincent Blondel) : Dimension discovery in large feature space datasets.

Aurélien Crucifix (advisor: Vincent Blondel): Algorithms for the crowdsourcing problems;

Jérémy Coppe (advisor: Jean-Charles Delvenne): Dynamique et structure des grands graphes et application aux équations différentielles

Guillaume Vankeerberghen (advisor: Julien Hendrickx et Raphaël Jungers): Analysis of a conjecture regarding Definitive Consensus in multi-agent systems

TBA.

The community structure of complex networks reveals both their organization and hidden relationships among their constituents. Most community detection methods currently available are not deterministic, and their results typically depend on the specific random seeds, initial conditions and tie-break rules adopted for their execution. Consensus clustering is used in data analysis to generate stable results out of a set of partitions delivered by stochastic methods. Here we show that consensus clustering can be combined with any existing method in a self-consistent way, enhancing considerably both the stability and the accuracy of the resulting partitions. This framework is also particularly suitable to monitor the evolution of community structure in temporal networks. An application of consensus clustering to a large citation network of physics papers demonstrates its capability to keep track of the birth, death and diversification of topics.

Complex networks are rarely static, but display dynamics on multiple time scales, and considering the time domain has recently attracted a lot of attention. I will discuss dynamic and temporal features of networks of human communication that reflect the underlying networks of social ties. Such networks display slow dynamics of changes in social ties -- relationships growing and waning in strength, ties becoming discontinued, new ties forming -- together with very nontrivial short-term microdynamics of the timings of individual social interaction events. I will address both time scales: related to slow dynamics, I will present recent results on the changes in the social networks of students finishing high school and moving to university, derived from mobile telephone call records. These results show that although there is significant turnover in these networks, individuals display surprisingly persistent call patterns that are in accordance with the layered network view of the social brain hypothesis. Regarding the short time scales, I will discuss the main characteristics of time series of communication events, from burstiness and correlations, and show how they affect network-wide spreading processes and how they translate into mesoscopic temporal patterns in the form of temporal motifs.

TBA.

We propose in this presentation an experimental method to generate random graphs with an arbitrary degree distribution and obeying any additional constraints. It is indeed possible to create a uniformly random sample of a set of such graphs by generalizing usual link-switching methods. We explore how an experimental process can get us as close as possible to this case. We then consider implementations of these algorithms in various contexts, especially real-world interaction networks.

Current Internet suffers with various scalability-induced problems. We propose in this presentation an inter-domain routing architecture for the Internet-like graph that based on geometry of the network and solves scalability and policy-induced problems. It introduces a Geographic routing Control Platform (GCP), which is a logical entity in each domain for the control of routing and forwarding tasks. This architecture uses a scalable routing algorithm, which is able to discover route between given source and destination and chooses the next hop based on geographic locations of GCP, with the help of a database which map the address and location of particular GCP.

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear programs (Klee-Minty examples). No non-polynomial lower bounds on the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.
Joint work with Oliver Friedmann and Uri Zwick

Several algorithms have been proposed to rank web pages, taking into account the web graph structure. Famous algorithms among them are PageRank, HITS, SALSA and HOTS. We shall focus here on Tomlin's HOTS algorithm, which is a scalable iterative scheme solving a nonlinear network flow problem. The dual solution of this problem, the HOTS score, is then used to rank web pages. An interesting problem in the context of web ranking is the optimization of the score of a web page (or site), given a set of controlled hyperlinks. Whereas PageRank optimization has been studied in several works, the optimization of the HOTS score, and even the convergence of the HOTS algorithm, are less well understood subjects. We prove that the algorithm converges by using nonexpansive mapping techniques and convex optimization techniques. We then address the problem of optimizing the HOTS score of web pages. We give a scalable algorithm based on a low rank property of the matrix of partial derivatives of the objective function. We report numerical results on a fragment of the web graph.

In this talk we present two web-based tools for researchers in graph theory. First, we show how the system GraPHedron allows to derive new conjectures (interactively or automatically) in extremal graph theory. We will briefly survey some theoretical results obtained with the help of GraPHedron. Then a new database of graphs (House of Graphs) will be introduced. The key principle is to have a searchable database and offer – next to complete lists of some graph classes – also a list of special graphs that already turned out to be interesting and relevant in the study of graph theoretic problems (e.g., as extremal graphs or as counterexamples). To build an initial database, we used GraPHedron to generate and solve a set of problems in an automated way.
(The project House of Graphs is joint work with Gunnar Brinkmann, Kris Coolsaet and Jan Goedgebeur (UGent))

In the last decade, a significant research activity has developed in the context of complex networks, largely motivated by the fact that many systems can be represented by networks, that is to say a set of sites or vertices connected by ties. After a brief introduction to the field of static complex networks, I will turn to the issue of dynamic complex networks by discussing various examples of infrastructure and social networks. In this context, I will moreover present the project SocioPatterns (http://www.sociopatterns.org/), in which we have developed an infrastructure capable of measuring social interactions in real-time in a limited space, such as a conference, offices, a hospital ... and in which we study the corresponding dynamical social networks. I will present some results obtained by the deployment of this infrastructure, which reveal unexpected regularities in social interactions. I will also present a model of social dynamics that reproduces a number of empirically observed facts. I will conclude with prospects offered by the area of dynamic networks.

Life and language are discrete combinatorial systems (DCSs) in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCS can be represented as an Alphabetic Bipartite Network (α-BiN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. There is an edge between a node corresponding to an elementary unit u and a node corresponding to a particular combination v if u is present in v. Naturally, the partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. The evolution equations for α-BiNs under different growth rules are derived, and the corresponding degree distributions computed. It is shown that asymptotically the degree distribution of α-BiNs can be described as a family of beta distributions. The one-mode projections of the α-BiNs and their asymptotics is also studied theoretically and further supported through simulations.

Community finding algorithms for networks have recently been extended to dynamic data. Most of these recent methods aim at exhibiting community partitions from successive graph snapshots and thereafter connecting or smoothing these partitions using clever time-dependent features and sampling techniques. These approaches are nonetheless achieving longitudinal rather than dynamic community detection. We assume that communities are fundamentally defined by the repetition of interactions among a set of nodes over time. According to this definition, analyzing the data by considering successive snapshots induces a significant loss of information: we suggest that it blurs essentially dynamic phenomena --- such as communities based on repeated inter-temporal interactions, nodes switching from a community to another across time, or the possibility that a community survives while its members are being integrally replaced over a longer time period. In this talk, we propose a formalism which aims at tackling this issue in the context of time-directed datasets (such as citation networks), and present several illustrations on both empirical and synthetic dynamic networks. We eventually introduce intrinsically dynamic metrics to qualify temporal community structure and emphasize their possible role as an estimator of the quality of the community detection --- taking into account the fact that various empirical contexts may call for distinct `community' definitions and detection criteria.

Ever since Aristotle, organization and classification have been cornerstones of science. In network science, categorization of nodes into modules with community-detection algorithms has proven indispensable to comprehending the structure of large integrated systems. But in real-world networks, the organization rarely is limited to two levels, and modular descriptions can only provide cross sections of much richer structures. For example, both biological and social systems are often characterized by hierarchical organization with submodules in modules over multiple scales. In many real-world networks, directed and weighted links represent the constraints that the structure of a network places on dynamical processes taking place on this network. Networks thus often represent literal or metaphorical flows: people surfing the web, passengers traveling between airports, ideas spreading between scientists, funds passing between banks, and so on. This flow through a system makes its components interdependent to varying extents. In my talk, I will present our information-theoretic approach to reveal the multiple levels of interdependences between the nodes of a network. I will also present a straightforward generalization to overlapping modules and discuss recent results on efficient modeling of the underlying dynamics on networks.

A gently introduction to the concept of communicability from a combinatorial perspective. We then make some links with the physics of classical and quantum harmonic oscillators. We analyse the use of communicability functions for detecting communities in networks and given some examples of applications. The analysis of self-communicability or subgraph centrality is then motivated and some examples are provided for the study of protein interaction networks. Finally the possibilities of communicability functions for studying brain networks are summarized.

9:30 Registration
10:00 Plenary lecture 1: Prof. Lorenz T. Biegler, Carnegie Mellon University, USA: Direct Transcription Strategies for Dynamic Real-time Optimization,
11:00 Poster session 1
12:15 Plenary lecture 2: Prof. Julien Hendrickx, UCL, Louvain-la-Neuve: TBA
12:45 Lunch
14:00 Plenary lecture 3: Prof. Henk Nijmeijer, T.U.Eindhoven, the Netherlands: The sympathy of pendulum clocks and beyond
15:00 Poster session 2
16:15 1987 - 2011: Michel Gevers and the IAP programme
17:00 End

Collective behavior and social dynamics have recently been studied in many fields of science using methods from statistical physics in order to describe self-organized, emergent phenomena by theoretical models. However an evident lack of empirical studies, especially in the field of collective behaviour of human beings can be observed. The main reason for this is the immanent difficulty to achieve information about the social connections between humans while observing collective processes in traditional experiment settings. Today, the existence of large-scale social online networks for the first time provides the opportunity of large-scale studies on human's collective behavior in consideration of the underlying social network structure. In this regard so-called collaborative social online games based on common social network services can be a useful tool for large-scale empirical studies in the field of social dynamics. Collaborative social online games feature a novel game principle where users do not act as individuals on their own account. Instead, users have to collaborate in large groups of similar entities based on local knowledge and local interaction facilities only. This talk gives an inside to the idea of utilizing collaborative social online games for studies on collective behavior and gives an overview of the ongoing work in this interdisciplinary field at the University of Luxembourg.

The use mathematical physics is today a well accepted framework where model and study social phenomena. After an initial phase relying mostly on qualitative models, scientists begun to obtain quantitative results. The aim of those quite abstract models is mainly to capture universal pattern in human behaviors without carefully adding complicating details that could blind a complete understanding of the assumptions done.

Thanks to the advancements in technology a new phase recently started, where researchers have access to fine measurements about real world interactions. The huge amount of data (internet based applications, mobile networks, face-to-face) is however often associated with a lack for a mathematical foundation of observed emergent properties. Moreover not everything can be measured; to understand why do people "internally" act in such a way as to determine the measured global properties, would necessitate a hierarchical model, whose levels will rang from the "brain level", though the "individual level" to eventually arrive to the "group level". The complexity of such model would be to important to allow us any useful analysis.

In the present paper we try to make a step forward and "measure the unmeasurable" using such kind of data. More precisely, we use recent results of face-to-face contact durations to try to answer the question: why do people engage face-to-face discussions?

Starting from a simple microscopic model we show evidence that measured data, notably supra linear growth of discussion time with respect to the agent connectivity, are compatible with two different scenarios based on the group structure. When the group exhibits clearly identified well reputed people, then the discussion are engaged mainly to just share time with the most reputed person (networking); on the other hand, when the reputation hierarchy is not strong, people discussions are finalized to exchange opinions.

Association networks represent systems of interacting elements, where a link between two different elements indicates a sufficient level of similarity between element attributes. While in reality relational ties between elements can be expected to be based on similarity across multiple attributes, the vast majority of work to date on association networks involves ties defined with respect to only a single attribute. We propose an approach for the inference of multi-attribute association networks from measurements on continuous attribute variables, using canonical correlation and a hypothesis-testing strategy. Within this context, we then study the impact of partial information on multi-attribute network inference and characterization, when only a subset of attributes is available. We examine through a combination of analytical and numerical techniques the implications of the choice and number of node attributes on the ability to detect network links and, more generally, to estimate higher-level network summary statistics, such as node degree, clustering coefficients, and measures of centrality. We consider in detail the case of two attributes and discuss generalization of our findings to more than two attributes. Our work is motivated by and illustrated within the context of gene/protein regulatory networks in human cancer cells. Joint work with Natallia Katenka.

Without having direct access to the information that is being exchanged, traces of information flow can be obtained by looking at temporal sequences of user interactions. These sequences can be represented as causality trees whose statistics result from a complex interplay between the topology of the underlying (social) network and the time correlations among the communications. I will show that causality trees in mobile-phone data can be represented as a dynamical directed network. This representation of the data reveals the existence of super-spreaders and super-receivers. I will show that the tree statistics, respectively the information spreading process, are extremely sensitive to the in-out degree correlation exhibited by the users. Moreover, I would explain that a given information, e.g., a rumor, would require users to retransmit it for more than 30 hours in order to cover a macroscopic fraction of the system. Our analysis indicates that topological node-node correlations of the underlying social network, while allowing the existence of information loops, they also promote information spreading. Temporal correlations, and therefore causality effects, are only visible as local phenomena and during short time scales. These results are obtained through a combination of theory and data analysis techniques.
(work in collaboration with Lionel Tabourier)
http://www.mpipks-dresden.mpg.de/~peruani/

Several infections are transmitted through interactions between individuals. These interactions form contact networks with non-trivial structural and temporal patterns. These patterns affect the propagation of infections and as such, need to be considered to better understand the emergence of epidemics and to control them. In this talk, I first introduce and discuss some properties of a large empirical temporal network of sexual contacts, obtained from a web community related to sexual encounters between sex-buyers and -sellers. Afterwards, I present some results about the simulation of general STIs on this evolving network and discuss how the infection patterns change due to not only the temporal constraints but also due to cluster structures, and finally I present some results about vaccination protocols based on temporal information and discuss their efficiency in diverse networks related to human interaction.