Skip to Main content Skip to Navigation
Journal articles

Finding maximal homogeneous clique sets

Pierre-Nicolas Mougel 1 Christophe Rigotti 2, 1, 3 Marc Plantevit 1 Olivier Gandrillon 4, 5
1 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
3 BEAGLE - Artificial Evolution and Computational Biology
LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558, Inria Grenoble - Rhône-Alpes, LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
5 DRACULA - Multi-scale modelling of cell dynamics : application to hematopoiesis
CGPhiMC - Centre de génétique et de physiologie moléculaire et cellulaire, Inria Grenoble - Rhône-Alpes, ICJ - Institut Camille Jordan [Villeurbanne]
Abstract : Many datasets can be encoded as graphs with sets of labels associated with the vertices. We consider this kind of graphs and we propose to look for patterns called maximal homogeneous clique sets, where such a pattern is a subgraph that is structured in several large cliques and where all vertices share enough labels. We present an algorithm based on graph enumeration to compute all patterns satisfying user-defined constraints on the number of separated cliques, on the size of these cliques, and on the number of labels shared by all the vertices. Our approach is tested on real datasets based on a social network of scientific collaborations and on a biological network of protein-protein interactions. The experiments show that the patterns are useful to exhibit subgraphs organized in several core modules of interactions. Performances are reported on real data and also on synthetic ones, showing that the approach can be applied on different kinds of large datasets.
Complete list of metadata
Contributor : Christophe Rigotti Connect in order to contact the contributor
Submitted on : Tuesday, May 28, 2013 - 10:41:41 PM
Last modification on : Tuesday, July 20, 2021 - 5:20:04 PM



Pierre-Nicolas Mougel, Christophe Rigotti, Marc Plantevit, Olivier Gandrillon. Finding maximal homogeneous clique sets. Knowledge and Information Systems (KAIS), Springer, 2014, 39 (3), pp.579-608. ⟨10.1007/s10115-013-0625-y⟩. ⟨hal-00827164⟩



Record views