TY - GEN
T1 - Finding cliques in social networks
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
AU - Fox, Jacob
AU - Roughgarden, Tim
AU - Seshadhri, C.
AU - Wei, Fan
AU - Wein, Nicole
N1 - Publisher Copyright:
© Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein;.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
KW - Fixed-parameter tractability
KW - Graph algorithms
KW - Social networks
UR - http://www.scopus.com/inward/record.url?scp=85049785982&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049785982&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.55
DO - 10.4230/LIPIcs.ICALP.2018.55
M3 - Conference contribution
AN - SCOPUS:85049785982
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 9 July 2018 through 13 July 2018
ER -