Maximala klicker

Introduktion till nätverksanalys i Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Maximala klicker

Definition: en klick som inte längre är en klick om man lägger till ytterligare en nod

En graf med fem noder. Fyra noder bildar en klick: varje nod är kopplad till alla andra noder. Tre av noderna i klicken är markerade i grönt. Den femte noden är bara kopplad till en annan nod.

Maximala klicker

Definition: en klick som inte längre är en klick om man lägger till ytterligare en nod

Samma graf med fem noder. Den här gången är alla fyra noderna i klicken markerade i grönt.

Maximala klicker

Tillämpningar: identifiering av communities

Samma graf med fem noder.

Communities

Hitta klicker
Hitta unioner av klicker

Samma graf med fem noder.

NetworkX API

find_cliques hittar alla maximala klicker

Maximala klicker

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

Maximala klicker

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

Två grafer, vardera med fem noder som bildar maximala klicker.

Maximala klicker

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

Fyra grafer: de två femnodsklickerna från tidigare, plus två nya grafer med vardera två noder kopplade med en kant.

Nu kör vi en övning!

Introduktion till nätverksanalys i Python