Finding cliques in social networks: A new distribution-free model

Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

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 nonadjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks with thousands of vertices tend to be weakly c-closed for modest values of c.

Original languageEnglish (US)
Pages (from-to)448-464
Number of pages17
JournalSIAM Journal on Computing
Volume49
Issue number2
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Fixed-parameter tractability
  • Graph algorithms
  • Social networks

Fingerprint

Dive into the research topics of 'Finding cliques in social networks: A new distribution-free model'. Together they form a unique fingerprint.

Cite this