networkx - clique, max independent set

What is Clique?

• clique는 maximal complete subgraph(모든 node pair 간에 edge가 있는 subgraph)라고 생각하시면 됩니다. ㅇ
• 가령, 노드 A, B, C가 있을 때, 서로 모두 연결되어 있다면(edge), 이는 3-clique가 되는 것이죠. 그래도 상대적으로 크기가 3인 clique는 쉬운 편인데, 커질수록, 충족해야 하는 edge의 수가 급증하므로, 매우 어려워지죠.

Large Clique in NetworkX

• Networkx에서는 다음의 3가지 정도의 함수를 제공합니다.
  • max_clique(G): 가장 큰 크기의 clique(Maximum Clique)를 approximation 방법으로 찾음.
  • clique_removal(G): approx. maximal clique를 순차적으로 제거하면서, Max Independet Set(가장 서로 인접하지 않은 노드의 집합, 다시 말하면, 이 안의 어떤 노드도 인접하지 않고 그래프에서 뽑을 수 있는 가장 큰 노드 집합)를 찾는 함수를 말합니다. 즉, clique에 속해 있다기 보다는 Max Independet Set를 찾기 위한 목적이 더 크죠.
  • large_clique_size(G): 현재 graph에서 가장 큰 크기의 clique의 clique를 리턴합니다. heuristic이며, 따라서 이 값이 아주 정확하다고 할 수는 없습니다.
• 사실, clique를 처리하는 것을 approximation이나 heuristic으로 처리하는 것은 그래프의 크기가 커질수록, clique를 도출하는 것이 어려워지기 때문이겠죠. 전문적으로 말하자면, NP-complete이니, NP-hard이니 하는데, 이건 매번 헷갈리는 것 같아요 제가 호호호.

Do it.

• 아무튼, python으로 간단히 코딩하였으며 코드와 결과는 다음과 같습니다.

import networkx as nx
from networkx.algorithms.approximation import clique
import time

import matplotlib.pyplot as plt


N = 50
p = 0.4
G = nx.fast_gnp_random_graph(N, p, seed=0)
#G = nx.petersen_graph()


print("==" * 30)
########################################
# clique.max_clique(G)
# :찾을 수 있는 가장 큰 크기의 max_clique(max_clique)를 approximation algorithm으로 찾음
max_cliq_approx = clique.max_clique(G)
print(f"max clique(approximation): {max_cliq_approx}")

########################################
# clique.large_clique_size(G)
# heuristic 이며 정확도를 보장하기는 어려움.
print("--" * 30)
print(f"len(max_cliq_approx): {len(max_cliq_approx)}")
max_clique_s = clique.large_clique_size(G)
print(f"max_clique_size(heuristic): {max_clique_s}")
print("--" * 30)

########################################
# clique.clique_removal(G)
# max_independent_set(서로 인접하지 않게 선정한 가장 많은 노드 집합)을 뽑는 함수에 가까움.
# maximal_clique를 순차적으로 그래프에서 제거하면서, max_independent_set를 찾음
# 즉, 같은 maximal_clique에 함께 존재하는 노드들은 동시에 max_independent_set에 속할 수 없음
# 따라서, 서로 다른 clique에 속하는 노드들간의 조합으로부터 max independet set를 뽑아낼 수 있음.
max_independent_set, remove_maximal_clique_ls = clique.clique_removal(G)
G_cp = G.copy()
print(f"== max_independent_set: {max_independent_set}")
print("== remove clique")
for i, remove_cliq in enumerate(remove_maximal_clique_ls):
    if False:# Draw figure
        plt.figure()
        nx.draw_networkx(G, pos=nx.spring_layout(G))
        plt.savefig(f"pic_{i}.png")
    ## draw complete
    G_cp.remove_nodes_from(remove_cliq)
    print(f"""{i:2d} == remove {remove_cliq}""")
print("=="*30)

============================================================
max clique(approximation): {10, 19, 13, 31}
------------------------------------------------------------
len(max_cliq_approx): 4
max_clique_size(heuristic): 6
------------------------------------------------------------
== max_independent_set: {0, 1, 2, 9, 13, 46, 14}
== remove clique
 0 == remove {16, 33, 0, 7}
 1 == remove {1, 34, 5, 21, 24}
 2 == remove {17, 2, 35, 22}
 3 == remove {38, 3, 4, 14}
 4 == remove {8, 32, 12, 6}
 5 == remove {40, 25, 9, 15}
 6 == remove {10, 28, 37, 47}
 7 == remove {27, 18, 19, 13}
 8 == remove {11, 36, 31}
 9 == remove {41, 44, 20}
10 == remove {43, 46, 23}
11 == remove {49, 26}
12 == remove {42, 29}
13 == remove {30, 39}
14 == remove {48, 45}
============================================================

reference

• https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.clique.max_clique.html#networkx.algorithms.approximation.clique.max_clique