qpCliqueNumber(qpgraph)
qpCliqueNumber()所属R语言包：qpgraph
Clique number
团数
译者：生物统计家园网 机器人LoveR
描述----------Description----------
Calculates the size of the largest maximal clique (the so-called clique number or maximum clique size) in a given undirected graph.
计算最大的（所谓的集团数量或最大团的大小）在一个给定的无向图的最大团的大小。
用法----------Usage----------
qpCliqueNumber(g, exact.calculation=TRUE, return.vertices=FALSE,
approx.iter=100, verbose=TRUE, R.code.only)
参数----------Arguments----------
参数：g
either a graphNEL object or an adjacency matrix of the given undirected graph.
无论是graphNEL对象或给定的无向图的邻接矩阵。
参数：exact.calculation
logical; if TRUE then the exact clique number is calculated; if FALSE then a lower bound is given instead.
逻辑;如果为TRUE，那么确切的团数计算;如果false，那么下限代替。
参数：return.vertices
logical; if TRUE a set of vertices forming a maximal clique of maximum size is returned; if FALSE only the maximum clique size is returned.
逻辑;如果实现，形成了一个最大规模的最大集团的顶点集返回;如果为FALSE返回最大团的大小。
参数：approx.iter
number of iterations to be employed in the calculation of the lower bound (i.e., only applies when exact.calculation=FALSE.
迭代次数，在计算下界（即只适用于exact.calculation=FALSE。
参数：verbose
show progress on calculations.
显示在计算方面取得的进展。
参数：R.code.only
logical; if FALSE then the faster C implementation is used (default); if TRUE then only R code is executed.
逻辑;如果为FALSE则更快的C实现使用（默认）;如果TRUE，那么只有R代码被执行。
Details
详情----------Details----------
The calculation of the clique number of an undirected graph is one of the basic NP-complete problems (Karp, 1972) which means that its computational cost is bounded by an exponential running time (Pardalos and Xue, 1994). The current implementation uses C code from the GNU GPL Cliquer library by Niskanen and Ostergard (2003) based on the, probably the fastest to date, algorithm by Ostergard (2002).
一个无向图的团数的计算是一个基本的NP完全问题（卡普，1972年），这意味着其计算成本指数Pardalos和薛，运行时间（1994）界。当前实现使用Niskanen和Ostergard C代码（2003）的基础上，可能最快由Ostergard（2002年）的日期，算法从GNU GPL Cliquer图书馆的。
The lower bound on the maximum clique size is calculated by ranking the vertices by their connectivity degree, put the first vertex in a set and go through the rest of the ranking adding those vertices to the set that form a clique with the vertices currently within the set. Once the entire ranking has been examined a large clique should have been built and eventually one of the largests ones. This process is repeated a number of times (approx.iter) each of which the ranking is altered with increasing levels of randomness acyclically (altering 1 to $p$ vertices and again). Larger values of approx.iter should provide tighter lower bounds although it has been proven that no polynomial time algorithm can approximate the maximum clique size within a factor of n^ε (ε > 0), unless P=NP (Feige et al, 1991; Pardalos and Xue, 1994).
下界上最大的集团规模位居顶点的连接度计算，放在一组中的第一个顶点，并通过其余的排名加入的顶点集内形成一个顶点集团目前设置。一旦整个排名已审查大型集团应已建成并最终的largests的之一。这个过程反复多次（approx.iter），其中每个排名的改变与水平的不断提高，非循环的随机性（改变1 $ P $的顶点，并再次）。 approx.iter值越大，应提供更严格的下限，尽管它已被证明没有多项式时间算法可以近似n^ε（ε > 0），除非，P = NP的一个因素内最大的集团规模（飞鸽等，1991; Pardalos和薛，1994）。
值----------Value----------
a lower bound of the size of the largest maximal clique in the given graph, also known as its clique number.
下界又称作为其集团号码，图中最大的最大团的大小。
作者（S）----------Author(s)----------
R. Castelo
参考文献----------References----------
Gaussian graphical model search from microarray data with p larger than n. J. Mach. Learn. Res., 7:2621-2650, 2006.
Approximating the maximum clique is almost NP-Complete. Proc. 32nd IEEE Symp. on Foundations of Computer Science, 2-12, 1991.
computations, 43:85-103, 1972.
Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Tech. Rep. T48, 2003. (http://users.tkk.fi/~pat/cliquer.html)
Discrete Appl. Math. 120:197-207, 2002.
J. Global Optim., 4:301-328, 1994.
参见----------See Also----------
qpClique
qpClique
举例----------Examples----------
require(graph)
nVar <- 50
set.seed(123)
g1 <- randomEGraph(V=as.character(1:nVar), p=0.3)
qpCliqueNumber(g1, verbose=FALSE)
g2 <- randomEGraph(V=as.character(1:nVar), p=0.7)
qpCliqueNumber(g2, verbose=FALSE)
转载请注明:出自 生物统计家园网(http://www.biostatistic.net)。
注：
注1：为了方便大家学习，本文档为生物统计家园网机器人LoveR翻译而成，仅供个人R语言学习参考使用，生物统计家园保留版权。
注2：由于是机器人自动翻译，难免有不准确之处，使用时仔细对照中、英文内容进行反复理解，可以帮助R语言的学习。
注3：如遇到不准确之处，请在本贴的后面进行回帖，我们会逐渐进行修订。
|
发表于 2012-2-26 11:39:04
