Publications [#372533] of Fan Wei

Papers Published

1. Fox, J; Roughgarden, T; Seshadhri, C; Wei, F; Wein, N, Finding cliques in social networks: A new distribution-free model, Leibniz International Proceedings in Informatics Lipics, vol. 107 (July, 2018), ISBN 9783959770767 [doi]
   (last updated on 2026/01/16)

   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.