• View
• Edit
• History
• Print

2004-2005

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

Laura Zager and George Verghese Measures of graph similarity have a broad array of applications, including comparing chemical structures, navigating complex networks like the World Wide Web, and more recently, analyzing different kinds of biological data. Our work focuses on a class of iterative algorithms that use the structural similarity of local neighborhoods to derive pairwise similarity scores between graph elements. We have developed a new similarity measure based on these approaches that uses a linear update to generate both node and edge similarity scores and has desirable convergence properties. We also explore the application of this similarity measure to graph matching. We attempt to correctly position a subgraph GB within a graph GA using a maximum weight matching algorithm applied to the similarity scores between GA and GB. Significant performance improvements are observed when the topological information provided by the similarity measure is combined with additional information about the attributes of the graph elements and their local neighborhoods. Matching results are presented for subgraph matching within randomly-generated graphs; an appendix briefly discusses matching applications in the yeast interactome, a graph representing protein-protein interactions within yeast.

http://www2.info.ucl.ac.be/people/YDE/yde.html

The context of this research is the analysis of biochemical networks, represented as graphs. The constraint programming framework (CP) is an attractive framework because many of the analyses can be expressed as a set of constraints on (extended) graphs, and various domain expertise can also be expressed within constraints. In CP, the potential search space induced by the domains of the variables is explored and actively pruned by propagators associated to the constraints. We present a new domain of computation in constraint programming : graphs. Graph variables are introduced, as well as associated primitive constraints and propagators. Two classes of problems are then handled : contrained path finding and approximate graph matching. It is shown how these problems can be solved in CP(Graph) through the definition of global constraints enhancing the pruning. Experimental results on a first implementation of CP(graph) will be reported.
PDF Slides?

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

There exists a set of two basic operations on undirected graph ("vertex addition" and "edge splitting") that preserve minimal rigidity, i.e., applying one of them on a minimally rigid graph always leads to a (larger) minimally rigid graph. Moreover, any minimally rigid graph can be obtained as the result of a sequence of operations applied on the initial seed K2. It is possible to define analogous operations on directed graphs in such a way that they preserve minimal persistence. However, they are not sufficient to build all the minimally persistent graphs. We consider thus different possibilities of additional operations that would lead to this property, and finally select the "edge switching", which is in a certain sense orthogonal to the "vertex addition" and "edge splitting". This involves the study of several properties of the minimally persistent graphs, such as the provable existence of a path from any vertex to all the vertices having some degrees of freedom.

http://www.lirmm.fr/xml/fr/lirmm.html

A paper of Paul Vitanyi is presented (http://homepages.cwi.nl/~paulv/papers/amdug.pdf) and then some improvements are proposed.

Introduction and Timetables?.

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

In this talk, we present a new way of representing and aggregating preferences using a stochastic interpretation.

Given a (weighted) list of (binary) preference relations on a set of alternatives, our objective is to aggregate this information into a single preference relation.

Introducing a Markov chain where each state corresponds to an alternative and whose transition probabilities are computed using the list of preference relations, we rank the alternatives according to the resulting asymptotic probability distribution.

We then extend the method to introduce the notion of incomparability and present a novel graphical scheme to represent alternatives. We demonstrate various properties of this method, especially in the important case where the preference relations are semiorders.

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

In certain applications, such as magnetic recording, one is often interested in binary codes whose elements avoid a set of forbidden patterns. In order to minimize the error probability of some magnetic-recording systems, a more complicated problem arises when it is desirable to find code words whose differences avoid a forbidden pattern or a set of forbidden patterns. The asymptotic growth with the length of the words of the largest cardinality of such set is the capacity of the forbidden set. Representing the problem as a graph theory problem, the capacity of a forbidden pattern, and of a set of forbidden patterns, can be expressed as the joint spectral radius of a set of matrices [3], [4]. The joint spectral radius is a quantity that is in general NP-hard to compute and approximate [5], and the natural question therefore arises of determining whether the particular structure of the matrices arising in the context of capacity computation make this computation any simpler. The talk will present the problem and show a related problem that is proven to be NP-hard. Eventually, we will discuss about how to compute efficiently a joint spectral radius in cases where the matrices are particularly structured, as for example in graph theory. Algorithms from [1], [2] will be presented.
{Key words} : joint spectral radius, capacity, forbidden words

[1] Vincent D. Blondel and Yurii Nesterov, Computationally efficient approximations of the joint spectral radius. To appear in SIAM Journal of Matrix Analysis.
[2] Moision and Orlitsky, On codes with local joint constraints. unpublished.
[3] Moision, Orlitsky, and Siegel, On Codes that Avoid Specified Differences. IEEE Transactions on Information Theory, 47, 2001.
[4] Bruce E. Moision, Alon Orlitsky, and Paul H. Siegel, Bounds On The Rate Of Codes Which Forbid Specified Difference Sequences. In Proc. 1999 IEEE Global Telecommun. Conf. (GLOBECOM '99), December 1999.
[5] J. Tsitsiklis and V. Blondel, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate.Mathematics of Control, Signals, and Systems. 10:31,40, 1997.

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

Motivated by [1,2,3], we consider formations of autonomous agents in a 2-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant, and the problem is to determine if one can guarantee that the structure of the formation will persist, i.e., if the distance between any pair of agents will remain constant. A natural way to represent such a formation is to use a directed graph. In this paper we provide a theoretical framework for this problem, and give a formal definition of persistent graphs (a graph is persistent if the structure of almost all corresponding formations persists). Note that although these two notions are related, persistence is a distinct property from rigidity (concerning which much is known [4]). We derive then various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define the notion of minimal persistence (persistence with an optimal number of edges), and eventually, we apply these notion to the interesting special case of cycle-free graphs.

[1] T. Eren, B.D.O. Anderson, A.S. Morse, and P.N. Belhumeur. Information structures to secure control of rigid formations with leader-follower structure. To appear
[2] J. Baillieul and A. Suri. Information patterns and hedging brockett's theorem in controlling vehicle formations. In Proc. of the 42nd IEEE Conf. On Decision and Control, volume 1, pages 556{563, Hawaii, december 2003.
[3] A. Das, J. Spletzer, V. Kumar, and C. Taylor. Ad hoc networks for localization and control. In Proc. of the 41st IEEE Conf. on Decision and Control, Las Vegas, NV, 2002.
[4] T. Tay and W. Whiteley. Generating isostatic frameworks. Structural Topology, (11):21{69, 1985.

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

Non-Negative Matrix Factorization (NNMF) has been heavily used in learning and feature extraction of human faces and in other related fields. For graphs, we will show how to formulate the problem of Graph Clustering (GC) as a NNMF problem. We will give some examples and formulate open problems in the application of NNMF to GC.

http://www.lirmm.fr/xml/fr/lirmm.html PageRank is a measurement of importance of the pages of the Web based on a very simple recursive principle: a page is important if it is pointed by important pages. Behind this definition hides at the same time a stochastic interpretation and a circuital vision.

The stochastic interpretation, that relies on the Perron-Frobenius theorem, is often the only one retained because it was proposed by Brin and Page, the authors of the algorithm. However, the circuital interpretation, deeply investigated by Bianchini et al. , proves useful too, as it uses the less restrictive Banach fixed-point theorem to prove its correctness.

The talk will explain those two interpretations, with their respective advantages and disadvantages. The stress will be laid on the adaptability of the ideal models at the reality of the Web graphs.

PPT Slides?

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

The literature existing in the field of graph matching, and in particular of spectral graph matching, only applies to undirected graphs. We look at how to extend these methods to directed graphs.
- We start from the notion of similarity matrix S and extend it to a set of mutually orthogonal matrices S_i.
- We then derive a general iterative method to compute "dominant projection subspaces" of graphs applicable for undirected graphs and extend it to directed graphs.
- Finally we apply this to a few examples and discuss the validity of the results.

http://web.mit.edu/ameg/www/index.html

We consider dynamical input/output models

G: -------y(k)=C*x(k), x(k+1)=A*x(k)+B*f(k),

where f=f(k) is a scalar input, y=y(k) is a scalar output. Such equations, for example, can model dissipation of a substance over a network, where n-by-n matrix A describes the network, column n-vector B defines substance injection points, and row n-vector C defines monitoring policy.

When n is very large, system simulation takes a lot of time, and analysis and design of interconnections with other systems becomes practically impossible. We are interested in approximating G by a reduced model

Gr: -------yr(k)=Cr*xr(k), xr(k+1)=Ar*xr(k)+Br*f(k),

where the dimension of xr(k) is very small, while taking care that Gr acts in a way similar to G.

The following mathematical problem can be related to this general model reduction setup: given r>0, a norm p=pN on the set of real sequences of length N>>r, and a stable system G, find an efficient (polynomial time) algorithm for minimizing p(g-gr), where g(k)=C*(A^k)*B (k=0,1,...,N-1) is the sequence of first N samples of the unit sample response of G, and gr(k)=Cr*(Ar^k)*Br is the sequence of first N samples of the unit sample response of a stable system Gr of order less than r.

Apparently, there is no norm p for which a polynomial time algorithm of optimal model reduction, as described above, is known. In this talk, a solution to a slightly simpler problem is given: a seminorm p=pN on the set of real sequences of length N>>r is defined, such that pN(g)>0 on unit sample responses of systems of order less than N/2, and the optimal model reduction problem with respect to pN has a solution of complexity which is LINEAR with respect to N, and polynomial with respect to r and accuracy.

http://www.core.ucl.ac.be/~vincentvannetelbosch/

PDF Slides

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

Recently, two new algorithms have been introduced to compute a similarity score between the nodes of two graphs [1, 3]. These algorithms both describe the similarity between nodes of two graphs as the limit of the iterates $ x_+ = (Ax)/ norm{Ax}$ , where $ A$ is a nonnegative matrix derived from the adjacency matrix of a so-called product graph. The matrix $ A$ may have several eigenvectors associated to eigenvalues of maximal magnitude and so these iterates may fail to converge. To cope with this lack of convergence, Melnik et al. [3], propose to change the iteration formula for $ x_+ = (Ax+b)/ norm{Ax+b}$ , for particular $ b$ and norm.They observe experimentally the convergence of their algorithm.
We will talk about results of Krause [2] from which the convergence to a unique fixed point can be deduced. Afterward, we will see how this fixed point can be characterized.

[1] Vincent D. Blondel, Anah´ Gajardo, Heymans Maureen, Pierre Senellart, and Paul Van Dooren, A measure of similarity between graph vertices: Applications to synonym extraction and web searching, SIAM Rev. 46 (2004), no. 4, 647-666. http://epubs.siam.org/sam-bin/getfile/SIREV/articles/41596
[2] Concave Perron-Frobenius theory and applications, Nonlinear Analysis 47 (2001), no. 3, 1457-1466. http://www.sciencedirect.com/science?_ob=ArticleURL...
[3] Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm, Similarity flooding: A versatile graph matching algorithm and its application to schema matching, Proc. 18th ICDE Conf., 2002. http://newdbpubs.stanford.edu:8090/pub/2002-1

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

I will present some equilibrium transportation models and discuss their relevance and complexity. We will discuss also some open questions.

PDF Slides?

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

The talk will consist in an overview presentation of the book "Random Graphs", by Svante Janson, Tomasz Luczak and Andrzej Rucinski (Wiley-Interscience Publications, 2000). Let us randomly pick up an undirected graph with N vertices and M edges. A typical result is: "if M > N log N then the graph will be connected with overwhelming probability (for large N)".

Depending on the available time and the interest of the audience, we could talk about
-the main basic theorems
-some of the ideas used to prove such results ("first moment method", "second moment method", etc.)
-the evolution of the random graph as the number of edges increases (including the "phase transition")
-properties that can be expressed by first-order logical formulae (and "zero-one laws")

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

Processes taking place on networks provide a large area of investigation, see [1]. Roughly speaking, there are two kinds of such processes: the ones act on the structure of graph and the others on the states of the nodes in a graph. I take a closer look at the later processes by considering what I call influence processes. Those are processes for which the state of a node depends directly on the states of its neighbours (and possibly of its proper state). The start point will be "The Influence Model" [2], and then I will talk about "The Voter Model" [3] and disease processes [1]. The motivations of such studies is usually that those models can be used to prevent waves of catastrophes, or they can be regarded as simple model of opinion formation in a given network, or yet they provide general insight into the effects of network topology on the dynamic of the states of the nodes in a graph.

[1] M.E.J. Newman. The Structure and Function of Complex Networks, SIAM Review 45, 224-256 (2003)
[2] C. Asavathiratham, The Influence Model: A Tractable Representation for the Dynamics of Networked Markov Chains, PhD dissertation, EECS Dept., MIT, Oct.2000.
[3] http://www.math.cornell.edu/~durrett/survey/survc5.html, http://psoup.math.wisc.edu/extras/nlvm/nlvmsim.html .

PPT Slides?

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

The concept of rigidity of structures has been used for decades in various domains like civil or mechanical engineering. In 1970, Laman studied it from a graph theory point of view, and gave a necessary and sufficient condition for a undirected graph to be generically rigid [1] (i.e. so that almost every corresponding structure is rigid). Nowadays, some new applications involving non-symmetric relations such as the control of a group a robots require to extend this concept to directed graphs [2]. Although some conjectures were made in this domain [3], no universally accepted definition of directed rigidity was provided yet. I will thus discuss some properties required for any reasonable definition and the implications of theses properties and of possible definitions.

[1] G. Laman. On graphs and rigidity of plane skeletal structures. J. Engrg. Math. 4 1970 331-340.
[2] A. Das, J. Spletzer, V. Kumar, and C. Taylor. Ad hoc networks for localization and control. In Proc. of the 41st IEEE Conf. on Decision and Control, Las Vegas, NV, 2002.
[3] T. Eren, W. Whiteley, B.D.O. Anderson, A.S. Morse and P.N. Belhumeur. Information structures to secure control of rigid formations with leader-follower structure. Not submitted yet.

http://www.esat.kuleuven.be/scd/person.php?view=0&persid=143 For the occasion of the Honorary Doctoral Degree awarded to Prof. Dr. Lennart Ljung, a literature network was built by querying Web of Science. The first degree literature network is constructed using as seed papers all 138 papers of "Ljung L" known to Web of Science, and by extending the network with all cited and all citing papers. The resulting directed graph contains 4943 nodes and 6216 edges (citations). On this graph we have applied Markov Clustering, a link-based clustering algorithm, and text-based hierarchical clustering. For ease of interpretation, each cluster has a corresponding term network. Multidimensional Scaling is another technique that has been applied on the 138 papers. To incorporate the dynamical aspect, consecutive bins of papers have been made using a sliding window of 5 years of publication. Each bin is again clustered, visualized on the 2D multidimensional scaling map, and complemented with a term network. To conclude, also a co-authorship network and various citation statistics are provided.

[1] (Biolayout, 2001) A.J. Enright, C.A. Ouzounis, BioLayout JAVA, Bioinformatics, 2001, 17/ 853-854, http://maine.ebi.ac.uk:8000/services/biolayout/
[2] (van Dongen, 2000) van Dongen S., "A cluster algorithm for graphs", Technical Report INS-R0010, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, May 2000, http://www.cwi.nl/ftp/CWIreports/INS/INS-R0010.ps.Z

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

The concept of rigidity of structures has been used for decades in various domains like civil or mechanical engineering. In 1970, Laman studied it from a graph theory point of view, and gave a necessary and sufficient condition for a undirected graph to be generically rigid [1] (i.e. so that almost every corresponding structure is rigid). Nowadays, some new applications involving non-symmetric relations such as the control of a group a robots require to extend this concept to directed graphs [2]. Although some conjectures were made in this domain [3], no universally accepted definition of directed rigidity was provided yet. I will thus discuss some properties required for any reasonable definition and the implications of theses properties and of possible definitions.

[1] G. Laman. On graphs and rigidity of plane skeletal structures. J. Engrg. Math. 4 1970 331-340.
[2] A. Das, J. Spletzer, V. Kumar, and C. Taylor. Ad hoc networks for localization and control. In Proc. of the 41st IEEE Conf. on Decision and Control, Las Vegas, NV, 2002.
[3] T. Eren, W. Whiteley, B.D.O. Anderson, A.S. Morse and P.N. Belhumeur. Information structures to secure control of rigid formations with leader-follower structure. Not submitted yet.

In the process of Software engineering (as well as several other industries such as aeronautics), an important task is the testing of the application. This task is crucial to ensure the quality of the product when it is released or updated. In fact, this task is so crucial that testing can take up to 50% of a project resource.

The Model-Based-Testing methodology models the application under test with a finite state automaton where each state of the automaton represents a possible state of the application (i.e. dialog window state) and where each transition is an action the application (i.e. a mouse click on a button). Once the model is built, test cases (sequence of transitions) are generated using a given strategy. For example, one would like to find the shortest path that passes through all the transitions of the automaton (Directed Chinese Postman problem, also called New-York street sweeper problem). There is a good introductory paper on MBT at http://www.geocities.com/model_based_testing/intelligent.pdf (it is targeted to IT people who do not have knowledge in graph theory).

Although there have been already a number of papers on the subject, I feel that this field has still a lot of open problems that need to be solved. In general, the people from IT have been using existing graph theory algorithms such as the Postman, to generate the test cases. However, they are quickly facing a number of problems:- state space explosion: it is trivial to see that the size of the automaton can quickly grow to infinity and thus, render his testing practically impossible,
- non-deterministic applications: complex software that involve multi-threading, networking and generally external resources (physical device) are generally non-deterministic. Thus, the tester only has an abstract automaton
- the majority of the graph theory algorithm are sequential algorithm and have not been developed to be parallelized. If an algorithm can produce a set of sub-optimal path instead of 1 optimal path then the computation can be distributed across a cluster of computers, etc...