标签: clique

现实世界的问题:

我有许多公司的董事数据,但有时候"XYZ的董事John Smith"和"ABC的董事John Smith"是同一个人,有时他们不是.此外,"XYZ的导演约翰J.史密斯"和"ABC的导演约翰史密斯"可能是同一个人,也可能不是.通常检查附加信息(例如,关于"约翰史密斯,XYZ主任"和"约翰史密斯,ABC主任"的传记数据的比较)使得有可能解决两个观察是否是同一个人.

问题的概念版本:

本着这种精神,我正在收集识别匹配对的数据.例如,假设我有以下匹配对:{(a, b), (b, c), (c, d), (d, e), (f, g)}.我想使用关系"与人相同"的传递属性来生成"连通组件" {{a, b, c, d, e}, {f, g}}.那是{a, b, c, d, e}一个人,{f, g}是另一个人.(该问题的早期版本提到了"派系",这显然是别的东西;这可以解释为什么find_cliques在networkx给出"错误"结果(为了我的目的).

以下Python代码完成了这项工作.但我想知道:是否有更好的(计算成本更低)方法(例如,使用标准或可用的库)？

这里和那里似乎有相关的例子(例如,python中的Cliques),但这些是不完整的,所以我不确定他们指的是什么库或如何设置我的数据来使用它们.

示例Python 2代码:

def get_cliques(pairs):
    from sets import Set

    set_list = [Set(pairs[0])]

    for pair in pairs[1:]:
        matched=False
        for set in set_list:
            if pair[0] in set or pair[1] in set:
                set.update(pair)
                matched=True
                break
        if not matched:
            set_list.append(Set(pair))

    return set_list

pairs …

任何人都可以告诉我,在网络上我可以找到一个解释Bron-Kerbosch算法的集团发现或解释它是如何工作的？

我知道它发表在"算法457:找到无向图的所有派系"一书中,但我找不到能描述算法的自由源.

我不需要算法的源代码,我需要解释它是如何工作的.

Google Pregel论文中提到了半聚类算法.使用以下公式计算半聚类的得分

哪里

Ic是所有内部边缘
的权重之和Bc是所有边界边缘的权重之和
Vc是半群集中的顶点数量,
fb是边界边缘分数因子(用户定义在0和1之间)

该算法非常简单,但我无法理解上述公式是如何到达的.请注意,分母是Vc顶点数之间可能的边数.

有人可以解释一下吗？

简而言之,我的天真代码(在Ruby中)看起来像:

# $seen is a hash to memoize previously seen sets
# $sparse is a hash of usernames to a list of neighboring usernames
# $set is the list of output clusters

$seen = {}
def subgraph(set, adj)
    hash = (set + adj).sort
    return if $seen[hash]
    $sets.push set.sort.join(", ") if adj.empty? and set.size > 2
    adj.each {|node| subgraph(set + [node], $sparse[node] & adj)}
    $seen[hash] = true
end

$sparse.keys.each do |vertex|
    subgraph([vertex], $sparse[vertex])
end

我的Bron Kerbosch实施:

def bron_kerbosch(set, points, exclude)
    $sets.push …

给定一个布尔值的2D数组,我想找到包含至少2列和至少2行的所有模式.问题与图中的派系有些接近.

在下面的示例中,绿色单元格表示"真实"位,灰色表示"假".模式1包含cols 1,3,4和5以及行1和2.模式2仅包含第2列和第4列以及第2,3,4行.

这背后的商业理念是在各种社交网络用户群之间找到相似性模式.在现实世界中,行数最多可达3E7,列数最多可达300.

除了蛮力匹配之外,无法找到解决方案.

请告知问题的正确名称,以便我可以阅读更多内容,或建议优雅的解决方案.

一种快速算法,用于在完美图形中找到最大团的大小(这个具有至少1个和弦的奇数周期),具有大约100个顶点？

还有比蛮力更简单的方法,因为这是一个完美的图形,应该有一个多项式时间解决方案.但我无法找到算法.

贪婪着色是否能在所有完美图形中实现最佳着色？

对于大学项目,我正在尝试实施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 …

我正在研究基于R中的跟随者关系的Twitter网络.在这个网络中,我想确定每个人中最大的团队的大小,可以在他或她的时间线中读取彼此的推文.因此我需要maximum.cliques.但是这个功能忽略了方向性.我知道它没有集成在igraph包中,但是有没有办法在有向网络中找到派系,每个节点都是主动和被动地相互连接的？

我有一个网络,我想受集团约束,但我还没有弄清楚如何正确地做到这一点.我能够使用k-cores执行相同的过程,但不确定创建仅包含clique的图形的正确过程.

我希望如果我使用该k_core函数显示我的查找子图的过程,有人可以帮助我改变我的过程以使用该clique函数查找子图.

首先,我创建一个图表,我将使用空手道俱乐部:

In [1]: import networkx as nx

In [2]: g = nx.karate_club_graph()

在iPython中绘制图表:

In [3]: pylab inline
Populating the interactive namespace from numpy and matplotlib

In [4]: nx.draw(g)

接下来,我找到4核内的所有边(有4个或更多边):

In [5]: g_4k_edges = nx.k_core(g, k=4).edges()

将这些边添加到新图:

In [6]: g_4k = nx.Graph()
In [7]: g_4k.add_edges_from(g_4k_edges)

绘制4核图:

In [8]: nx.draw(g_4k)

关于如何做到这一点的任何想法,但不是使用k核来绑定网络,而是使用具有4个或更多顶点的派系？