Maximální kliky

Úvod do analýzy sítí v Pythonu

Eric Ma

Data Carpentry instructor and author of nxviz package

Maximální kliky

Definice: klika, která po přidání jednoho uzlu přestane být klikou

Graf s pěti uzly. Čtyři uzly tvoří kliku: každý je spojen se všemi ostatními. Tři uzly kliky jsou zvýrazněny zeleně. Pátý uzel je spojen pouze s jedním uzlem.

Maximální kliky

Definice: klika, která po přidání jednoho uzlu přestane být klikou

Stejný graf s pěti uzly. Tentokrát jsou všechny čtyři uzly kliky zvýrazněny zeleně.

Maximální kliky

Aplikace: detekce komunit

Stejný graf s pěti uzly.

Komunity

Nalezení klik
Nalezení sjednocení klik

Stejný graf s pěti uzly.

NetworkX API

find_cliques nalezne všechny maximální kliky

Maximální kliky

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

Maximální kliky

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

Dva grafy, každý s pěti uzly tvořícími maximální kliky.

Maximální kliky

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

Čtyři grafy: dvě pětičlenné kliky z předchozího slide a dva nové grafy, každý se dvěma uzly spojenými hranou.

Lass uns üben!

Úvod do analýzy sítí v Pythonu