我的算法类中的一个任务是设计一个穷举搜索算法来解决集团问题.也就是说,给定大小为n的图,该算法应该确定是否存在大小为k的完整子图.我想我已经得到了答案,但我不禁想到它可以改进.这就是我所拥有的:

版本1

输入:由数组A [0,... n -1] 表示的图形,要查找的子图形的大小k.

output:如果子图存在则为True,否则为False

算法(类似python的伪代码):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

版本2

input:大小为n乘n的邻接矩阵,k是要查找的子图的大小

输出:A中大小为k的所有完整子图.

算法(这次是在函数/ …

我的问题

是否有一种有效的算法可以在一个完整的k -partite图中找到最大权重(或最小权重)k - clique(当且仅当顶点根据维基百科属于不同的部分集时,顶点是相邻的图)？

有关条款的更多详细信息

Max-weight Clique:图中的每条边都有一个重量.集团的权重是集团中所有边缘的权重之和.目标是找到一个具有最大重量的集团.

请注意,clique的大小是k,它是完整k-partite图中最大可能的clique大小.

我试过了什么

我在项目期间遇到了这个问题.由于我不是CS人,我不确定复杂性等.

我搜索了几篇相关的论文,但没有一篇论文涉及同样的问题.我还编写了一个贪心算法+模拟退火处理它(结果似乎不好).我也尝试过类似动态编程的东西(但它看起来效率不高).所以我想知道是否可以有效地计算出精确的最优值.提前致谢.

编辑由于我的输入可能非常大(例如每个集团中的顶点数量是2 ^ k),我希望找到一个非常快速的算法(例如,k的及时多项式)来计算出最优结果.如果不可能,我们可以证明复杂性的下限吗？

"证明给定输入G和k是NP是完全的,G是否同时具有大小为k的集团和一个独立的大小为k的集合.请注意,这是1个问题,而不是2;答案是肯定的,当且仅当 G有这两个子集."

我的算法课程中遇到了这个问题,一大群学生无法弄明白.这是我们到目前为止所拥有的......

我们知道,集团和独立集合问题本身就是NP-Complete.我们也知道,对于这个问题的验证,给出一些"证书"是在NP中.

问题是以某种方式将上述问题(包含独立集合和集团)的问题简化为完全由集团或独立集合组成的问题(至少我们认为我们需要这样做).我们不知道如何在不丢失将减少量减少回原始形式所需的信息的情况下执行此减少.

我正在寻找一种重新排序技术来将邻接矩阵的连通分量组合在一起.

例如,我用蓝色和绿色两组进行了说明.最初,'1的条目分布在矩阵的行和列中.通过重新排序行和列,所有'1'可以位于矩阵的两个连续部分中,更清楚地显示蓝色和绿色分量.

我不记得这种重新排序技术是什么.我搜索了邻接矩阵,集团,排序和重新排序的许多组合.

我发现的最接近的点击是

1. symrcm 将元素移近对角线,但不制作组.

2. 有没有办法重新排序矩阵的行和列,以创建一个密集的角,在R？重点是删除完全空的行和列

请提供此技术的通用名称,以便我可以更有效地谷歌,或指向我的Matlab功能的方向.

对于大学项目,我正在尝试实施Bron-Kerbosch算法,即列出给定图形中的所有最大派系.

我正在尝试实现第一个算法(没有透视),但我的代码在维基百科的例子上测试后没有产生所有答案,到目前为止,我的代码是:

# dealing with a graph as list of lists 
graph = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0],[0,0,0,1,0,0]]


#function determines the neighbors of a given vertex
def N(vertex):
    c = 0
    l = []
    for i in graph[vertex]:
        if i is 1 :
         l.append(c)
        c+=1   
    return l 

#the Bron-Kerbosch recursive algorithm
def bronk(r,p,x):
    if len(p) == 0 and len(x) == 0:
        print r
        return
    for vertex in p:
        r_new = r[::]
        r_new.append(vertex)
        p_new = [val for val in p if …

在努力解决这个问题一段时间后,我希望在这里得到一些建议.我想知道是否有人知道一种基于显着性确定成对分组标签的自动方法.这个问题与重要性测试无关(例如Tukey用于参数化或Mann-Whitney用于非参数) - 给定这些成对比较,一些boxplot类型的数字通常用子脚本表示这些分组:

我手工完成了这个例子,这可能很乏味.我认为算法中的标记顺序应该基于每个组中的级别数 - 例如,那些包含与所有其他级别显着不同的单个级别的组应该首先命名,然后是包含2个级别的组,然后是3,等等,检查新分组是否添加了新的所需分组,并且没有违反和差异.

在下面的示例中,棘手的部分是让算法识别级别1应该与3和5分组,但3和5不应该分组(即共享标签).

示例代码:

set.seed(1)
n <- 7
n2 <- 100
mu <- cumsum(runif(n, min=-3, max=3))
sigma <- runif(n, min=1, max=3)

dat <- vector(mode="list", n)
for(i in seq(dat)){
    dat[[i]] <- rnorm(n2, mean=mu[i], sd=sigma[i])
}

df <- data.frame(group=as.factor(rep(seq(n), each=n2)), y=unlist(dat))

bp <- boxplot(y ~ group, df, notch=TRUE)
kr <- kruskal.test(y ~ group, df)
kr
mw <- pairwise.wilcox.test(df$y, df$g)
mw
mw$p.value > 0.05 # TRUE means that the levels are not significantly different at the p=0.05 level

# …

我正在处理约 200 个节点和约 3500 个边的图表。我需要找到该图的所有派系。使用networkxenumerate_all_cliques()可以很好地处理最多100个节点的较小图形，但对于较大的图形会出现内存不足的情况。

“但是，希望该算法不会耗尽内存，因为它只将候选子列表保留在内存中，并不断删除耗尽的子列表。” enumerate_all_cliques() 的源代码

有没有办法返回长度为 k 的所有派系的生成器，而不是所有派系，以节省内存？

我很惊讶 networkx 似乎没有内置函数来做到这一点，但也许我错过了一些使用内置算法来做到这一点的聪明方法？

我一直试图用下面提到的算法解决最大团问题,到目前为止还没能找到失败的情况.
算法:
对于给定的图,每个节点编号从1到N.
1.将一个节点视为永久节点并形成一组节点,使每个节点连接到该永久节点.(该集合还包括永久节点)
2现在形成原始图形的子图,使其包含所形成的集合中的所有节点,并且仅包含集合中存在的节点之间的那些边缘.
3.找出每个节点的度数.
如果所有节点都有相同的学位,那么我们就有了一个集团.
5.否则从该子图中删除最小度数节点,并从步骤3开始
重复.6.对图中的所有节点重复步骤1-5.

谁能指出这个算法的缺陷？
这是我的代码 http://pastebin.com/tN149P9m.