Finding Cliques in Social Networks: A New Distribution-Free Model
Finding Cliques in Social Networks: A New Distribution-Free Model
复制标题
DOI：
10.4230/lipics.icalp.2018.55
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
J. Fox;Tim Roughgarden;C. Seshadhri;F. Wei;Nicole Wein
中科院分区：
文献类型：
--
作者：
J. Fox;Tim Roughgarden;C. Seshadhri;F. Wei;Nicole Wein
我们提出了一个新的无分销社交网络模型。我们的定义是由社交网络最普遍的签名之一，即封闭的最普遍的签名之一，即与共同邻居成对的属性往往相邻。我们最基本的定义是“ $ c $ clucted”图，其中每对顶点$ u，v $至少$ c $ common邻居，$ u $和$ v $都相邻。我们研究了列举所有最大集团的经典问题，这是社交网络分析中的重要任务。我们证明，相对于$ c $ claped图的$ c $，这个问题是固定参数。我们的结果延续到“弱$ c $ clupt的图形”，这只需要一个顶点删除订单，该订购避免了与$ c $ common neighbors的一对非贴上的顶点。数值实验表明，经过良好的社交网络往往易于$ c $，对于$ c $的适度值。
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$.