Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile, which is the final graph partitioning. This allows to evaluate the robustness of a cluster as the average percentage of partitions in the profile joining its element pairs ; this notion can be extended to partitions. Doing so, the initial and consensus partitions can be compared. A simulation protocol, based on random graphs structured in communities is designed to evaluate the efficiency of the Bootstrap Clustering approach.

This paper presents a new application of logic programming to a real-life problem in hydraulic engineering. The work is developed as a collaboration of computer scientists and hydraulic engineers, and applies Constraint Logic Programming to solve a hard combinatorial problem. This application deals with one aspect of the design of a water distribution network, i.e., the valve isolation system design. We take the formulation of the problem by Giustolisi and Savić (2008 Optimal design of isolation valve system for water distribution networks. In Proceedings of the 10th Annual Water Distribution Systems Analysis Conference WDSA2008, J. Van Zyl, A. Ilemobade, and H. Jacobs, Eds.) and show how, thanks to constraint propagation, we can get better solutions than the best solution known in the literature for the Apulian distribution network. We believe that the area of the so-called hydroinformatics can benefit from the techniques developed in Constraint Logic Programming and possibly from other areas of logic programming, such as Answer Set Programming.

We first describe four recent methods to cluster vertices of anundirected non weighted connected graph. They are all based onvery different principles. The fifth is a combination of classicalideas in optimization applied to graph partitioning. We comparethese methods according to their ability to recover classesinitially introduced in random graphs with more edges within theclasses than between them.

In this paper, a graph partitioning problem that arises in the design ofSONET/SDH networks is defined and formalized. Approximation algorithms withperformance guarantees are presented. To solve this problem efficiently inpractice, fast greedy algorithms and a tabu-search method are proposed andanalyzed by means of an experimental study.