Passer à la navigation principale Passer à la recherche Passer au contenu principal

A Declarative Framework for Maximal k-plex Enumeration Problems

  • Université d'Artois
  • INSY2S

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

12 Citations (Scopus)

Résumé

It is widely accepted that an ideal community in networks is the one whose structure is closest to a (maximal) clique. However, in most real-world graphs the clique model is too restrictive, as it requires complete pairwise interactions. More relaxed cohesive subgraph models were then studied. A k-plex is one of the arguably most studied pseudo-clique model. A k-plex of size n is a subgraph where any vertex is adjacent to at least (n - k) vertices. Unfortunately, some maximal k-plexes, by involving irrelevant subgraphs, are far from designing meaningful communities in real-world networks. In this paper, we first introduce a novel variant of k-plex model, called cohesive k-plex, which is more appropriate for modeling closely-interacting communities. Then, we reduce the problem of enumerating maximal (cohesive) k-plexes in a graph to those of enumerating the models of a formula in propositional logic. Afterwards, to make our approach more efficient, we provide a decomposition technique that is particularly suitable for deriving smaller and independent sub-problems easy to resolve. Lastly, our extensive experiments on various real-world graphs demonstrate the efficiency of the proposed approach w.r.t state-of-the-art algorithms.

langue originaleAnglais
titreInternational Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
EditeurInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages660-668
Nombre de pages9
ISBN (Electronique)9781713854333
étatPublié - 1 janv. 2022
Evénement21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 - Auckland, Virtual, Nouvelle-Zélande
Durée: 9 mai 2022 → 13 mai 2022

Série de publications

NomProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2
ISSN (imprimé)1548-8403
ISSN (Electronique)1558-2914

Une conférence

Une conférence21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
Pays/TerritoireNouvelle-Zélande
La villeAuckland, Virtual
période9/05/22 → 13/05/22

Empreinte digitale

Examiner les sujets de recherche de « A Declarative Framework for Maximal k-plex Enumeration Problems ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation