2009 | OriginalPaper | Chapter
Discovering Relevant Cross-Graph Cliques in Dynamic Networks
Authors : Loïc Cerf, Tran Bao Nhan Nguyen, Jean-François Boulicaut
Published in: Foundations of Intelligent Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Several algorithms, namely
CubeMiner
,
Trias
, and
Data-Peeler
, have been recently proposed to mine closed patterns in ternary relations. We consider here the specific context where a ternary relation denotes the value of a graph adjacency matrix at different timestamps. Then, we discuss the constraint-based extraction of patterns in such dynamic graphs. We formalize the concept of
δ
-contiguous closed 3-clique and we discuss the availability of a complete algorithm for mining them. It is based on a specialization of the enumeration strategy implemented in
Data-Peeler
. Indeed, clique relevancy can be specified by means of a conjunction of constraints which can be efficiently exploited. The added-value of our strategy is assessed on a real dataset about a public bicycle renting system. The raw data encode the relationships between the renting stations during one year. The extracted
δ
-contiguous closed 3-cliques are shown to be consistent with our domain knowledge on the considered city.