
Seminars /
20132014Seminars are usually held on Friday from 11:00 to 12:00 in the main seminar room (Euler Room  A002) of the Building Euler. Monday June 30, 2014, 11:00 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 largescale server farms, skillbased call centers, health care, and flexible supply chains are among our main motivations. Monday June 16, 2014, 15:00 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 edgecentric perspective can often prove more natural. Here we present graphtheoretical measures to quantify edgetoedge relations inspired by the notion of flow redistribution induced by edge failures. Our measures, which are related to the pseudoinverse of the Laplacian of the network, are global and reveal the dynamical interplay between the edges of a network, including potentially nonlocal 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 edgecentric framework through analyses of the Iberian power grid, traffic flow in road networks, and the C. elegans neuronal network.
Tuesday June 10, 2014, 11:00 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 peertopeer 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. April 28, 2014, 11:00 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 wellchosen operators enables us to find a randomized distributed optimization algorithm. April 2, 2014, 11:00 We are interested in estimating the worstcase performance of firstorder methods for several classes of convex functions. Our approach relies on the idea originally proposed by [Teboulle and Drori]. that the worstcase 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 firstorder 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. Mon March 17, 2014, 11:00 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. Mon March 10, 2014, 14:00 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 multiresolution 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 timescale 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. Thu March 6, 2014, 11:00 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 multimachine dynamics in electric power grids to mass action kinetics in molecular networks. February 19, 2014, 11:00 (Nyquist room, Maxwell Building a.164) The activity of modern scholarship leaves plenty footprints in the online world, and Wikipedia, the world's biggest peerproduced 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. February 14, 2014, 11:00 (Nyquist room, Maxwell Building a.164) 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 2sum 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 2sum 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 semisupervised seriation problems. We present numerical experiments on archeological data, Markov chains and gene sequences. January 31, 2013, 11:00 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 n1, 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 n1 for bidirectional graphs with port numbering, which are natural models in distributed computation. December 6, 2013, 11:00 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. November 15, 2013, 11:00 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. October 30, 2013, 11:00 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. October 25, 2013, 11:00
Double seminar (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 NPhardness 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.
October 18, 2013, 11:00 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 openloop disturbance rejection techniques. September 23, 2013, 11:00 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. 