Finding Collections of k-Clique Percolated Components in Attributed Graphs

Pierre-Nicolas Mougel 1, 2 Christophe Rigotti 1, 2, 3, * Olivier Gandrillon 4, 5
* Corresponding author
2 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 - UMR 5558
3 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
4 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 : In this paper, we consider graphs where a set of Boolean attributes is associated to each vertex, and we are interested in k-clique percolated components (components made of overlapping cliques) in such graphs. We propose the task of finding the collections of homogeneous k-clique percolated components, where homogeneity means sharing a common set of attributes having value true. A sound and complete algorithm based on subgraph enumeration is proposed. We report experiments on two real databases (a social network of scientific collaborations and a network of gene interactions), showing that the extracted patterns capture meaningful structures.
Complete list of metadatas

https://hal.inria.fr/hal-00758843
Contributor : Christophe Rigotti <>
Submitted on : Thursday, November 29, 2012 - 2:16:25 PM
Last modification on : Wednesday, November 20, 2019 - 2:42:42 AM

Identifiers

  • HAL Id : hal-00758843, version 1

Citation

Pierre-Nicolas Mougel, Christophe Rigotti, Olivier Gandrillon. Finding Collections of k-Clique Percolated Components in Attributed Graphs. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2012, Kuala Lumpur, Malaysia. pp.181--192. ⟨hal-00758843⟩

Share

Metrics

Record views

465