Cliques maximales

Introduction à l'analyse des réseaux en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Cliques maximales

  • Définition : une clique qui, si on ajoute un nœud, n'est plus une clique

Un graphe de cinq nœuds. Quatre nœuds forment une clique : chaque nœud est relié à tous les autres. Trois nœuds de la clique sont en vert. Le cinquième nœud n'est relié qu'à un seul autre nœud.

Introduction à l'analyse des réseaux en Python

Cliques maximales

  • Définition : une clique qui, si on ajoute un nœud, n'est plus une clique

Le même graphe de cinq nœuds. Cette fois, les quatre nœuds de la clique sont tous en vert.

Introduction à l'analyse des réseaux en Python

Cliques maximales

  • Applications : détection de communautés

Le même graphe de cinq nœuds.

Introduction à l'analyse des réseaux en Python

Communautés

  • Repérer les cliques
  • Regrouper les cliques

Le même graphe de cinq nœuds.

Introduction à l'analyse des réseaux en Python

API NetworkX

  • find_cliques trouve toutes les cliques maximales
Introduction à l'analyse des réseaux en Python

Cliques maximales

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

Introduction à l'analyse des réseaux en Python

Cliques maximales

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

Deux graphes ; chacun compte cinq nœuds formant des cliques maximales.

Introduction à l'analyse des réseaux en Python

Cliques maximales

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

Quatre graphes : les deux cliques de cinq nœuds déjà vues, plus deux nouveaux graphes composés chacun de deux nœuds reliés par une arête.

Introduction à l'analyse des réseaux en Python

Passons à la pratique !

Introduction à l'analyse des réseaux en Python

Preparing Video For Download...