Finding maximal homogeneous clique sets - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Knowledge and Information Systems (KAIS) Année : 2014

Finding maximal homogeneous clique sets

Résumé

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.
Fichier non déposé

Dates et versions

hal-00827164 , version 1 (28-05-2013)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More