An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem
An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem
复制标题
DOI：
10.1007/s00453-008-9238-3
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
T. Uno
中科院分区：
文献类型：
--
作者：
T. Uno
在给定图中寻找稠密结构的问题是信息学中的一个基本问题，包括数据挖掘和数据工程。团是一种表示稠密结构的流行模型，由于其简单易行而被广泛使用。伪团是团的自然扩展，团是从团中去除少量边而得到的子图。本文定义了一个伪团，它的边数与顶点数相同的团的边数之比不小于一个给定的阈值。在本文中，我们解决的问题，列举所有的伪团为一个给定的图和阈值。我们首先表明，它似乎是很难获得多项式时间算法使用简单的分而治之的方法。然后，我们提出了一个多项式时间，多项式延迟精确，算法的基础上反向搜索。每个伪团的时间复杂度为O（Δlog| V| +min {Δ2，|V| +| E|}).计算实验表明，我们的算法的效率，随机生成的图和实际图。
The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering. Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise, algorithm based on reverse search. The time complexity for each pseudo clique isO(Δlog |V|+min {Δ2,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs.