Максимальные клики

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

Eric Ma

Data Carpentry instructor and author of nxviz package

Максимальные клики

  • Определение: клика, которая при добавлении одного узла перестаёт быть кликой

Граф из пяти узлов. Четыре узла образуют клику: каждый соединён со всеми остальными. Три из них выделены зелёным. Пятый узел соединён только с одним другим узлом.

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

Максимальные клики

  • Определение: клика, которая при добавлении одного узла перестаёт быть кликой

Тот же граф из пяти узлов. На этот раз все четыре узла клики выделены зелёным.

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

Максимальные клики

  • Применение: поиск сообществ

Тот же граф из пяти узлов.

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

Сообщества

  • Поиск клик
  • Поиск объединений клик

Тот же граф из пяти узлов.

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

API NetworkX

  • find_cliques находит все максимальные клики
Введение в анализ сетей на Python

Максимальные клики

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)

nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

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

Максимальные клики

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)
nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

Два графа, каждый из пяти узлов, образующих максимальные клики.

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

Максимальные клики

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)
nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

Четыре графа: два графа из пяти узлов-клик и два новых графа, каждый из двух узлов, соединённых ребром.

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

Давайте потренируемся!

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

Preparing Video For Download...