• View
• Edit
• History
• Print

2007-2008

The presentation has two parts, the first one is application oriented and motivates the second part which is more theory oriented.

First, we briefly investigate stochastic resource allocation problems with scarce, reusable resources and non-preemtive, time-dependent, interconnected tasks. We provide reactive solutions of them by applying reinforcement learning (RL) and other machine learning techniques. The effectiveness of our system is demonstrated by results of simulation experiments on both benchmark and industry-related data. We also argue that this kind of approach can handle disturbances and work in changing environments, as well.

Then, we investigate the possibility of applying RL methods in cases when the environment may change over time. First, theorems are presented which show that the optimal value function of a discounted Markov decision process (MDP) Lipschitz continuously depends on the immediate-cost function and the transition-probability function. Dependence on the discount factor is also analyzed and shown to be non-Lipschitz. Afterwards, the concept of (epsilon, delta)-MDPs is introduced, which is a generalization of MDPs and epsilon-MDPs. In this model the transition function and the cost function may vary from time to time, but the changes must be asymptotically bounded. Finally, learning in changing environments is analyzed. A general relaxed convergence theorem for stochastic iterative algorithms is presented and illustrated by classical RL methods as well as numerical experiments.

Financial markets are examples of very interesting large complex systems. The availability of reliable high frequency data of stock markets gives the possibility to study market mechanisms in detail and connect microscopic dynamics to macroscopic measurables and understand the role of human behaviour. In my talk I first review some studies made on the cross-correlation properties between price changes of stocks. I study equal time and lagged correlations and show that some of the properties can be explained by the tendency of the markets to become more and more efficient, while other properties can be attributed to the human time scale of information spreading. In the second part of the talk I show results on the dynamics of order placement (to buy or sell) of liquid stocks on the London Stock Exchange (LSE) after experiencing a large intra-day price change. I discuss the changes around large events and the relaxation properties of several measurables, finding generally a slow decay to normal values. With the help of a zero-intelligence multi-agent model I simulate the order placement, and show that some of the dynamics can be reproduced without assuming complicated behavioural concepts of traders.

There has been much recent interest in effective methods to compute Nash or correlated equilibria for finite games. In this talk we present an overview of some of our recent results for the computation of equilibria in games where the players have an infinite number of pure strategies. In particular, we discuss games where the payoff functions are a polynomial expression of the actions of the players. In the zero-sum case, we show that the value of the game, and the corresponding optimal mixed strategies, can be computed by solving a single semidefinite programming problem, thus providing a natural generalization of the well-known LP characterization of finite games. We also discuss some further extensions to the general nonzero sum case, for both Nash and correlated equilibria. Much of the material is joint work with Asu Ozdaglar and Noah Stein.

A cellular automaton is a synchronous parallel computing model, which consists in a juxtaposition of finite state automata (cells) whose state changes over time according to that of their neighbors. Despite the simplicity of this local evolution rule, the overall behavior that appears in the evolution of a population of cells can be very complex. Given a cellular automaton, we can associate to it a language, which is the set of sequences of states that can be taken by a given cell. This language is directly linked to the cellular automaton, since reading a letter forward in the trace corresponds to applying an evolution step in the automaton. The trace subshift is the set of infinite words which finite factors are in this language. We prove the undecidability of a rather large class of problems over trace subshifts of cellular automata.

We consider a one-round two-player network pricing game, the {em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most $ min {k,3+2ln b,1+ln W}$ , where $ k$ is the number of distinct red costs, $ b$ is the number of blue edges, and $ W$ is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm.

Social bookmarking systems allow users to organize and share bookmarks, photos, etc. on the web. The reason for the success of these systems lies mainly in the fact that no specific skills are needed for publishing and editing. As these systems grow larger, however, the users feel the need for more structure for better organizing their resources. This poses new challenges for the research areas of information retrieval and knowledge discovery. The underlying data structure of social bookmarking systems are so-called folksonomies, which can be considered as tri-partite hyper-graphs. One approach is thus to transfer existing graph algorithms to this new kind of structure.

In the talk, I will first present our social bookmarking system BibSonomy <http://www.bibsonomy.org/>, which supports the scientific community in organizing and sharing bookmarks and lists of publication references; and which serves as a platform for our experiments with Information Retrieval and Knowledge Discovery algorithms. In the second part of the talk, I will present selected research results.

I introduces a novel iterative method that assigns a reputation to $ n+m$ items: n raters and m objects. Each rater evaluates a subset of objects leading to a nxm evaluation matrix with a certain sparsity pattern. From this evaluation matrix we give a nonlinear formula to define the reputation of raters and objects. I also provide an iterative algorithm that superlinearly converges to the unique vector of reputations and this for any evaluation matrix. In contrast to classical outliers detection, no evaluation is discarded in this method but each one is taken into account with different weights for the reputation of the objects. The complexity of one iteration step is linear in the number of evaluations, making our algorithm efficient for large data set. Experiments show good robustness of the reputation of the objects against cheaters and spammers and good detection properties of cheaters and spammers.

Some integrated models for ranking scientific publications together with authors and journals are presented and analyzed. The models rely on certain adiacency matrices obtained from the relations of citation, authorship and publication, which concurr to forming a suitable irreducible stochastic matrix whose Perron vector provides the ranking. Some perturbation theorems concerning the Perron vector of nonnegative irreducible matrices are proved. These theoretical results provide a validation of the consistency and effectiveness of our models. Several paradigmatic examples are reported together with some results obtained on a real set of data.

The use of WiFi routers is becoming close to mainstream in the US and Europe, with 8.4% and 7.9% of all such respective households having deployed such routers by 2006, and a WiFi market expected to grow quickly in the next few years as more new digital home devices are being shipped with WiFi technology. As the WiFi deployment becomes more and more pervasive, the larger is the risk that massive attacks exploiting the WiFi security weaknesses could affect large numbers of users. Indeed, many WiFi security threats have been downplayed based on the belief that the physical proximity needed for the potential attack to occur would represent an obstacle for attackers. The presence nowadays of large ad-hoc networks of routers make these vulnerabilities considerably more risky than previously believed. In this talk, I will consider the ability of malware to propagate from wireless router to wireless router over the wireless channel, infecting large urban areas where such routers are deployed relatively densely. Introducing an SIR epidemiological model, in analogy with biological epidemics, I will present simulations of the contagion process on real-world data for geo-referenced wireless routers. Worrisome scenarios and suggestions to minimize the threat will be presented and discussed.

More information is available at http://www.inma.ucl.ac.be/~blondel/workshops/2008/

Low rank matrix factorizations are used widely in statistical data analysis. In Nonnegative Matrix Factorization (NMF), a (nonnegative) mixed m-by-n data matrix X is approximately factored into a product of two nonnegative rank k matrices, with k small compared to m and n. This factorization has the advantage of providing a physically realizable representation of the mixed data. NMF is widely used in a variety of applications, including air emission control, image and spectral data processing, text mining, chemometric analysis, neural learning processes, sound recognition, remote sensing, and object characterization. Nonnegative Tensor Factorization (NTF) is a natural extension of NMF to higher dimensional data. In NTF high-dimensional data, such as hyperspectral or related data sets, can be approximated by a sum of rank 1 nonnegative tensors. We show how these methods can be used effectively to solve problems in space situational awareness, in particular for space object identification by spectral unmixing. The work is funded by the AFOSR.

Les ensembles d'entiers $ p$ -reconnaissables (reconnus par automates finis) ont été largement étudiés depuis le début des années 1970. Dans l'optique de généraliser les résultats classiques concernant ces ensembles d'entiers, on s'interesse à des ensembles d'entiers reconnus par des automates dénombrables, dit $ p^infty$ -reconnaissables. Cet exposé presente un panorama des résultats obtenu concernant ces ensembles. En pratique, nous présenterons deux notions de reconnaissabilité par automates dénombrables ainsi que certaines propriétés et les limites de ces notions. D'autre part, nous nous interesserons aux propriétés combinatoires des mots infinis caractéristiques de certains de ces ensembles.

The road coloring conjecture has been one of the most longstanding and popular open problems in graph theory for the last decades. In 1977, Adler, Goodwin and Weiss conjectured that an acyclic k-regular strongly connected graph can always be colored (with k colors) in such a way that the obtained automaton (colored graph) is synchronizing [1]. (A graph is synchronizing if there exists a color sequence such that any path of this color leads to the same vertex). The conjecture has been proved in several particular cases, and has led to interesting theoretical developments during the last 30 years. Nevertheless, it has been open until very recently. In September 2007, A.N. Trahtman proposed a proof for the conjecture [2]. It is an interesting fact that the proof is (almost) self contained, and the main ideas are rather simple and elegant. During this informal seminar, we plan to expose these main ideas.

[1] R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel J. of Math. 27(1977), 49-63.
[2] A.N. Trahtman. The road coloring problem, Israel J. of Math., accepted. Available on arxiv: http://arxiv.org/abs/0709.0099

Organization of the next 6 months for the Large graphs group, by Vincent.

This talk describes novel methods for extracting a subgraph that best captures the relationships between K given nodes of interest in a graph. We introduce a betweenness measure based on random walks connecting distinct nodes of interest. Expected node and edge passage times along these walks can be efficiently computed. These quantities, which are defined here relatively to the choice of seed nodes, overcome limitations of shortest paths or maximal flow approaches. The proposed technique applies both to directed or undirected connected graphs.

The main contribution of this work is a fast computation of the expected edge and node passage times along all possible walks up to a prescribed length L. We propose a novel algorithm for computing these walks with a time complexity linear in K, L and the graph order. We also measure how well this algorithm approximates walks of any length.

Practical experiments on large artificial graphs and real metabolic networks from the KEGG LIGAND database are presented. A demonstration of a Cytoscape plug-in implementing this technique concludes the talk. This plug-in offers a convenient and efficient visualization of large biochemical networks.

Slides?

More information is available here?

We shall consider several undecidable problems in finitely generated matrix semigroups over different number systems. We shall explore some new undecidable properties arising from studying the structure of semigroups such as vector ambiguity, recurrent matrix problems, determining whether any matrix in a semigroup is diagonal and undecidability for matrix equations.

We shall also present two versions of Post's correspondence problem, named "Index Coding PCP" and "Fixed Element PCP", which we developed in connection with several of the undecidability proofs above.

Detecting communities in networks is crucial to uncover relationships between nodes of complex networks. In spite of the sizeable literature on the topic, the elements of the problem are not clearly defined. I discuss the three main aspects of the problem, which in some respect still pose a challenge to scholars: the definition(s) of community, the evaluation of partitions and the issue of hierarchies.

Joint seminar with the Cesame seminar

In the last years, several models have been introduced in order to model the way opinions diffuse in society and consensus is (or not) reached. In this talk, I'll first focus on the Voter model and on the Vacillating Voter model [1] and show that their features may be radically different depending on the underlying topology, i.e. the social network, on which the dynamics takes place. I will also focus on the Majority Rule and the Unanimity Rule [2], and discuss in detail the role played by the degree heterogeneity [3] and the presence of communities [4,5] in the network.

[1] R. Lambiotte and S. Redner, arxiv:0710.0914
[2] R. Lambiotte, S. Thurner and R. Hanel, Phys. Rev. E 76, 046101 2007
[3] R. Lambiotte, Europhys. Lett. 78, 68002 2007.
[4] R. Lambiotte, M. Ausloos, and J. A. Hołyst, Phys. Rev. E 75, 030101R 2007
[5] R. Lambiotte and M. Ausloos, J. Stat. Mech.: Theory Exp. , P08026 2007

Consider agents that discuss about a certain issue which can be expressed as a real number. If an agent gets aware of the opinions of other agents and trusts them she adjusts her opinion by building a weighted average. If agents have bounded confidence, they only trust agents which differ in opinion not more than a certain bound of confidence.

The most prominent models of continuous opinion dynamics under bounded confidence are the model of Hegselmann and Krause and the model of Deffuant, Weisbuch and others. They differ in their communication regime and can be seen as communication protocols, where the communication topology switches dynamically depending an the actual states of the nodes. We discuss, to what extend results about consensus protocols are applicable for these models.

Starting with a large enough number of agents with random initial opinions the process converges to a characterisic stable distribution of opinions in opinion clusters with respect to number, size and location of clusters. This characteristic cluster pattern changes drastically at certain critical values of the bound of confidence. This can be displayed in bifurcation diagrams, which can be computed numerically after reformulation of dynamics on the agent's density. An analytic description of critical bounds of confidence is still lacking. Even a proof of convergence for the density-based model versions is still lacking.

One specific critical bound of confidence is where the consensus transition appears. If confidence is higher a vast majority of agents finds consensus while for lower bounds of confidence they split into two equally sized clusters. The critical bound for the consensus transition can be significantly affected by dimensionality and shape of the opinion space. Counter-intuitive effects occur, when heterogeneous bounds of confidence are allowed. Some phenomena will be presented.

This is a 3 hours graduate course organized by the Computational Intelligence and Learning Doctoral School. For more details, please consult http://www.uclouvain.be/doctoralschool-cil/

Given a subset S of N, filtering a word a0a1 ... an by S consists in deleting the letters ai such that i is not in S. By a natural generalization, denote by L[S], where L is a language, the set of all words of L filtered by S. The filtering problem is to characterize the filters S such that, for every recognizable language L, L[S] is recognizable. In this paper, the filtering problem is solved, and a unified approach is provided to solve similar questions, including the removal problem considered by Seiferas and McNaughton. There are two main ingredients on our approach: the first one is the notion of residually ultimately periodic sequences, and the second one is the notion of representable transductions.

The Self Organizing Map is an interesting interactive data mining tool as it provides both a nonlinear projection and a clustering of a dataset. The standard formulation of SOM is limited to vector data but variants have been proposed for arbitrary data via the kernel trick. We present in this talk one of this variant, the batch kernel SOM. We show how it can be used to cluster and visualize at the same time the vertices of a graph via heat kernels derived from the Laplacian of the graph. This method is applied to a medieval social network built from agrarian contracts.

Research in collaboration with Nathalie Villa (Institut de Mathématiques de Toulouse)

The ubiquity of mobile phones provides an unprecedented opportunity to collect enormous amounts of quantitative data on one-to-one human communications. Based on such data, we have reconstructed a very large weighted social network, where the link weights depict communication frequencies and are thus related to the strength of social ties. We analyze the global and local structural properties of this society-wide communication network, and observe that the link weights are coupled to the topology: the network structure is seen to be compatible with the weak ties hypothesis, i.e. communities with strong internal connections are connected to other communities through weak links. We probe this weight-topology coupling by removing links according to different thresholding schemes, and analyze its consequences on the diffusion of information.

Slides?

In real-world networks, nodes often group themselves into dense clusters, giving the whole graph a highly modular topology. We introduce a constructive model for generating realistic, community-rich graphs. The construction rule relies on two key concepts: preferential attachment and self-similarity. We then derive a conceptually related algorithm for community detection. A simplified version of the algorithm, searching for modularity maximizing partitions, is finally presented.

Based on the equations of the Kuramoto model of interacting oscillators, a dynamical model of mutually attracting agents is introduced for which the long term behavior results in the formation of several groups or clusters. The cluster structure is completely characterized by a set of inequalities in the parameters of the model, and the clustering behavior is similar to the behavior of the Kuramoto model.

The clustering model is related to compartmental systems, and using this relation we can derive a solution for the minimum cost flow problem (with strictly convex cost functions) as an implementation by (a modified version of) this model, for well-chosen interaction functions.

We consider linear switched systems of the form $ dot x=A(t) x$ , where $ A(.)$ is a (arbitrary) measurable function with values on a compact set of Hurwitz matrices. For this kind of systems we are interested on the notion of exponential stability of the origin, uniform with respect to $ A(.)$ . In particular we show that the uniform exponential stability is equivalent to the existence of a common polynomial Lyapunov function. On the other hand we prove that, unlikely the case of stable ordinary linear systems, in the case of switched systems it is not possible to give a uniform lower bound to the degree of the polynomial Lyapunov function.

http://ccp2007.ulb.ac.be/

Depuis leur création, certains systèmes pair-à-pair ont d'abord proposé de connecter leurs utilisateurs en une structure afin de faciliter la rechercher et de les rendre rapide. D'autres ont proposé de ne pas imposer de voisins spécifiques aux utilisateurs, utilisant ainsi les lois de puissance et les communautés naturellement présente dans les échanges. Nous allons vois ici un tour d'horizons de ces différents systèmes puis je proposerais des méthodes pour obtenir de bons résultats dans chacune de ces deux catégories.