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
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information, Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive, CarMeN - Laboratoire de recherche en cardiovasculaire, métabolisme, diabétologie et nutrition
5 DRACULA - Multi-scale modelling of cell dynamics : application to hematopoiesis
CGMC - Centre de génétique moléculaire et cellulaire, Inria Grenoble - Rhône-Alpes, ICJ - Institut Camille Jordan [Villeurbanne], UCBL - Université Claude Bernard Lyon 1 : EA
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.
Type de document :
Article dans une revue
Knowledge and Information Systems (KAIS), Springer, 2013, 35 (1), pp.1-30. <10.1007/s10115-013-0625-y>
Liste complète des métadonnées

https://hal.inria.fr/hal-00827164
Contributeur : Christophe Rigotti <>
Soumis le : mardi 28 mai 2013 - 22:41:41
Dernière modification le : mercredi 22 février 2017 - 09:28:51

Identifiants

Citation

Pierre-Nicolas Mougel, Christophe Rigotti, Marc Plantevit, Olivier Gandrillon. Finding maximal homogeneous clique sets. Knowledge and Information Systems (KAIS), Springer, 2013, 35 (1), pp.1-30. <10.1007/s10115-013-0625-y>. <hal-00827164>

Partager

Métriques

Consultations de la notice

463