1. 학습
    2. /
  2. 강의
    3. /
  3. Python으로 시작하는 네트워크 분석
Connected

연습 문제

크기가 "n"인 모든 최대 clique 찾기

이제 삼각형(그리고 열린 삼각형)까지 살펴보셨으니, 최대 clique 개념으로 넘어가 보겠습니다. 최대 clique는 인접한 간선을 더해 확장할 수 없는 clique를 말하며, 커뮤니티를 찾을 때 그래프의 유용한 속성입니다. NetworkX에는 그래프에서 각 최대 clique에 포함된 노드를 찾아주는 함수 nx.find_cliques(G)가 있습니다. IPython Shell에서 T에 대해 이 함수를 직접 사용해 보시고, 이어서 연습 문제를 풀어 보세요.

지침

100 XP
  • G와 size 두 매개변수를 받는 함수 maximal_cliques()를 작성해 크기가 n인 모든 최대 clique를 찾으세요.
    • for 반복문에서 nx.find_cliques() 함수를 사용해 G의 모든 clique를 순회하세요.
    • 현재 clique의 크기가 size이면 리스트 mcs에 추가하세요.
  • assert 문과 작성한 maximal_cliques() 함수를 사용해 그래프 T에 크기가 3인 최대 clique가 33개 있는지 확인하세요.