Clique massimali

Introduzione all'analisi delle reti in Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Clique massimali

Definizione: una clique che, se estesa di un nodo, non è più una clique

Un grafo con cinque nodi. Quattro formano una clique: ogni nodo è connesso a tutti gli altri. Tre dei nodi nella clique sono evidenziati in verde. Il quinto nodo è connesso a un solo nodo.

Clique massimali

Definizione: una clique che, se estesa di un nodo, non è più una clique

Lo stesso grafo con cinque nodi. Questa volta, i quattro nodi della clique sono tutti evidenziati in verde.

Clique massimali

Applicazioni: rilevamento comunità

Lo stesso grafo con cinque nodi.

Comunità

Trova le clique
Trova unioni di clique

Lo stesso grafo con cinque nodi.

API di NetworkX

find_cliques trova tutte le clique massimali

Clique massimali

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

Clique massimali

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

Due grafi, ciascuno con cinque nodi che formano clique massimali.

Clique massimali

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

Quattro grafi: le due clique da cinque nodi di prima, più due nuovi grafi con due nodi collegati da un arco.

Ayo berlatih!

Introduzione all'analisi delle reti in Python