Maximale Cliquen

Einstieg in die Netzwerkanalyse mit Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Maximale Cliquen

  • Definition: eine Clique, die beim Erweitern um einen Knoten keine Clique mehr ist

Ein Graph mit fünf Knoten. Vier Knoten bilden eine Clique: Jeder ist mit allen anderen verbunden. Drei dieser Knoten sind grün markiert. Der fünfte Knoten ist nur mit einem anderen verbunden.

Einstieg in die Netzwerkanalyse mit Python

Maximale Cliquen

  • Definition: eine Clique, die beim Erweitern um einen Knoten keine Clique mehr ist

Der gleiche Graph mit fünf Knoten. Diesmal sind alle vier Knoten der Clique grün markiert.

Einstieg in die Netzwerkanalyse mit Python

Maximale Cliquen

  • Anwendungen: Community-Erkennung

Der gleiche Graph mit fünf Knoten.

Einstieg in die Netzwerkanalyse mit Python

Communities

  • Cliquen finden
  • Vereinigungen von Cliquen finden

Der gleiche Graph mit fünf Knoten.

Einstieg in die Netzwerkanalyse mit Python

NetworkX-API

  • find_cliques findet alle maximalen Cliquen
Einstieg in die Netzwerkanalyse mit Python

Maximale Cliquen

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

Einstieg in die Netzwerkanalyse mit Python

Maximale Cliquen

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

Zwei Graphen, jeweils mit fünf Knoten, die maximale Cliquen bilden.

Einstieg in die Netzwerkanalyse mit Python

Maximale Cliquen

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 Graphen: die beiden Fünf-Knoten-Cliquen von zuvor plus zwei neue Graphen mit je zwei durch eine Kante verbundenen Knoten.

Einstieg in die Netzwerkanalyse mit Python

Lass uns üben!

Einstieg in die Netzwerkanalyse mit Python

Preparing Video For Download...