@article{910c5c0f09bb47fe875ad38e08f9d133,

title = "Finding cliques in social networks: A new distribution-free model",

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.",

keywords = "Fixed-parameter tractability, Graph algorithms, Social networks",

author = "Jacob Fox and Tim Roughgarden and C. Seshadhri and Fan Wei and Nicole Wein",

note = "Funding Information: ∗Received by the editors August 29, 2018; accepted for publication (in revised form) January 6, 2020; published electronically April 27, 2020. A preliminary version of this paper appeared in the proceedings of ICALP{\textquoteright}18. https://doi.org/10.1137/18M1210459 Funding: The first author was supported by a Packard fellowship, by NSF Career Award DMS-1352121, and by an Alfred P. Sloan Foundation fellowship. The second author was supported in part by NSF award CCF-1524062. The third author was supported by NSF awards CCF-1319080 and CCF-1740850. The fifth author was supported in part by a National Science Foundation fellowship. †Department of Mathematics, Stanford University, Stanford, CA 94305-2125 (jacobfox@ stanford.edu, fanwei@stanford.edu). ‡Department of Computer Science, Stanford University, Stanford, CA 94305 (tim@cs.stanford. edu). §Department of Computer Science, University of California, Santa Cruz, CA 95064 (sesh@ucsc. edu). ¶EECS, Massachusetts Institute of Technology (MIT), Cambridge, MA 02139 (nwein@mit.edu). Publisher Copyright: {\textcopyright}2020 Society for Industrial and Applied Mathematics.",

year = "2020",

doi = "10.1137/18M1210459",

language = "English (US)",

volume = "49",

pages = "448--464",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}