• View
• Edit
• History
• Print

2006-2007

This talk is on maintenance of formation geometries of a class of autonomous multi-agent systems moving in formation, namely persistent formations, using decentralized switching control schemes. In a persistent formation, the formation shape is maintained during any continuous motion via a set of constraints on each agent to keep its distances from a pre-specified group of other neighboring agents constant. The talk consists of several cohesive motion control problems for persistent autonomous formations. The aim in the first two of these problems is designing distributed control schemes for moving a given persistent formation with specified initial position and orientation to arbitrary desired final position and orientation without deforming the shape of the formation during the motion, one for obstacle-free environments and the other for regions with obstacles. The third problem is on obstacle avoidance and rendezvous of a team of three unmanned aerial vehicles (UAVs) around a common target. In the fourth problem, a similar team of three UAVs is required to survey a region of interest in formation following a specified path. The last problem investigated using switching control approaches is acquisition/maintenance of desired inter-agent distances for non-hierarchical autonomous multi-agent platoons using a decentralized scheme in the existence of measurement noises, which cause instability problems when classical controllers are used.

Speeding up approximate pattern matching is a line of research in stringology since the 80’s. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are excluded (filtered out) in a first step, and remaining regions are compared to the pattern by dynamic programming in a second step. Among the necessary conditions used to test similarity between the regions and the pattern, many require a minimum number of common substrings between them. When only substitutions are taken into account for measuring dissimilarity, it was shown recently that counting spaced subwords instead of substrings improve the filtration efficiency. However, a preprocessing step is required to design one or more patterns, called gapped seeds, for the subwords, depending on the search parameters. The seed design problems proposed up to now differ by the way the similarities to detect are given: either a set of similarities is given in extenso (this is a “region specific” problem), or one wishes to detect all similar regions having at most k substitutions (general detection problem). Several articles exhibit exponential algorithms for these problems. In my talk, I will present hardness and inapproximability results for both the region specific and general seed design problems, thereby justifying the exponential complexity of known algorithms.

Data mining, and graph mining in particular, is a hot topic both in the academic world and in the industry. Many machine learning methods can be used to tackle data mining tasks; they are however seldom adapated for graph data and rather aimed at spreadsheet-like data. In this talk, the field of machine learning will be brievely presented, and in particular, a short introduction to support vector machines will be given. The talk will also focus on how these methods can be used in a business environement and how the University can value its research through spin-off companies. Finally, the links between machine learning and graph theory are discussed; paths for future research are evoked.

In this talk, we will consider two particular problems of directed graph matching. The first problem concerns graphs with nodes that have been subdivided into classes of different type. The second problem treats graphs with edges of different types. In the two cases, the matching process is based on a constrained projection of the nodes and of the edges of both graphs in a lower dimensional space. The methods are formulated as non-convex optimization problems where the objective functions use the adjacency matrices and the constraints impose the isometry of the so-called projections. Iterative algorithms are proposed to solve the optimization problems. As illustration, we will give examples of graph matching for graphs with two types of nodes and graphs with two types of edges.

Many real networks, like social networks, are inhomogeneous and contain groups which are very dense while only sparsely connected to the other groups. The detection of such subgraphs or communities has received a lot of attention in the last few years, attention related to the amount of studies around complex networks, but also to the fact that the main parameter used to evaluate the quality of a partition into communities is hard to maximize. During this talk I will present the main approaches introduced recently, which are either divisive or agglomerative. Divisive approaches are trying to remove inter-community links to leave a set of disconnected subgraphs, while agglomerative ones are trying to identify similar nodes in the network to cluster them and iteratively to group small communities into larger ones.

PDF Slides?.

• Social networks are known to differ from other types of networks due to their high clustering coefficient and their assortative correlations between the degrees of adjacent nodes. We introduce a model where the social network grows with copying mechanisms, i.e. where people discover new friends by copying those of their friends. The model, made as simple as possible, allows to analytically predict the behaviour of the degree distribution, the non-vanishing values of the clustering coefficient and of the assortativity parameter r, as well as the small-world diameter of the network. The role of node ageing (physics/0701157) and of link redirection (physics/0612148) is also discussed.
• We focus on an opinion formation-like model (majority model) on different topologies. First, the case of networks with communities (physics/0612146) is considered. It is shown that situations where the communities reach different opinions is possible only if the separation between the communities is large enough. We also focus on "dichotomous networks" in order to show the role played by the degree distribution on the average behaviour of the nodes.

We consider a simple dynamical model of agents distributed on the real line. The agents have a limited vision range and they synchronously update their positions by moving to the average position of the agents that are within their vision range. This dynamical model was initially introduced in the social science literature as an opinion dynamic model and is known there as the “Krause model”. The model gives rise to surprising and partly unexplained dynamics that we describe and discuss. One of the central observations is the 2R-conjecture: when sufficiently many agents are distributed on the real line and have their position evolve according to the above dynamics, the agents eventually merge into clusters that have inter-cluster distances roughly equal to 2R (R is the vision range of the agents). This observation is supported by extensive numerical evidence and is robust under various modifications of the model. It is easy to see that clusters need to be separated by at least R. On the other hand, the unproved bound 2R that is observed in practice can probably only be obtained by taking into account the specifics of the model's dynamics. We study these dynamics and consider a number of issues related to the 2R conjecture that explicitly uses the model dynamic. In particular, we provide bounds for the vision range that lead all agents to merge into only one cluster, we analyze the relations between agents on finite and infinite intervals, and we introduce a notion of equilibrium stability for which clusters of equal weights need to be separated by at least 2R to be stable. These results, however, do not prove the conjecture. To understand the system behavior for a large agent density, we also consider a version of the model that involves a continuum of agents.

Let us imagine a beautiful World in which everybody scores everybody... That is the case in the WWW, in the Ebay site or yet in the peer2peer network. However the graph representing the scores between agents is far from being complete. Our goal is to bring order to these worlds in the same way that L. Page and S. Brin did for the WWW. I would like to talk about existing Reputation systems, and how to improve them.

More information available from http://www.feem-web.it/ctn/events/ctn12i.htm

While there is ample evidence that social and communication networks play a key role during the spread of new ideas, products, or services, network effects are expected to have diminished influence in the stationary state, when all users are aware of the innovation, and its usage pattern is determined mainly by its utility to the user. Here we study four mobile phone-based services available to over six million subscribers, allowing us to simultaneously monitor the communication network between individuals and the time-resolved service usage patterns.
We find that usage highly correlates with the structure of the communication network, and demonstrate the coexistence on the same social network of two distinct usage classes, network effects being responsible for the quantifiable differences between them. To test the predictive power of our theory, we demonstrate that traditional marketing techniques are ineffective in permanently boosting service adoption, and propose a hub-based incentive mechanism that has the potential to enhance usage for one of the two service classes.

Everyone has already played a combinatorial game, such as chess, go, or the game of Nim. Chess and go are probably the hardest games, whereas Nim is the first game for which a complete "polynomial" strategy has been found. But they all belong to the same set of "combinatorial games". In this talk, we will firstly present combinatorial games through the definition of Conway et al., and then try to explain what makes a game easy or not. By relaxing some points of the definition of Conway, it is easy to build new games. For example, consider the combinatorial game "Clobber", that was introduced in 2002 by Nowakowski et al. This game is as much difficult as chess or go. However, if we consider a soitaire variation of it, we get an interesting and recreational one-player game on graphs, that we called "Solitaire ClobberThe rules of Solitaire Clobber are the following: Black and white stones are placed on the vertices of a given graph (one per vertex). A move consists in picking a stone and "clobbering" (which means destroying) an adjacent stone of the opposite color. The picked stone takes the place of the clobbered one, which is removed . The goal is to minimize the number of remaining stones in the end. On any graph, the computation of this minimum value is a NP-hard problem. However, it becomes easier on some families of graphs, such as cliques, trees, cycles, grids, or hypercubes. Some of these results will be detailed.

In current studies of the physical properties of networks, little attention is paid to the impact of the dynamics of the nodes on the topology of the network. Together with Francisco Varela for more than 15 years, I did some computer simulations contributing to an improved understanding of chemical and biological structure and function. We were interested in the topology of these networks, in the way they evolve in time both structurally and complying with their intrinsic dynamics (oscillatory or chaotic), and in the reactivity of these networks to outside perturbation. Chemical reaction networks, immune idiotypic networks and neural networks are illustrations of this forceful attention we paid for natural networks. These recent years, we have attended a resurgent interest for evolving networks showing interesting topology like the scale-free one. Although the most representative of these networks have been spotted in the human, computer and social worlds, the fact that such a topology allows the nodes to optimally connect has encouraged some authors to believe that this scale-freeness should hopefully be shared by biological and chemical networks. Even some possible explanations like "preferential attachment" has been proposed to justify such a topology. In my conference, I will discuss this hypothesis by showing simulations of the three networks, their dynamics, their meta-dynamics, how both interact, the likelihood of the topology and the preferential attachment and the consequences of certain topologies on the functions of the network.

The study of complex networks, or large graphs appearing in real contexts, has exploded since a few years, considering either problems specific to some networks, like web-page ranking or spread of viruses over the Internet, or some generalizations of these problems like the study of the measurement biases, the modeling of complex networks, etc. During this seminar, four different problems related to complex networks will be presented. These problems are modeling of complex networks, metrology of the Internet, dynamics of sensor networks and diffusion of innovations.

The modeling part will be presented using a random bipartite model introduced in [1]. While this model was initially introduced to model some specific complex networks, it can easily be used for most of them. Some limitations of this model will also be presented.

The metrology part will be dedicated to the case of the Internet. After a brief presentation of the problem, I will show some simulations results which where aimed at evaluating the bias that can appear when one wants to measure a network like the Internet using a tool like traceroute, and the benefit one can have using many different sources to explore the network.

In a third part I will present different approaches to study the dynamics of sensor networks based of real data from [3]. These approaches are based on the study of the dynamics of classical properties, on the dynamics of connected components and finally using flooding to rank nodes and links in terms of usefulness.

Finally, and depending on the available time, I might present some basic results about the diffusion of innovations, namely mms, over mobile.

See http://www.inma.ucl.ac.be/~blondel/studydays/06networks.html Organized jointly with IAPV/22.

http://www.lri.fr/~pierre/

This talk will describe the basic principles of Distributed Hash Tables for peer-to-peer file-sharing systems. It will briefly survey the several types of distributed hash tables proposed in the literature, and compare their main features.

http://ionia.bu.edu/

For a variety of reasons (sensors are powered by batteries, have limited computational capabilities, operate in noisy environments, the wireless channel is unreliable) sensor networks are extremely resource constrained. Hence, aggressive optimization of network operations is not merely a desirable luxury but rather an indispensable necessity. In this talk I shall outline challenges to that end and review our recent system/network-level work in drastically increasing sensor network efficiency and enabling predictable performance. Illustrative outcomes of our work include: a novel RF-based localization system, a minimal energy routing algorithm with latency performance guarantees, and a TDMA-like transmission scheduling algorithm that can drastically improve throughput over existing approaches.

We study the following consensus problem: some agents are given initial positions in the euclidian space, and move in discrete-time in order to reach the barycentre of their initial positions. Every agent asks several other agents their position before taking a decision to modify its own position. We impose that, in order to limit costs, every agent communicates with only a few other agents. What is the quickest way to converge to consensus ? This is the question we solve.

During this seminar, I will describe a few chapters of the book "Symbolic dynamics and coding", of D. Lind and B. Marcus. Surprisingly, all the fundamental concepts in this book are strongly related with graph theory, This particular way of looking to problems defined on graphs enlight some aspects of graph theory in an interesting way. I will finally discuss some ideas of generalization of results in this book that could hopefully help to solve some open problems.

With CP(Graph), we introduced graph variables and constraints over these variables in Constraint Programming (CP). While all CP solvers support finite domains (i.e. integers), some now include set variables which ease the modeling of problems involving sets. Together with so-called global constraints, these "global variable types" allow an higher-level modeling for the CP user and a better exploitation of the structure of the problem by the constraint solver. A common substructure found in CP models of graph problems is that of a subgraph extraction problem in which a subgraph of a given fixed graph is sought under some constraints.

Each variable in a CP model has a domain: the set of all values it can be assigned to. Graph domains -- sets of graphs -- are approximated by graph intervals. With this approximation, the domain data-structure models a number of graphs which is exponential in its size.

An important task in CP is that of filtering for a constraint. This task consists in identifying sets of values which cannot belong to a solution of a constraint. By removing these values which belong to no solution, the search space is reduced. We proposed filtering algorithms for several constraints modeling graph properties and relations. These algorithms use techniques and data structures from discrete algorithmics but focus on a different problem: instead of finding one solution of a graph problem, the task consists in finding the union and the intersection of all the solutions of this graph problem.

A proof of concept of this framework has been implemented on top of Gecode and applied to constrained metabolic pathway extraction and constrained graph matching. It is available under an open-source license.

Slides?.