Finding Cliques in Social Networks: A New Distribution-Free Model

DOI10.1137/18M1210459zbMATH Open1443.68128arXiv1804.07431OpenAlexW3019028961MaRDI QIDQ5112249

Author name not available (Why is that?)

Publication date: 28 May 2020

Published in: (Search for Journal in Brave)

Abstract: We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure---the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a "$c$-closed" graph, where for every pair of vertices $u,v$ with at least $c$ common neighbors, $u$ and $v$ are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to $c$ on $c$-closed graphs. Our results carry over to "weakly $c$-closed graphs", which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with $c$ common neighbors. Numerical experiments show that well-studied social networks tend to be weakly $c$-closed for modest values of $c$.

Full work available at URL: https://arxiv.org/abs/1804.07431

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Finding Cliques in Social Networks: A New Distribution-Free Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112249)