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 metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-01200865
Contributor : Clémence Magnien <>
Submitted on : Thursday, September 17, 2015 - 1:12:24 PM
Last modification on : Monday, May 6, 2019 - 11:49:34 AM
Long-term archiving on : Tuesday, December 29, 2015 - 7:44:52 AM

File

Multipartie.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

590

Files downloads

217