稍微研究了一下，我发现这就是图论中所谓的最大独立集问题，不幸的是NP-hard。
图 G的独立集S 是 G 的顶点的子集，因此 S 中没有顶点彼此相邻。在我们的例子中，我们正在寻找一个最大独立集（MIS），即具有最大可能顶点数的独立集。
有几个库用于处理图和网络，例如igraph或NetworkX，它们具有查找最大独立集的功能。我最终使用了 igraph。
对于我的问题，我们可以将图像视为图 G 的顶点，将“相似矩阵”视为邻接矩阵：
images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']
sm = np.array([[1, 1, 1, 0, 1],
[1, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 1]])
# Adjacency matrix
adj = sm.copy()
np.fill_diagonal(adj, 0)
# Create the graph
import igraph
g = igraph.Graph.Adjacency(adj.tolist(), mode='UNDIRECTED')
# Find the maximum independent sets
g.largest_independent_vertex_sets()
[(1, 2, 3), (2, 3, 4)]
不幸的是，这对于成千上万的图像（顶点）来说太慢了。所以我仍然愿意接受有关更快方法的建议（也许不是找到所有的 MIS，而是找到一个）。
注意：@Sergey (UPDATE#1) 和 @marke 提出的解决方案并不总是返回 MIS——它们是贪婪的近似算法，会删除最大度数的顶点，直到没有边缘。为了证明这一点，请考虑以下示例：
sm = np.array([[1, 1, 0, 0, 0, 1],
[1, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[1, 0, 0, 0, 1, 1]])
两种解决方案都返回[3, 5]，但对于此示例，最大独立集是两个 ，[(0, 3, 4), (1, 2, 5)]由 正确找到igraph。np.argmax要了解为什么这些解决方案无法找到 MIS，下面是一个 gif，它显示了如何在每次迭代中删除顶点和边（这是返回多次出现最大值的第一次出现的“副作用” ）：
Sergey 的解决方案（UPDATE#2）似乎有效，但它比 igraph 的largest_independent_vertex_sets(). 对于速度比较，您可以使用以下随机生成的长度为 100 的相似度矩阵：
a = np.random.randint(2, size=(100, 100))
# create a symmetric similarity matrix
sm = np.tril(a) + np.tril(a, -1).T
np.fill_diagonal(sm, 1)
# create adjacency matrix for igraph
adj = sm.copy()
np.fill_diagonal(adj, 0)
更新：事实证明，虽然我有数千个图像 - 顶点，但边的数量相对较少（即我有一个稀疏图），因此使用 igraph 查找 MIS 是可以接受的它的速度。或者，作为一种折衷方案，可以使用贪婪的近似算法来找到一个大的独立集（如果足够幸运，也可以使用 MIS）。下面是一个看起来相当快的算法：
def independent_set(adj):
'''
Given adjacency matrix, returns an independent set
of size >= np.sum(1/(1 + adj.sum(0)))
'''
adj = np.array(adj, dtype=bool).astype(np.uint8)
np.fill_diagonal(adj, 1) # for the purposes of algorithm
indep_set = set(range(len(adj)))
# Loop until no edges remain
while adj.sum(0).max() > 1:
degrees = adj.sum(0)
# Randomly pick a vertex v of max degree
v = random.choice(np.where(degrees == degrees.max())[0])
# "Remove" the vertex v and the edges to its neigbours
adj[v, :], adj[:, v] = 0, 0
# Update the maximal independent set
indep_set.difference_update({v})
return indep_set
或者更好的是，我们可以得到一个最大的独立集：
def maximal_independent_set(adj):
adj = np.array(adj, dtype=bool).astype(np.uint8)
degrees = adj.sum(0)
V = set(range(len(adj))) # vertices of the graph
mis = set() # maximal independent set
while V:
# Randomly pick a vertex of min degree
v = random.choice(np.where(degrees == degrees.min())[0])
# Add it to the mis and remove it and its neighbours from V
mis.add(v)
Nv_c = set(np.nonzero(adj[v])[0]).union({v}) # closed neighbourhood of v
V.difference_update(Nv_c)
degrees[list(Nv_c)] = len(adj) + 1
return mis