Cliques maximais

Introdução à Análise de Redes em Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Cliques maximais

Definição: uma clique que, ao adicionar um nó, deixa de ser clique

Um grafo com cinco nós. Quatro formam uma clique: cada nó conecta a todos os outros. Três desses nós estão em verde. O quinto nó conecta-se a apenas um nó.

Cliques maximais

Definição: uma clique que, ao adicionar um nó, deixa de ser clique

O mesmo grafo com cinco nós. Agora, os quatro nós da clique estão em verde.

Cliques maximais

Aplicações: detecção de comunidades

O mesmo grafo com cinco nós.

Comunidades

Encontrar cliques
Unir cliques

O mesmo grafo com cinco nós.

API do NetworkX

find_cliques encontra todas as cliques maximais

Cliques maximais

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 maximais

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

Dois grafos; cada um com cinco nós formando cliques maximais.

Cliques maximais

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

Quatro grafos: os dois cliques de cinco nós anteriores, mais dois com dois nós ligados por uma aresta.

Vamos praticar!

Introdução à Análise de Redes em Python