• View
• Edit
• History
• Print

2013-2014

Seminars are usually held on Friday from 11:00 to 12:00 in the main seminar room (Euler Room - A002) of the Building Euler.
If you wish to receive the seminar announcements, please send an email to sympa2@listes.uclouvain.be.
The subject line should be 'subscribe large-graphs-networks yourname' where yourname is your first and last name.

It is well known that resource pooling (or, equivalently, the use of flexible resources that can serve multiple types of requests) significantly improves the performance of service systems. On the other hand, complete resource pooling often results in higher infrastructure (communication and coordination) costs. This leads us to explore the benefits that can be derived by a limited amount of resource pooling, and the question whether a limited amount of pooled resources can deliver most of the benefits of complete resource pooling. Applications in large-scale server farms, skill-based call centers, health care, and flexible supply chains are among our main motivations.

We demonstrate, in the context of some concrete models, that a very small amount of flexibility can be surprisingly powerful in improving performance, both in terms of queueing delay and system capacity. However, to harness the benefits of flexibility, one should carefully architect network topologies, scheduling policies, and how to properly leverage (predictive) information in making dynamic resource allocation decisions. In this talk, I will discuss stochastic models and analytical results that provide interesting insights on these challenges.

The analysis of complex networks has so far revolved mainly around the role of nodes and communities of nodes. However, the dynamics of interconnected systems is often focalized on edge processes, and a dual edge-centric perspective can often prove more natural. Here we present graph-theoretical measures to quantify edge-to-edge relations inspired by the notion of flow redistribution induced by edge failures. Our measures, which are related to the pseudo-inverse of the Laplacian of the network, are global and reveal the dynamical interplay between the edges of a network, including potentially non-local interactions. Our framework also allows us to define the embeddedness of an edge, a measure of how strongly an edge features in the weighted cuts of the network. We showcase the general applicability of our edge-centric framework through analyses of the Iberian power grid, traffic flow in road networks, and the C. elegans neuronal network.

In superpeer based p2p networks, the superpeer nodes are discovered through the process of bootstrapping, whereby resourceful peers get upgraded to superpeers. However, bootstrapping is influenced by several factors like limitation on the maximum number of connections a peer can have due to bandwidth constraints, limitation on the availability of information of existing peers due to cache size constraints and also by the attachment policy of the newly arriving peers to the resourceful peers. In this talk we propose an analytical framework which explains the emergence of superpeer networks on execution of the commercial peer-to-peer bootstrapping protocols by incoming nodes. Bootstrapping protocols exploit physical properties of the online peers like resource content, processing power, storage space, connectivity etc as well as take the finiteness of bandwidth of each online peer into consideration. With the help of rate equations, we show that execution of these protocols results in the emergence of superpeer nodes in the network - the exact degree distribution is evaluated. We also show that the cache parameters must also be suitably tuned so as to increase the fraction of superpeers in the network. We validate the developed framework through extensive simulation. The analysis of the results shows that the amount of superpeers produced in the network depends on the protocol as well as the properties of the joining nodes. As an application study, we show that our framework can explain the topological configuration of commercial Gnutella networks.

Distributed Optimization in a network of autonomous agents is a very popular topic in many communities ranging from machine learning to digital communications. Indeed, processing massive quantities of data scattered in a network often involve solving a global optimization problem (depending on all the data of our network). More precisely, distributed optimization imply a local use of the data and computational resources of each agent combined with information exchanges through the network links in order to reach a consensus over the sought value. After having clearly formulated our optimization problem, we will introduce the monotone operators framework for convex optimization. This formalism will help us design and prove the convergence of a distributed optimization algorithm. Then, we will show how a random activation of well-chosen operators enables us to find a randomized distributed optimization algorithm.

We are interested in estimating the worst-case performance of first-order methods for several classes of convex functions. Our approach relies on the idea originally proposed by [Teboulle and Drori]. that the worst-case performance of an algorithm can itself be formulated as an optimization problem. This optimization problem turns out to be relatively easily solvable for a class of first-order optimization methods. We use the approach to estimate the performance in terms of different measures, like the distance to optimality in the objective space or the residual gradient norm.

In this talk, we consider the problem of computing an approximate solution of a system of linear equations whose matrix of the coefficients is the Laplacian matrix of a graph. Of course, there already exist many solvers that approximate a solution of such systems. However, the tricky point here is finding an algorithm running in nearly linear time. The scope of this talk will be presenting the very recent algorithm presented by Kelner, running in nearly linear time.

Finding communities in complex networks has been an area of intense inquiry for many years. Although there are a plethora of different approaches, one particularly interesting multi-resolution global partition quality function, stability, solves this by introducing a dynamic process onto the network and analysing its behaiour. Here we introduce severability, a local analogue of stability. By pairing together an internal mixing component with an escape measurement, we in some sense measure how good a time-scale separation there is between dynamics on the community vs the network as a whole. By doing this using a purely local (in both space and time) computation, we not only avoid having to consider the entire network, but also permit the presence of overlapping communities. Several toy examples are drawn from image segmentation, metabolic networks, and word association to illustrate the characteristics of this approach.
Work by Y. William Yu, Jean-Charles Delvenne, Mauricio Barahona, Sophia Yaliraki

The linear consensus algorithm has originally been introduced in the context of distributed computation and decision making, where it serves as a network protocol for the exchange of messages among agents embedded in a communication graph. In recent years it has been found at the heart of various models describing the nonlinear dynamics of network systems with applications ranging from multi-machine dynamics in electric power grids to mass action kinetics in molecular networks.


In this talk we take an interconnected dissipative systems view and study the behavior of consensus systems by means of a lossless-memoryless decomposition as known from classical network analysis. Starting from a dissipation inequality, we show that modeling energy and dissipation in network systems involves not only the choice of an appropriate energy function, but also the construction of an appropriate dissipation metric, under which the original dissipation inquality becomes an equality and the chosen energy function a potential in which the system evolves lossless as gradient flow. Then, the chosen energy is related to a coordinate transformation on the lossless system part, and the memoryless part takes the role of a metric tensor acting as controller for the lossless subsystem. It turns out that sum of squares energy functions, or the Laplacian potential of a graph, represent energy with dissipation metric the Euclidean metric. Taking Kullback Leiber information as energy results in a gradient flow with dissipation metric related to logarithmic means of adjacent subsystem states.


The presented results are intimately related to dynamical systems that are contraction maps under Hilbert's projective metric, to Markov chains evolving on finite state space, and to the topic of lossless approximations of dissipative behaviors. Eventually, from the viewpoint we take, it seems that dynamics in molecular networks governed by mass action kinetics, electric power grid dynamics, or Markov chains are just linear consensus algorithms with appropriately chosen dissipation metric.

The activity of modern scholarship leaves plenty footprints in the online world, and Wikipedia, the world's biggest peer-produced encyclopedia, is not an exception. Hundreds of Wikipedia articles cover academic institutions and researchers themselves, shaping online image and public understanding of modern scholarship. Only the researchers of proved 'high academic notability' can be featured in the encyclopedia, as required by Wikipedia notability guidelines. It is one of the reasons why the researchers who have biographical articles on Wikipedia are generally considered to be of higher academic importance than those who are not featured there. In this talk, I discuss (1) whether Wikipedia presence correlates with higher notability of researchers; (2) whether truly notable researchers are likely to be covered by the encyclopedia, and (3) if Wikipedia can be used as an early indicator or proxy of academic impact for decisions such as funding and promotion.

Seriation seeks to reconstruct a linear order between variables using unsorted similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We prove the equivalence between the seriation and the combinatorial 2-sum problem (a quadratic minimization problem over permutations) over a class of similarity matrices. The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we produce a convex relaxation for the 2-sum problem to improve the robustness of solutions in a noisy setting. This relaxation also allows us to impose additional structural constraints on the solution, to solve semi-supervised seriation problems. We present numerical experiments on archeological data, Markov chains and gene sequences.

The view of depth k of a node is a tree containing all the walks of length k leaving that node. Views contain all the information that nodes could obtain by exchanging messages with their neighbors. In particular, a value can be computed by a node on a network using a distributed deterministic algorithm if and only if that value only depends on the node's view of the network. Norris has proved that if two nodes have the same view of depth n-1, they have the same views for all depths. Taking the diameter d into account, we prove a new bound in O(d+d\log(n/d)) instead of n-1 for bidirectional graphs with port numbering, which are natural models in distributed computation.
This automatically improves various results relying on Norris's bound. We also provide a bound that is stronger for certain colored graphs.

In this talk we analyze a voting model based on random preferences of the participants. Each voter can choose a party with certain probability, which depends on divergence between his preferences and the position of the party. Our model represents a rare example of a community detection model with unique equilibrium solution. This is achieved by allowing the flexible positions for the parties. We propose an efficient algorithm for finding the equilibrium state.

Stability is the most fundamental requirement placed on any control systems. This talk will explore the stability theory of switched linear systems, which are dynamical systems whose structure experiences abrupt changes but remains to be linear. Recent results on their stability analysis and Lyapunov theory will be presented. Their relationship with joint spectral characteristics will be discussed.

Given a linear recurrence sequence over the reals, the Positivity Problem asks whether the terms of the sequence are all positive, while the Ultimate Positivity Problem asks whether all but finitely many terms of the sequence are positive. These problems have applications in theoretical biology, software verification, quantitative automata, combinatorics, term rewriting, and the study of generating functions.
The decidability of Positivity and Ultimate Positivity for rational linear recurrence sequences is a long-standing open problem. In this talk we summarise some of our recent work in the area. We show that Positivity and Ultimate Positivity are decidable for linear recurrence sequences of order 5; obtaining decidability for either problem for sequences of order 6 would entail major breakthroughs in the field of Diophantine approximation of transcendental numbers; for simple linear recurrence sequences, i.e., those with no repeated characteristic roots, Ultimate Positivity is decidable at all orders.

(1)In this talk, I will present the notion of minimum rank of a loop directed graph, namely a directed graph allowing loops. In order to study the minimum rank of such a graph, many graph parameters have been introduced. One of them is the zero forcing number, providing a lower bound on the minimum rank. In my presentation, I will talk on the one hand about the NP-hardness of the computation of this parameter and its connection with the constraint matchings in a bipartite graph and, on the other hand about some algorithms for the computation of the zero forcing number of a loop directed tree.


(2) In genetic, a more an more used tool is DNA microarrays, that measure the expression levels of large numbers of genes simultaneously. A big challenge in analysing those datasets comes from their dimension, typically about a few (tens of) thousands variables for at best a few hundred samples. The goal pursued here is to discover clusters of genes behaving together (or pathways) in order to better understand interaction between genes. A possible approach is to factorise the data matrix in a product of two matrices of smaller rank.

This talk generalizes the dynamics behind consensus algorithms towards a procedure to symmetrize the actions of a finite group. After introducing the theoretical framework, most of the talk will review its various applications that range from extended agreement problems, through uniform random state generation, and a Fourier transform, to open-loop disturbance rejection techniques.

We examine the Laplacian spectrum of temporal networks to be compared with that of the corresponding aggregate networks. We show by analytical arguments that the Laplacian eigenvalues are smaller (i.e., closer to zero) for temporal than aggregate networks for different scenarios of temporal network realizations derived from the same aggregate network. Therefore, diffusive dynamics is slower in temporal than aggregate networks. We illustrate our analytical results with some model and real networks. This work has been done in collaboration with Konstantin Klemm and Victor M. Eguiluz.