НачатьНачать бесплатно

Поиск всех максимальных клик размера «n»

Теперь, когда вы изучили треугольники (и открытые треугольники), перейдём к концепции максимальных клик. Максимальные клики — это клики, которые нельзя расширить, добавив смежное ребро. Они полезны при поиске сообществ в графе. NetworkX предоставляет функцию для определения узлов, входящих в каждую максимальную клику графа: nx.find_cliques(G). Поэкспериментируйте с этой функцией, применив её к графу T в IPython Shell, а затем приступайте к выполнению упражнения.

Это упражнение является частью курса

Введение в анализ сетей на Python

Посмотреть курс

Инструкции к упражнению

  • Напишите функцию maximal_cliques() с двумя параметрами — G и size — которая находит все максимальные клики заданного размера n.
    • В цикле for выполните итерацию по всем кликам в G с помощью функции nx.find_cliques().
    • Если текущая клика имеет размер size, добавьте её в список mcs.
  • Используйте оператор assert и функцию maximal_cliques(), чтобы убедиться, что в графе T ровно 33 максимальные клики размером 3.

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

# Define maximal_cliques()
def ____:
    """
    Finds all maximal cliques in graph `G` that are of size `size`.
    """
    mcs = []
    for clique in ____:
        if ____ == ____:
            ____
    return mcs

# Check that there are 33 maximal cliques of size 3 in the graph T
assert ____ == ____
Редактировать и запускать код