Partie 2 Utilisation de la bibliothèque networkx

Il existe deux grandes bibliothèques en python pour la gestion des graphes :

  • networkx
  • igraph

La nouvelle version (2.2) de networkx couvre largement ce dont on a besoin pour créer, manipuler et analyser les réseaux.

2.1 Introduction à networkx

Import de la bibliothèque 1 :

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
g = nx.Graph() # DiGraph() pour un graphe orienté
g.add_nodes_from(range(5))
g.add_edges_from([(0,1),(3,4),(4,2),(1,3),(4,0),(1,2)])

Les méthodes suivantes permettent d’accéder aux attributs du graphe et fournissent les primitives essentielles :

  • g.degree() : degrés des sommets du graphe g
  • g.number_of_nodes() : nombre de sommets du graphe g
  • g.number_of_edges() : nombre d’arcs du graphe g
  • g.predecessors(i) : liste des prédecesseurs du sommet i
  • g.successors(i) : liste des successeurs du sommet i
  • g.neighbors(i) : liste des voisins du sommet i

On dispose aussi des indicateurs et outils suivants (liste non exhaustive) :

  • density(g) : densité du graphe g
  • diameter(g) : diamètre du graphe g
  • shortest_path(g) : plus courts chemins entre tous les couples de sommets de g
  • pagerank(g) : calcul du pagerank

2.2 Analyse d’un réseau social d’Orques

2.2.1 Construction du réseau

g = nx.newman_watts_strogatz_graph(100, 15, 0.35, seed = 12345 )
plt.figure()
nx.draw(g)
## /usr/local/lib/python3.7/dist-packages/networkx/drawing/nx_pylab.py:611: MatplotlibDeprecationWarning: isinstance(..., numbers.Number)
##   if cb.is_numlike(alpha):
plt.show()

Remarque : on utilise ici un générateur de graphes 2

Noms des sommets (les membres de nos réseau social) :

names = [ "Geygrat",    "Dalba",      "Orcgro",   "Brukzhul", "Rumsnarl",
          "Ub",         "Buckner",    "Nershnag", "Murbaag",  "Bagthrum",
          "Irok",       "Gratdu",     "Skumzu",   "Zugzu",    "Shnagta",
          "Gruntlúrtz", "Nackgim",    "Rendah",   "Zogdahk",  "Grim",
          "Kashgash",   "Murzgor",    "Tanazg",   "Zugsnarl", "Nackdah",
          "Dorg",       "Bruksel",    "Rokgar",   "Gauz",     "Triggba",
          "Zogug",      "Kilrogg",    "Kilmuz",   "Gimb",     "Kaglug",
          "Ronggimb",   "Ubgor",      "Rongzoc",  "Tulrok",   "Shagaluk",
          "Jubag",      "Gromgar",    "Dushner",  "Shaggarm", "Rokarg",
          "Lurtzka",    "Golgimgash", "Baagkil",  "Shurub",   "Bagro",
          "Nákhdahk",   "Rokgor",     "Telúrtz",  "Danmeg",   "Shagte",
          "Duzgor",     "Dablorg",    "Gorhúr",   "Badork",   "Lagong",
          "Thokner",    "Luknerzock", "Megcro",   "Geyta",    "Zockmog",
          "Tugri",      "Dogbal",     "Lugu",     "Gimgrom",  "Buzbol",
          "Usnarlburz", "Doggrat",    "Guli",     "Orca",     "Baggar",
          "Bolckor",    "Gratco",     "Thakglúk", "Zuga",     "Zuor",
          "Jugor",      "Balga",      "Orcrad",   "Skabnaz",  "Glukhurtz",
          "Orprukharg", "Grunthar",   "Tanmeggu", "Durmurz",  "Zu-gul",
          "Grarend",    "Ugim",       "Húrthrum", "Drog",     "Likrok",
          "Kargcrou",   "Ronurk",     "Kargu",    "Garmburz", "Tinourk"]
for n in g.nodes:
  g.nodes[n]["name"]=names[n]

2.2.2 Affichage (pour illustrer les paramètres graphiques)

options = {
      'node_color' : 'yellow',
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
    }
plt.figure()
nx.draw(g,**options)
plt.show()

2.2.3 Analyse

Nous allons maintenant nous intéresser aux questions vraiment importantes…

  • Quels sont les Orques les plus importants/centraux ?
  • Quels sont les Orques les plus critiques pour la cohésion du réseau ?
  • Quelles suggestions d’amis faut-il faire pour « consolider » le réseau ?
  • Y a-t-il des communautés qui se sont formées ?
  • Comment l’information va-t-elle se propager dans mon réseau ?

Nous allons déjà déterminer les Orques qui occupent des positions importantes dans ce réseaux en identifiant les leaders. Commençons par utiliser l’information de degré :

print(g.degree())
## [(0, 25), (1, 25), (2, 23), (3, 22), (4, 18), (5, 24), (6, 18), (7, 18), (8, 18), (9, 18), (10, 15), (11, 22), (12, 25), (13, 20), (14, 19), (15, 22), (16, 21), (17, 18), (18, 19), (19, 23), (20, 16), (21, 18), (22, 19), (23, 19), (24, 17), (25, 22), (26, 22), (27, 20), (28, 17), (29, 16), (30, 17), (31, 17), (32, 20), (33, 18), (34, 18), (35, 19), (36, 21), (37, 20), (38, 18), (39, 23), (40, 18), (41, 21), (42, 21), (43, 25), (44, 20), (45, 18), (46, 17), (47, 20), (48, 16), (49, 19), (50, 19), (51, 17), (52, 17), (53, 20), (54, 23), (55, 22), (56, 19), (57, 19), (58, 18), (59, 16), (60, 18), (61, 16), (62, 17), (63, 17), (64, 20), (65, 20), (66, 18), (67, 19), (68, 23), (69, 16), (70, 21), (71, 18), (72, 21), (73, 16), (74, 19), (75, 19), (76, 16), (77, 16), (78, 16), (79, 19), (80, 19), (81, 15), (82, 19), (83, 18), (84, 23), (85, 18), (86, 15), (87, 21), (88, 16), (89, 21), (90, 17), (91, 18), (92, 17), (93, 20), (94, 16), (95, 17), (96, 18), (97, 17), (98, 17), (99, 16)]

Cherchons le degré le plus élevé :

degre_max = max(np.array(g.degree())[:,1])
print(degre_max)
## 25

Puis les positions des Orques ayant ce degré :

index_max = [i for i,j in g.degree() if j == degre_max]
print(index_max)
## [0, 1, 12, 43]

On obtient alors la liste des Orques les plus centraux d’après le degré :

orques_deg_max = [ g.nodes[i]["name"] for i in index_max ]
print(orques_deg_max)
## ['Geygrat', 'Dalba', 'Skumzu', 'Shaggarm']

Utilisons maintenant d’autres indicateurs de centralité :

centralité de degré

centralite = nx.degree_centrality(g)
centralite_ind = list(centralite.keys())
centralite_val = list(centralite.values())
maximum = max(centralite_val)
sommets_centralite_max = [centralite_ind[i] for i in g.nodes if centralite_val[i] == maximum]
print(sommets_centralite_max)
## [0, 1, 12, 43]
orques_centraux = [ g.nodes[i]["name"] for i in sommets_centralite_max ]
print(orques_centraux)
## ['Geygrat', 'Dalba', 'Skumzu', 'Shaggarm']

centralité de proximité

centralite = nx.closeness_centrality(g)
centralite_ind = list(centralite.keys())
centralite_val = list(centralite.values())
maximum = max(centralite_val)
sommets_centralite_max = [centralite_ind[i] for i in g.nodes if centralite_val[i] == maximum]
print(sommets_centralite_max)
## [0, 1]
orques_centraux = [ g.nodes[i]["name"] for i in sommets_centralite_max ]
print(orques_centraux)
## ['Geygrat', 'Dalba']

centralité d’intermédiarité

centralite = nx.betweenness_centrality(g)
centralite_ind = list(centralite.keys())
centralite_val = list(centralite.values())
maximum = max(centralite_val)
sommets_centralite_max = [centralite_ind[i] for i in g.nodes if centralite_val[i] == maximum]
print(sommets_centralite_max)
## [54]
orques_centraux = [ g.nodes[i]["name"] for i in sommets_centralite_max ]
print(orques_centraux)
## ['Shagte']

On peut visualiser ces sommets en utilisant d’autres couleurs :

# Initialisation
couleurs_sommets = ["yellow"] * g.number_of_nodes() 
# Coloration des somemts d'intérêt
sommets_a_voir = [0, 1, 12, 43, 54]
for i in sommets_a_voir:
  couleurs_sommets[i] = "red"
# Visualisation
options = {
      'node_color' : couleurs_sommets,
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
    }
plt.figure()
nx.draw(g,**options)
plt.show()

2.2.4 Détection de communautés

La fonction greedy_modularity_communities() de networkx permet d’extraire des communautés par maximisation de la modularité :

from networkx.algorithms import community
partition = community.greedy_modularity_communities(g)

Nombre de partitions trouvées :

print(len(partition))
## 3

Affichage de la composition des communautés :

for i in range(len(partition)):
  community = list(partition[i])
  print("Communauté ",str(i+1))
  print([ g.nodes[i]["name"] for i in community ])
## Communauté  1
## ['Geygrat', 'Dalba', 'Orcgro', 'Brukzhul', 'Rumsnarl', 'Ub', 'Geyta', 'Zockmog', 'Tugri', 'Dogbal', 'Lugu', 'Gimgrom', 'Buzbol', 'Usnarlburz', 'Doggrat', 'Guli', 'Orca', 'Baggar', 'Bolckor', 'Gratco', 'Thakglúk', 'Zuga', 'Zuor', 'Jugor', 'Balga', 'Orcrad', 'Skabnaz', 'Glukhurtz', 'Orprukharg', 'Grunthar', 'Tanmeggu', 'Durmurz', 'Zu-gul', 'Grarend', 'Ugim', 'Húrthrum', 'Drog', 'Likrok', 'Kargcrou', 'Ronurk', 'Kargu', 'Garmburz', 'Tinourk']
## Communauté  2
## ['Dorg', 'Bruksel', 'Rokgar', 'Gauz', 'Triggba', 'Zogug', 'Kilrogg', 'Kilmuz', 'Gimb', 'Kaglug', 'Ronggimb', 'Ubgor', 'Rongzoc', 'Tulrok', 'Shagaluk', 'Jubag', 'Gromgar', 'Dushner', 'Shaggarm', 'Rokarg', 'Lurtzka', 'Golgimgash', 'Baagkil', 'Shurub', 'Bagro', 'Nákhdahk', 'Rokgor', 'Telúrtz', 'Danmeg', 'Shagte', 'Duzgor', 'Dablorg', 'Gorhúr', 'Badork', 'Lagong', 'Thokner', 'Luknerzock', 'Megcro']
## Communauté  3
## ['Buckner', 'Nershnag', 'Murbaag', 'Bagthrum', 'Irok', 'Gratdu', 'Skumzu', 'Zugzu', 'Shnagta', 'Gruntlúrtz', 'Nackgim', 'Rendah', 'Zogdahk', 'Grim', 'Kashgash', 'Murzgor', 'Tanazg', 'Zugsnarl', 'Nackdah']

Visualisation par contruction d’un vecteur de couleurs :

couleurs_num = [0] * g.number_of_nodes()
for i in range(len(partition)):
  for j in partition[i]:
    couleurs_num[j] = i
options = {
      'cmap'       : plt.get_cmap('jet'), 
      'node_color' : couleurs_num,
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
    }
plt.figure()
nx.draw(g,**options)
plt.show()

2.2.5 Détection des Orques critiques

Essayons de détecter les points d’articulation de ce graphe :

pt = nx.articulation_points(g)
print([i for i in pt])
## []

Il n’y en a pas ! Ce qui n’est pas surpenant compte tenu de la structure et de la densité du graphe. On peut générer un graphe moins dense afin de tester cette fonction :

g2 = nx.erdos_renyi_graph(100, 0.05, seed=12345, directed=False)
options = {
      'node_color' : 'yellow',
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
    }
plt.figure()
nx.draw(g2,**options)
plt.show()

pt = nx.articulation_points(g2)
print([i for i in pt])
## [16]

2.2.6 Effet « petit monde »

Même ce graphe a été généré à l’aide de paramètres contrôlés et non représentatifs des réseaux sociaux existants, on peut se demander si « l’effet petit monde » est vérifié ici, en calculant la distance géodésique moyenne entre les couples de points :

p = nx.shortest_path(g) 
n = g.number_of_nodes()
nb_inter = []
for i in range(n):
  for j in range(i+1,n):
    nb_inter.append(len(p[i][j])-2)
# On aurait pu éviter la double boucle
# nb_inter2 = [len(p[i][j]) for i in range(n) for j in range(i+1,n)]
print("Nombre d'intermédiaires entre les individus du réseau")
## Nombre d'intermédiaires entre les individus du réseau
print("- Minimum   : ", str(np.min(nb_inter)))
## - Minimum   :  0
print("- Maximum   : ", str(np.max(nb_inter)))
## - Maximum   :  2
print("- Moyenne   : ", str(np.mean(nb_inter)))
## - Moyenne   :  0.9014141414141414
print("- Médiane   : ", str(np.median(nb_inter)))
## - Médiane   :  1.0

2.2.7 Pagerank des utilisateurs

pg = nx.pagerank(g)
print(pg.values())
## dict_values([0.012626383840202354, 0.012635930959914093, 0.011800229250165384, 0.01128029153177614, 0.009497393147650985, 0.012190380851856746, 0.009443036452771869, 0.009444412925097689, 0.00946809532288441, 0.009453261941932032, 0.008114711380699132, 0.011318088929321329, 0.012567457253428725, 0.01039708209829097, 0.009913633527047942, 0.011256969000308174, 0.010821889597040796, 0.009515690664202927, 0.009938850152870373, 0.011748034522462545, 0.008596559773515648, 0.009481925092829859, 0.009976112612110538, 0.010006114730113402, 0.00912203205224513, 0.011353843481386763, 0.011344824247361785, 0.010446972526303713, 0.009116507906247465, 0.008660770581195505, 0.009083081227167267, 0.009130217541500937, 0.010400374347208611, 0.009557917765325235, 0.009589063287788156, 0.010006468028785877, 0.010851599649412258, 0.010390203894011834, 0.009458512636237372, 0.011721170805443853, 0.009478775970196716, 0.010811995324794408, 0.010849552676663207, 0.01263741630442079, 0.010372438142783345, 0.009525236767969618, 0.009065365557042017, 0.010390499362024257, 0.008598180095355037, 0.009977878645447882, 0.009923814591031924, 0.009077312474734874, 0.00910658992915708, 0.01045084371214827, 0.011856357148214385, 0.011343344127940485, 0.010027323906348277, 0.010038584846355307, 0.009547712652309264, 0.008683473796989895, 0.009594498996222908, 0.008676258581082851, 0.009148513047806527, 0.009162146075949442, 0.010532989980991218, 0.010454650667919015, 0.009624769768014182, 0.01004929426890891, 0.01182829090618099, 0.008704635088199061, 0.010947344160373518, 0.009615779637622293, 0.010992571042825553, 0.00873649402182718, 0.010118373216557997, 0.01013154947926248, 0.008785917196307702, 0.008731942246034987, 0.008749147133388386, 0.010129613451807832, 0.010115028818028138, 0.008336060475240027, 0.010139808731028502, 0.009689520134419873, 0.011876220471790785, 0.009664626442640798, 0.008300273275216844, 0.01100588803049009, 0.008788487669577003, 0.010981394944744888, 0.009204883619790737, 0.009630283382543296, 0.00922949952659707, 0.010547169771125107, 0.008688153240645414, 0.009131588575246931, 0.009594213493167376, 0.009129713440170186, 0.009110153226478174, 0.008633462195732897])

Visualisation :

options = {
      'cmap'       : plt.get_cmap('viridis'), 
      'node_color' : list(pg.values()),
      'node_size'  : 550,
      'edge_color' : 'tab:grey',
      'with_labels': True
    }
plt.figure()
nx.draw(g,**options)
plt.show()

Et notre vainqueur est :

pg_val = list(pg.values())
pg_key = list(pg.keys())
id_pg_max = [i for i in pg_key if pg[i] == max(pg_val)]
print([g.node[i]["name"] for i in id_pg_max])
## ['Shaggarm']