브론-케르보쉬 알고리즘

Bron–Kerbosch algorithm

Bron-Kerbosch 알고리즘은 컴퓨터 과학에서 방향이 없는 그래프에서 모든 최대 클리크를 찾기 위한 열거 알고리즘입니다. 즉, 나열된 부분 집합 중 하나에 있는 각 정점 쌍이 에지로 연결된 두 개의 속성을 가진 정점의 모든 부분 집합이 나열되며, 나열된 부분 집합 중 어떤 것도 완전한 연결을 유지하면서 추가 정점을 추가할 수 없습니다. 브론-케르보쉬 알고리즘은 1973년에 그 설명을 발표한 네덜란드 과학자 코엔라드 브론과 조프 케르보쉬에 의해 설계되었습니다.

클릭 문제를 해결하기 위한 다른 알고리즘은 이론적으로 최대 독립 집합이 거의 없는 입력에서 더 나은 실행 시간을 가지고 있지만, 브론-케르보쉬 알고리즘과 이에 대한 후속 개선은 대안보다 실제로 더 효율적이라고 자주 보고됩니다.[1] 전산화학과 같은 그래프 알고리즘의 응용 분야에 잘 알려져 있고 널리 사용되고 있습니다.[2]

Akkoyunlu(1973)의 동시대 알고리즘은 다른 용어로 제시되지만 동일한 검색 트리를 생성하기 때문에 브론-Kerbosch 알고리즘과 동일한 것으로 볼 수 있습니다.[3]

피벗하지 않고

브론-케르보쉬 알고리즘의 기본 형태는 주어진 그래프 G에서 모든 최대 클리크를 찾는 재귀적 역추적 알고리즘입니다. 더 일반적으로, 세 개의 서로소인 정점 R, P, X 집합이 주어졌을 때, R의 모든 정점을 포함하고, P의 일부 정점을 포함하고, X의 정점을 포함하지 않는 최대 클리크를 찾습니다. 알고리즘에 대한 각 호출에서 P와 X는 R에 추가될 때 클리크를 형성하는 정점으로 구성된 서로소 집합입니다. 즉, P ∪ X는 R의 모든 원소에 연결된 정점들의 집합입니다. P와 X가 둘 다 비어 있을 때 R에 더 이상 추가할 수 있는 요소가 없으므로 R은 최대 클릭이고 알고리즘은 R을 출력합니다.

R과 X를 빈 집합으로 설정하고 P를 그래프의 정점 집합으로 설정하여 재귀를 시작합니다. 각 재귀 호출 내에서 알고리즘은 P의 정점을 차례로 고려합니다. 그러한 정점이 없으면 R을 최대 클릭(X가 비어 있는 경우)으로 보고하거나 역추적합니다. P에서 선택한 각 정점 v에 대해 v가 R에 추가되고 P와 X가 v의 이웃 집합 N(v)으로 제한되는 재귀적 호출을 수행하며, 이는 v를 포함하는 R의 모든 클리크 확장을 찾아 보고합니다. 그런 다음 v를 P에서 X로 이동하여 향후 클리크에서 고려 대상에서 제외하고 P의 다음 정점으로 계속 진행합니다.

즉, 의사 코드에서 알고리즘은 다음 단계를 수행합니다. 

알고리즘 BronKerbosch1(R, P, X)은 P와 X가 모두 비어 있는 경우 P의 각 정점 v에 대한 최대 클릭으로 R을 보고합니다. P ⋂ N(v), X ⋂ N(v) P:= P \ {v} X : = X ⋃ {v}

피벗과 함께

위에서 설명한 알고리즘의 기본 형태는 최대 또는 그렇지 않은 모든 클릭에 대해 재귀적 호출을 수행하는 비 최대 클리크가 많은 그래프의 경우 비효율적입니다. 시간을 절약하고 알고리즘이 최대 클리크를 포함하지 않는 검색 분기에서 더 빨리 역추적할 수 있도록 브론과 케르보쉬는 P에서 선택된 "피봇 정점" u를 포함하는 알고리즘의 변형을 도입했습니다.[4] 모든 최대 클릭은 u 또는 비이웃 중 하나를 포함해야 합니다. 그렇지 않으면 클릭에 u를 추가하여 클릭을 확장할 수 있습니다. 따라서 알고리즘에 대한 각 재귀 호출에서 R에 추가되는 정점 v에 대한 선택으로 u와 그 비이웃만 검정하면 됩니다. 의사 코드에서: 

알고리즘 BronKerbosch2(R, P, X)는 P와 X가 모두 비어 있는 경우 R을 최대 클릭으로 보고하고 P의 각 정점 v에 대한 P ⋃ X의 피벗 정점 u를 선택합니다. P \ N(u) do BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v) P : = P \ {v} X : = X ⋃ {v}

피벗을 선택하여 알고리즘에 의한 재귀 호출 수를 최소화하면 비피벗 버전의 알고리즘에 비해 실행 시간을 크게 절약할 수 있습니다.[5]

꼭짓점 순서 지정을 사용하여

브론-케르보쉬 알고리즘의 기본 형태를 개선하기 위한 대안적인 방법은 가장 바깥쪽 재귀 수준에서 피벗하는 것을 포기하고 대신 재귀 호출의 순서를 신중하게 선택하여 각 재귀 호출 내에서 후보 정점 집합 P의 크기를 최소화하는 것입니다.

그래프 G의 축퇴는 가장 작은 수 d이므로 G의 모든 부분 그래프는 d 이하의 차수를 갖는 정점을 갖습니다. 모든 그래프에는 축퇴 순서가 있는데, 각 정점이 순서 뒤에 오는 이웃 수가 d 이하가 되도록 정점 순서가 있습니다. 축퇴 순서는 나머지 정점 중 최소 차수의 정점을 반복적으로 선택하여 선형 시간에서 찾을 수 있습니다. Bron-Kerbosch 알고리즘이 루프를 통과하는 정점 v의 순서가 축퇴 순서라면, 각 호출의 후보 정점 집합 P(순서 뒤에 있는 v의 이웃)는 최대 d의 크기를 갖도록 보장됩니다. 제외된 정점의 집합 X는 v의 모든 이전 이웃으로 구성되며 d보다 훨씬 클 수 있습니다. 재귀의 최상위 레벨 아래의 알고리즘에 대한 재귀 호출에서는 피벗 버전을 계속 사용할 수 있습니다.[6][7]

의사 코드에서 알고리즘은 다음 단계를 수행합니다. 

알고리즘 BronKerbosch3(G)는 Gdo BronKerbosch2({v), P ⋂ N(v), X ⋂ N(v) P:= P \ {v} X:= X ⋃ {v}

이 변형된 알고리즘은 작은 퇴행성 그래프에 효율적인 것으로 입증될 수 있으며,[6] 실험에 따르면 대규모 희소 소셜 네트워크 및 기타 실제 그래프에도 실제로 잘 작동하는 것으로 나타났습니다.[7]

예

최대 5개의 클리크가 있는 그래프: 네 개의 간선과 삼각형

표시된 예제 그래프에서 알고리즘은 처음에 R = Ø, P = {1,2,3,4,5,6} 및 X = Ø로 호출됩니다. 피벗 u는 재귀 호출 수를 최소화하기 위해 차수 3 정점 중 하나로 선택되어야 합니다. 예를 들어, u를 정점 2로 선택했다고 가정합니다. 그러면 P \ N(u)에는 나머지 3개의 정점이 있습니다: 정점 2, 4, 6.

v = 2에 대한 알고리즘의 내부 루프의 반복은 R = {2}, P = {1,3,5}, X = Ø를 갖는 알고리즘에 재귀적 호출을 수행합니다. 이 재귀적 호출 내에서 1 또는 5 중 하나가 피벗으로 선택되며, 하나는 정점 3에 대한 호출이고 다른 하나는 정점이 피벗으로 선택되지 않은 경우에 대한 호출입니다. 이 두 개의 통화는 결국 {1,2,5} 및 {2,3} 두 개의 클리크를 보고합니다. 이러한 재귀적 호출에서 돌아온 후, 정점 2는 X에 추가되고 P에서 제거됩니다.

v = 4에 대한 알고리즘의 내부 루프의 반복은 R = {4}, P = {3,5,6} 및 X Ø를 사용하여 알고리즘에 재귀적 호출을 수행합니다(비록 정점 2는 알고리즘에 대한 외부 호출에서 집합 X에 속하지만 v의 이웃이 아니며 재귀적 호출에 전달된 X의 부분 집합에서 제외됩니다). 이 재귀적 호출은 {3,4}, {4,5}, {4,6} 세 개의 클리크를 보고하는 알고리즘에 세 번째 수준의 재귀적 호출을 수행하게 됩니다. 그런 다음, 정점 4는 X에 추가되고 P에서 제거됩니다.

알고리즘의 내부 루프의 세 번째이자 마지막 반복에서 v = 6의 경우 R = {6}, P = Ø 및 X = {4}인 알고리즘에 대한 재귀적 호출이 있습니다. 이 재귀 호출은 P가 비어 있고 X가 비어 있지 않기 때문에 더 이상의 클리크를 보고하지 않고 즉시 역추적합니다. 왜냐하면 정점 6을 포함하고 정점 4를 제외하는 최대 클리크는 있을 수 없기 때문입니다.

따라서 알고리즘의 호출 트리는 다음과 같습니다. 

브론케르보쉬2(Ø, {1,2,3,4,5,6}, Ø) 브론케르보쉬2({2,3,5}, Ø) 출력: {2,3} 브론케르보쉬2({2,5}, Ø, Ø) 출력: {2,3} 브론케르보쉬2({2,5},{1,5}, Ø) 출력: {1,2,5} 브론케르보쉬2({4},{3,5,6}, Ø) 출력: {3,4} 브론케르보쉬2({3,4}, Ø) 출력: {3,4} 브론케르보쉬2({4,5}, Ø, Ø) 출력: {4,5} 브론케르보쉬2({4,5}, Ø) 출력: {4,5}5} BronKerbosch2({4,6}, Ø, Ø): 출력 {4,6} BronKerbosch2({6}, Ø, {4}): 출력 없음

예제의 그래프는 퇴행성 2를 가지고 있습니다. 하나의 가능한 퇴행성 순서는 6,4,3,1,2,5입니다. Bron-Kerbosch 알고리즘의 정점 순서화 버전을 정점에 적용하면, 이 순서에서 호출 트리는 다음과 같이 보입니다. 

브론케르보쉬3(G) 브론케르보쉬2({6,4}, Ø) 브론케르보쉬2({6,4}, Ø): 출력 {6,4} 브론케르보쉬2({4,{3,5},{6}) 브론케르보쉬2({4,3}, Ø): 출력 {4,3} 브론케르보쉬2({4,5}, Ø): 출력 {4,5} 브론케르보쉬2({3,2},{4}) 브론케르보쉬2({3,2}, Ø): 출력 {3,2} 브론케르보쉬2({3,2}, Ø): 출력 {3,2} 브론케르보쉬2({1},{2,5}, Ø) BronKerbosch2({1,2}, {5}, Ø) BronKerbosch2({1,2,5}, Ø, Ø): 출력 {1,2,5} BronKerbosch2({2},{5},{1,3}): 출력 없음 BronKerbosch2({5}, Ø,{1,2,4}): 출력 없음

최악의 경우 분석

브론-케르보쉬 알고리즘은 출력에 민감한 알고리즘이 아닙니다. 클릭 문제에 대한 다른 알고리즘과 달리 최대 클릭당 다항 시간 내에 실행되지 않습니다. 그러나 Moon & Moser(1965)의 결과로 모든 n-vertex 그래프는 최대 3개의n/3 최대 클리크를 가지며 브론-Kerbosch 알고리즘(각 단계에서 재귀 호출 수를 최소화하는 피벗 전략)의 최악의 실행 시간은 O(3n/3)이며 이 경계와 일치합니다.[8]

희소 그래프의 경우 더 엄격한 경계가 가능합니다. 특히 Bron-Kerbosch 알고리즘의 정점 순서화 버전은 O(dn3d/3) 시간에 실행되도록 만들 수 있으며, 여기서 d는 그래프의 퇴화, 희소성의 척도입니다. 최대 클리크의 총 수가 (n - dd/3)3인 기존 축퇴 그래프가 있으므로 이 경계는 촘촘합니다.[6]

메모들

  1. ^ Cazals & Karande (2008).
  2. ^ 첸(2004).
  3. ^ 존스턴 (1976).
  4. ^ 토미타, 다나카 & 타카하시 (2006); 카잘스 & 카란데 (2008).
  5. ^ 존스턴(1976), 코흐(2001), 카잘스 & 카란데(2008).
  6. ^ a b c Eppstein, Löffler & Strash (2010).
  7. ^ a b Eppstein & Strash (2011).
  8. ^ 토미타, 다나카 & 타카하시 (2006).

참고문헌

  • Akkoyunlu, E. A. (1973), "The enumeration of maximal cliques of large graphs", SIAM Journal on Computing, 2: 1–6, doi:10.1137/0202001.
  • Chen, Lingran (2004), "Substructure and maximal common substructure searching", in Bultinck, Patrick (ed.), Computational Medicinal Chemistry for Drug Discovery, CRC Press, pp. 483–514, ISBN 978-0-8247-4774-9.
  • Bron, Coen; Kerbosch, Joep (1973), "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM, 16 (9): 575–577, doi:10.1145/362342.362367.
  • Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010.
  • Eppstein, David; Löffler, Maarten; Strash, Darren (2010), "Listing all maximal cliques in sparse graphs in near-optimal time", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, vol. 6506, Springer-Verlag, pp. 403–414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36, S2CID 10918411.
  • Eppstein, David; Strash, Darren (2011), "Listing all maximal cliques in large sparse real-world graphs", 10th International Symposium on Experimental Algorithms, arXiv:1103.0318, Bibcode:2011arXiv1103.0318E.
  • Johnston, H. C. (1976), "Cliques of a graph—variations on the Bron–Kerbosch algorithm", International Journal of Parallel Programming, 5 (3): 209–238, doi:10.1007/BF00991836, S2CID 29799145.
  • Koch, Ina (2001), "Enumerating all connected maximal common subgraphs in two graphs", Theoretical Computer Science, 250 (1–2): 1–30, doi:10.1016/S0304-3975(00)00286-3.
  • Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577.
  • Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015.

외부 링크