4  Partitionner

4.1 Cliques et k-cores

La page de la documentation consacrée aux cliques propose x fonctions dont plusieurs sont obsolotètes. Par défaut, NetworkX renvoit tous les ous-graphes complets d’ordre 1 à n, n correspondant au sous-graphe maximal complet et donc à la clique au sens strict du terme.

# cliques d'ordre 1 à n
print("Nombre de `cliques' : ", sum(1 for c in nx.find_cliques(GU)))
print("Nombre de sommets dans la plus grande clique : ", max(len(c) for c in nx.find_cliques(GU)))
print("Composition de la plus grande clique \n", max(nx.find_cliques(GU), key=len))
Nombre de `cliques' :  86
Nombre de sommets dans la plus grande clique :  10
Composition de la plus grande clique 
 ['13001', '13213', '13201', '13206', '13205', '13209', '13212', '13208', '13211', '13210']

Nombre de variations des k-cores sont proposées (k-shell, k-crust, k-corona…), elles seront abordées dans une version ultérieure de ce tutoriel.

# ordre des k-cores
print(list(nx.k_components(GU)))

# composition du 8-core
list(nx.k_core(GU, k = 8))
[8, 7, 6, 5, 4, 3, 2, 1]
['13205',
 '13213',
 '13214',
 '13211',
 '13201',
 '13206',
 '13001',
 '13209',
 '13203',
 '13005',
 '13212',
 '13208',
 '13204',
 '13210']

4.2 Blockmodel

NetworkX ne semble pas proposer de méthodes de blockmodeling. La documentation fournit un script créant une partition des sommets créée par une CAH sur la matrice d’adjacence.

4.3 Détection de communautés

Plusieurs méthodes de détection de communautés sont implémentées dans le sous-module community. Seule la mesure de la modularité semble disponible pour évaluer la qualité de la partition obtenue.

# détection de communautés
louv = nx.community.louvain_communities(GU, seed=123)
print("nb de communautés (louvain) :", len(louv))
louv[1]

#mesure de la modularité
print("modularité (louvain) : ", round(nx.community.modularity(GU, louv),2))

# algorithme maximisant la modularité
greed = nx.community.greedy_modularity_communities(GD)
print("nb de communautés (greedy mod.) :", len(greed))
print("modularité (greedy mod.) : ", round(nx.community.modularity(GD, greed),2))
nb de communautés (louvain) : 7
modularité (louvain) :  0.5
nb de communautés (greedy mod.) : 6
modularité (greedy mod.) :  0.51

Les lignes qui suivent anticipent sur la section suivante et indiquent comment visualiser les communautés détectées. La première étape est de créer un dictionnaire attribuant à chaque sommet la communauté d’appartenance détectée avec l’algorithme utilisé.

# création d'un dictionnaire vide
louvain_dict = {} 

# boucle qui remplit le dictionnaire
for i,c in enumerate(louv): 
    for CODGEO in c: 
        louvain_dict[CODGEO] = i
        
# ligne optionnelle pour ajouter cet attribut 
# nx.set_node_attributes(GD, louvain_dict, 'louvain')

# choix de l'algorithme de placement des sommets
pos = nx.spring_layout(GU)

# importation d'une palette de couleurs 
# nb de couleurs égal au nombre de classes + 1 (Python commence à 0)
cmap = plt.get_cmap('Paired', max(louvain_dict.values()) + 1)

# visualisation des sommets
nx.draw_networkx_nodes(GU,   # sommets à visualiser
                       pos,  # placement
                       louvain_dict.keys(),  # identifiants
                       node_size=40,         # taille 
                       cmap=cmap,            # palette de couleur
                       node_color=list(louvain_dict.values())) # affecter une couleur différente pour chaque classe
nx.draw_networkx_edges(GU, 
                       pos, 
                       alpha=0.5)  # transparence
<matplotlib.collections.LineCollection at 0x19739473880>