Edit on GitHub

DisjointCliqueCover.jl

Description

This package DisjointCliqueCover, written in the Julia language, implements a method to estimate a minimal edge-disjoint edge clique cover (EECC) of a graph, according to the heuristic presented in Burgio et al. [1]. A minimal edge clique cover is a minimal set of cliques able to cover the entire set of edges in the graph. In a EECC, the cliques are required to be all edge-disjoint, i.e., they can have no more than one node in common.

A graph can admit multiple minimal edge clique covers and finding one of them is known to be a NP-complete problem [2]. Therefore, approximate heuristics are needed to estimate it in large graphs.

The notion of EECC is introduced in [1] as a basis to define the Microscopic Epidemic Clique Equations (MECLE) model. This is a discrete-time markovian model describing complex contagion processes on higher-order networks, represented as hypergraphs and, specifically, as simplicial complexes. The model builds upon the cliques in the underlying graph of a considered higher-order network. As shown in [1], in order to account for the higher-order dynamical correlations among the states of the nodes in those cliques, the latter are required to be edje-disjoint. This leads to the search for the EECC of the underlying graph, hence to the respective heuristic whose source code is here provided.

As an example, the following graph admits a unique minimal EECC

eecc.png

which is given by

[2, 4, 13, 14]
[3, 4, 5]
[6, 7, 13]
[8, 9, 13]
[9, 10, 11]
[1, 2]
[1, 14]
[7, 8]
[11, 12]
[12, 13]

References

  1. Giulio Burgio, Alex Arenas, Sergio Gómez and Joan T. Matamalas: Network clique cover approximation to analyze complex contagions through group interactions, Comms. Phys. (2021) in press (arXiv:2101.03618)

  2. Lawrence T. Kou, Larry J. Stockmeyer and Chak Kuen Wong: Covering edges by cliques with regard to keyword conflicts and intersection graphs, Comms. ACM 21(2) (1978) 135–139 (doi)

Authors

  • Giulio Burgio (Universitat Rovira i Virgili, Tarragona, Spain)

  • Alex Arenas (Universitat Rovira i Virgili, Tarragona, Spain)

  • Sergio Gómez (Universitat Rovira i Virgili, Tarragona, Spain)

  • Joan T. Matamalas (Harvard Medical School & Brigham and Women's Hospital, Boston, USA)