Skip to Main content Skip to Navigation
Journal articles

On the termination of some biclique operators on multipartite graphs

Christophe Crespelle 1 Matthieu Latapy 2 Thi Ha Duong Phan 3
1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
2 ComplexNetworks
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.
Document type :
Journal articles
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Clémence Magnien Connect in order to contact the contributor
Submitted on : Thursday, September 17, 2015 - 1:12:24 PM
Last modification on : Tuesday, November 16, 2021 - 4:11:58 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 7:44:52 AM


Files produced by the author(s)



Christophe Crespelle, Matthieu Latapy, Thi Ha Duong Phan. On the termination of some biclique operators on multipartite graphs. Discrete Applied Mathematics, Elsevier, 2015, 195, pp.59-73. ⟨10.1016/j.dam.2015.02.006⟩. ⟨hal-01200865⟩



Les métriques sont temporairement indisponibles