Максимальні кліки

Вступ до аналізу мереж у Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Максимальні кліки

Визначення: кліка, яка при додаванні ще одного вузла вже не є клікою

Граф із п'яти вузлів. Чотири вузли утворюють кліку: кожен з'єднаний з усіма іншими. Три вузли кліки підсвічено зеленим. П'ятий вузол з'єднаний лише з одним іншим.

Максимальні кліки

Визначення: кліка, яка при додаванні ще одного вузла вже не є клікою

Той самий граф із п'яти вузлів. Цього разу всі чотири вузли кліки підсвічено зеленим.

Максимальні кліки

Застосування: пошук спільнот

Той самий граф із п'яти вузлів.

Спільноти

Знайдіть кліки
Знайдіть об'єднання клік

Той самий граф із п'яти вузлів.

NetworkX API

find_cliques знаходить усі максимальні кліки

Максимальні кліки

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]]

Максимальні кліки

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]]

Два графи, у кожному по п'ять вузлів, що утворюють максимальні кліки.

Максимальні кліки

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