Isolation concepts for clique enumeration: Comparison and computational experiments
Isolation concepts for clique enumeration: Comparison and computational experiments
复制标题
派枚举的隔离概念：比较和计算实验
DOI：
10.1016/j.tcs.2009.05.008
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
Falk Hüffner;Christian Komusiewicz;Hannes Moser;R. Niedermeier
我们做计算研究有关的枚举孤立集团图。最近引入的隔离度测量了集团与图的其余部分的连通度。隔离有助于获得更快的算法枚举的最大一般集团和过滤出集团与特殊语义。我们比较了三个隔离的概念和它们的组合与两个枚举模的最大集团（“孤立最大”与“最大孤立”）。所有研究的概念表现出的枚举任务相对于参数“隔离度”的固定参数的易处理性。我们提供了第一个系统的实验研究，相应的枚举算法，使用合成图（在Gn，m，pmodel），金融网络，和音乐艺术家相似性网络，提出了一个有用的工具，在分析金融和社交网络枚举孤立的集团。
We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the Gn,m,pmodel), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.