Cliques máximas

Introducción al análisis de redes en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Cliques máximas

Definición: una clique que, al añadir un nodo, deja de ser clique

Un grafo con cinco nodos. Cuatro nodos forman una clique: cada nodo está conectado con todos los demás. Tres de esos nodos están en verde. El quinto nodo solo está conectado a uno.

Cliques máximas

Definición: una clique que, al añadir un nodo, deja de ser clique

El mismo grafo con cinco nodos. Ahora, los cuatro nodos de la clique están en verde.

Cliques máximas

Aplicaciones: detección de comunidades

El mismo grafo con cinco nodos.

Comunidades

Encontrar cliques
Unir cliques

El mismo grafo con cinco nodos.

API de NetworkX

find_cliques encuentra todas las cliques máximas

Cliques máximas

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

Cliques máximas

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

Dos grafos; cada uno con cinco nodos que forman cliques máximas.

Cliques máximas

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

Cuatro grafos: las dos cliques de cinco nodos de antes y dos nuevos grafos con dos nodos unidos por una arista.

¡Vamos a practicar!

Introducción al análisis de redes en Python