• View
• Edit
• History
• Print

2005-2006

http://www.core.ucl.ac.be/staff/glineur.html

In this talk, we will briefly outline two algebraic techniques applicable to the resolution of systems of polynomial equations and the minimization of multivariate polynomials. The first one is based on a generalization of the companion matrix for univariate polynomials to the case of multiple variables. The second technique relies on the decomposition of polynomials into sums of squares and its formulation as a convex (semidefinite) optimization problem."

PDF slides?.

In this work, we present a model that integrates both exploration and exploitation in a common framework. First of all, we define the concept of degree of exploration from a state as the entropy of the probability distribution on the set of admissible actions in this state. This entropy value allows to control the degree of exploration linked to this state, and should be provided by the user. Then, we restate the exploration/exploitation problem as a global optimization problem : define the best exploration strategy that minimizes the expected cumulated cost, while maintaining fixed degrees of exploration. This formulation leads to a set of nonlinear updating rules reminiscent from the “value iteration” algorithm. Interestingly enough, when the degree of exploration is zero for all states (no exploration), these equations reduce to Bellman’s equations for finding the shortest path while, when it is maximum, a full “blind” exploration is performed. We further show that if the graph of states is directed and acyclic, the nonlinear equations can easily be solved by performing a single backward pass from the destination state. The theoretical results are confirmed by simple simulations showing that the model behaves as expected.

http://www.inma.ucl.ac.be/~hendrickx Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the context of moving autonomous agent formations, persistence characterizes the efficacy of a directed structure of unilateral distances constraints seeking to preserve a formation shape. We first review the definition and main properties of rigidity using a linear algebraic formalism. We then provide an alternative definition of persistence, based on the same linear algebraic concepts and some elements of game theory. This new formulation, simpler than the equivalent one provided in [1,2], allows us to prove some of the main properties of persistence in a shorter way.

[1] Julien M. Hendrickx, Brian D.O. Anderson, Jean-Charles Delvenne and Vincent D. Blondel, *Directed graphs for the analysis of rigidity and persistence in autonomous agents systems, *To appear in: International journal of robust and nonlinear control
[2] Changbin Yu, Julien M. Hendrickx, Baris Fidan, Brian D. O. Anderson, Vincent D. Blondel, *Three and higher dimensional autonomous formations: rigidity, persistence and structural persistence. *To appear in: Automatica

We will derive new bounds for the GMRES method of Saad and Schultz, for solving linear systems. We will first give a simple formula for the norm of the residual of GMRES based only on the Krylov matrix. This formula allows us to generalize the well known result on the convergence behavior of GMRES when the matrix has a full set of eigenvectors. The explicit formula of the residual norm of the GMRES when applied to a normal matrix, which is a rational function, is given in terms of eigenvalues and of the components of the eigenvector decomposition of the initial residual. By minimizing this rational function over a convex subset, we obtain the sharp bound of the residual norm of the GMRES method applied to normal matrices, even if the spectrum contains complex eigenvalues. Hence we completely characterize the worst case GMRES for normal matrices. We use techniques from constrained optimization rather than solving the classical min-max problem (problem in polynomial approximation theory).

http://www.inma.ucl.ac.be/~dekerch,
http://www.inma.ucl.ac.be/~ninove

http://www.fundp.ac.be/universite/personnes/page_view/01001721/,

Je voudrais soulever quelques questions relatives a la possibilite et aux difficultes de la mise en evidence de fonctions specifiquement biologiques a partir de graphes decrivant des "interactomes" (genome, proteome, glycome,;...). Je montrerai que les analyse en termes de modularite sont insuffisantes et demandent a etre completees par des analyses qui tiennent compte d'une "dynamique".

http://www.inma.ucl.ac.be/~jungers

We present the theory of trackability of a target on a sensor network. We show how a natural formulation of this problematic involves the computation of a joint spectral radius. We then present the joint spectral radius and some new results about it. references :
-The Theory of Trackability with Applications to Sensor Networks, Dartmouth Computer Science Technical Report TR2005-555, August 2005
-Vincent D. Blondel and John N. Tsitsiklis.A survey of computational complexity results in systems and control. emph{Automatica}, 36(9):1249-1274, 2000.
-J. Tsitsiklis, V. Blondel, The Lyapunov exponent and joint spectral radius ofpairs of matrices are hard -- when not impossible -- to compute and to approximate, Mathematics of Control, Signals, and Systems, 10, pp. 31-40, 1997. (Correction in 10, pp. 381, 1997)

The problem of distributions of random power series was studied by many authors and found applications in various problems of mathematics. One special case known as Bernuolli convolutions leads to the famous Erdos problem, which is still unsolved. In 1995 Derfel, Dyn and Levin considered another special case, in some sense "dual" to the Erdos problem. They obtained some sufficient conditions for the existence of density of a random series. We present a complete criterion showing that the roots of the characteristic function have to form special subsets on a binary tree. This allows us to characterize all possible cases of the criterion in terms of binary trees.

http://www.inma.ucl.ac.be/~dekerch

I will mainly present the paper of J. Kleinberg et al. "Maximizing the Spread of Influence through a Social Network". They propose several models for the processes by which ideas and influence propagate through a social network. Then the following algorithmic problem is posed: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large scale of cascade of furtheradoptions, which set of individuals should we target?

(ppt file)?

http://www.inma.ucl.ac.be/~vdooren

Abstract (pdf file)?

http://www.inma.ucl.ac.be/~delvenne

We present a new pagerank algorithm on large graphs based on Ruelle's "thermodynamic formalism". We make a comparison with the classical pagerank and with Kleinberg's HITS method. We point out possible applications to graph clustering. synthesis. (ps file)?

http://www.inma.ucl.ac.be/~dekerech

This talk gives an overview of the analysis of a real large phone calls networks. In those networks, nodes are handsets and connections are calls, moreover its connections change over time and each node has some evolving state. Such a network has several interesting properties that will be discussed like its Scale Free shape and the dynamicity of the states. The main part will concern the identification of influent nodes in the spread of technology. These nodes are called the leaders, and we use the background of the mathematical theory of infectious diseases to describe the process. Three methods will be exposed: first the algorithm of S. Brin and L. Page used by google for its Page Rank, second an algorithm based on similarity between two graphs, and third the definition of Social Leader. Eventually, some results will conclude the presentation.

http://www.inma.ucl.ac.be/~ho

We present a method to approximate a non-negative matrix A by a low-rank product UV whose factors U and V are also non-negative. This kind of approximation is useful in applications such as face learning and recognition, and in clustering of non-negative data. In particular, we will focus on the application of this method to the problem of Graph Clustering where vertices of a graph are to be grouped into clusters with high connectivity within each cluster and low connectivity across clusters. We present some promising results and mention some open problems.

http://www.ba.cnr.it/~irmanm21/Welcome.html,
http://www.iac.rm.cnr.it/

Semiseparable matrices are matrices whose submatrices below (above) the main diagonal have low rank with respect to the size of the matrix. This talk will be focused on the exploitation of the latter structure to design fast algorithms to solve linear systems, to compute the eigendecomposition in problems involving such matrices. In particular, new algorithms for computing the roots of polynomials exploiting the semiseparable structure of the companion matrix will be described.

PDF Slides?.

Most of the important graph problems just like graph isomorphism, connectivity, graph coloring, graph partitions, graph drawing play important role in theoretical and practical worlds of graphs and till now we do not have a polynomial algorithms for these problems. Spectral methods give good approximations for such problems and in practice they are one of the most used methods. I shall try to give a brief survey about eigenvalue and eigenvectors methods in (algebraic) graphs theory and give some (counter)examples, when these methods don't work.

http://www.inma.ucl.ac.be/~ninove

We present a variant of the PageRank algorithm [Brin and Page 1998]. Our method considers an enlightened random walk on the graph of the web for ranking webpages. After presenting the model, some intuitive justification and mathematical developments, we will compare our EnlightRank with the usual PageRank on a real example.

http://www.anu.edu.au/

This presentation will demonstrate the use of Rigid Graph Theory in applications such as Autonomous Multiagent Formation Control. In many control scenarios, when formations of agents move in the plane or in three-dimensional space, the shape of the formation needs to be maintained. This part of talk introduces the use of rigidity ideas to ensure retention of the formation shape, with a focus on identifying the minimum number of inter-agent constraints that need to be fulfilled. Change of formation due to splitting, merging, or closing ranks (following the loss of one or more agents) is also considered. The topics will be further investigated with the use of Directed Graphs to model the Leader-Follower type of control structure. This inspired us to develop a framework to analyse this problem with notions of persistence and structural persistence. The latter will be an emphasis of the first part of the presentation. The second part of the presentation will briefly introduce recent results on (minimally) rigid formation merging and point out questions that is currently or will be investigated. The contents of the work will be based on existing literature, works at National ICT Australia and The Australian National University, and collaboration works with researchers at Yale University and UCL, Belgium. The first part of the talk (on structural persistence of formations) was recently presented in the MARS05 workshop in Barcelona on 13th Sep 2005.