1. Học hỏi
    2. /
  2. Khoa Học
    3. /
  3. Nhập môn Phân tích Mạng bằng Python
Connected

Bài tập

Tìm tất cả maximal clique có kích thước "n"

Bây giờ bạn đã khám phá tam giác (và tam giác mở), hãy chuyển sang khái niệm maximal clique. Maximal clique là những clique không thể mở rộng thêm bằng cách bổ sung một cạnh kề, và là một thuộc tính hữu ích của đồ thị khi tìm cộng đồng. NetworkX cung cấp một hàm cho phép bạn xác định các nút tham gia vào mỗi maximal clique trong một đồ thị: nx.find_cliques(G). Hãy thử nghiệm hàm này với T trong IPython Shell, rồi quay lại trả lời bài tập.

Hướng dẫn

100 XP
  • Viết một hàm maximal_cliques() có hai tham số - G và size - để tìm tất cả các maximal clique có kích thước n.
    • Trong vòng lặp for, duyệt qua tất cả các clique trong G bằng hàm nx.find_cliques().
    • Nếu clique hiện tại có kích thước bằng size, hãy thêm nó vào danh sách mcs.
  • Dùng một câu lệnh assert và hàm maximal_cliques() của bạn để kiểm tra rằng có 33 maximal clique có kích thước 3 trong đồ thị T.