Université d'Auvergne Clermont1 | CNRS



7 years 23 weeks ago
22/10/2009 - 15:00
Jean-Charles Delvenne, Université Catholique de Louvain, Belgique
IUT des Cézeaux


The complexity of biological, social and engineering networks makes it desirable to find natural partitions into communities that can act as simplified descriptions and provide insight into the structure and function of the overall system. Although community detection methods abound, there is a lack of consensus on how to quantify and rank the quality of partitions. We show here that the quality of a partition can be measured in terms of its stability, defined in terms of the clustered autocovariance of a Markov process taking place on the graph. Because the stability has an intrinsic dependence on time scales of the graph, it allows us to compare and rank partitions at each time and also to establish the time spans over which partitions are optimal. Hence the Markov time acts effectively as an intrinsic resolution parameter that establishes a hierarchy of increasingly coarser clusterings. Within our framework we can then provide a unifying view of several standard partitioning measures: modularity and normalized cut size can be interpreted as one-step time measures, whereas Fiedler's spectral clustering emerges at long times.
We apply our method to characterize the relevance and persistence of partitions over time for constructive and real networks, including hierarchical graphs and social networks. We also obtain reduced descriptions for atomic level protein structures over different time scales. Finally, we obtain hierarchical segmentation of images, without a priori knowledge.
7 years 24 weeks ago
15/10/2009 - 15:00
Chafik Samir, ISIT, France
IUT des Cézeaux

I will describe an approach for statistical analysis of shapes of 2D boundaries (closed curves) and 3D objects (surfaces) using ideas from Riemannian geometry. A fundamental tool in this shape analysis is the construction and implementation of geodesic paths between shapes on nonlinear manifolds. We use geodesic paths to accomplish a variety of tasks, including the definition of an intrinsic metric to compare shapes, the computation of intrinsic statistics for a given set of shapes, the estimation of optimal deformations on shape spaces, and the construction of smooth paths fitting a given set of shapes. We demonstrate this approach using three applications: (i) 3D face recognition according to their shapes, (ii) symmetrization of 2D and 3D objects, and (iii) 2D and 3D objects metamorphosis.