Cliques maximales

Introduction à l’analyse de réseaux en Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Cliques maximales

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

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

Introduction à l’analyse de réseaux en Python

Cliques maximales

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

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

Introduction à l’analyse de réseaux en Python

Cliques maximales

  • Applications : détection de communautés

Le même graphe à cinq nœuds.

Introduction à l’analyse de réseaux en Python

Communautés

  • Trouver des cliques
  • Trouver des unions de cliques

Le même graphe à cinq nœuds.

Introduction à l’analyse de réseaux en Python

API NetworkX

  • find_cliques trouve toutes les cliques maximales
Introduction à l’analyse de 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 de 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 avec cinq nœuds formant des cliques maximales.

Introduction à l’analyse de 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’avant, plus deux nouveaux graphes composés chacun de deux nœuds reliés par une arête.

Introduction à l’analyse de réseaux en Python

Passons à la pratique !

Introduction à l’analyse de réseaux en Python

Preparing Video For Download...