Kliki maksymalne

Wprowadzenie do analizy sieci w Pythonie

Eric Ma

Data Carpentry instructor and author of nxviz package

Kliki maksymalne

Definicja: klika, która po dodaniu jednego węzła przestaje być kliką

Graf z pięcioma węzłami. Cztery węzły tworzą klikę — każdy jest połączony z pozostałymi. Trzy węzły kliki są zaznaczone na zielono. Piąty węzeł jest połączony tylko z jednym węzłem.

Kliki maksymalne

Definicja: klika, która po dodaniu jednego węzła przestaje być kliką

Ten sam graf z pięcioma węzłami. Tym razem wszystkie cztery węzły kliki są zaznaczone na zielono.

Kliki maksymalne

Zastosowania: wykrywanie społeczności

Ten sam graf z pięcioma węzłami.

Społeczności

Znajdowanie klik
Znajdowanie sum klik

Ten sam graf z pięcioma węzłami.

API NetworkX

find_cliques znajduje wszystkie kliki maksymalne

Kliki maksymalne

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

Kliki maksymalne

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

Dwa grafy, w każdym pięć węzłów tworzących kliki maksymalne.

Kliki maksymalne

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

Cztery grafy: dwie pięciowęzłowe kliki oraz dwa nowe grafy złożone z dwóch węzłów połączonych krawędzią.

Czas na ćwiczenia!

Wprowadzenie do analizy sieci w Pythonie