Maximale cliques

Introductie tot netwerkanalyse in Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Maximale cliques

Definitie: een clique die, zodra je één knoop toevoegt, geen clique meer is

Een graaf met vijf knopen. Vier knopen vormen een clique: elke knoop is met alle andere verbonden. Drie knopen in de clique zijn groen gemarkeerd. De vijfde knoop is slechts met één andere verbonden.

Maximale cliques

Definitie: een clique die, zodra je één knoop toevoegt, geen clique meer is

Dezelfde graaf met vijf knopen. Nu zijn de vier knopen in de clique allemaal groen gemarkeerd.

Maximale cliques

Toepassingen: community-detectie

Dezelfde graaf met vijf knopen.

Communities

Vind cliques
Vind unies van cliques

Dezelfde graaf met vijf knopen.

NetworkX-API

find_cliques vindt alle maximale cliques

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

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

Twee grafen, elk met vijf knopen die maximale cliques vormen.

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

Vier grafen: de twee vijfknopencliques van eerder, plus twee nieuwe grafen met telkens twee knopen verbonden door een rand.

Laten we oefenen!

Introductie tot netwerkanalyse in Python