Cours “Network science” - Erwan Le Merrer

Cours “Network science” - Erwan Le Merrer

TP1 du 25/11/2019

Nous utiliserons NetworkX pour la manipulation des concepts abordés dans le poly. La documentation est disponible ici.

Démarrage rapide sur NetworkX ici.

Warm-up

  • créez un graphe “G” dirigé
from networkx import nx
import pylab as plt
import numpy as np

G = nx.DiGraph()
  • ajoutez 5 noeuds et connectez les en cycle
    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
  • affichez le degree sortant du noeud 0
    print(G.out_degree(0))
  • affichez le nombre de noeuds, puis le nombre d’arêtes de G

  • vérifiez que l’arête (0, 3) n’existe pas, grâce à la fonction appropriée
    print(G.has_edge(0, 3))

  • inversez la direction des arêtes de G
    G = G.reverse()

  • ajoutez l’arête (0, 3), avec nom positionné (attribut) à “raccourci”, puis l’afficher
    G.add_edge(0, 3, nom='raccourci')
    print(G[0][3])

/!\ pas très propre, certainement mieux à faire…

  • affichez votre graphe avec la function “draw” et vérifier qu’il est cohérent avec l’exercice
    nx.draw(G,nx.spring_layout(G),cmap=plt.get_cmap('seismic'), with_labels=True)
    plt.show()

Etude d’un graphe réel

Le graphe Zachary Karate Club

  • importez le graphe “karate club” dans G
    G = nx.karate_club_graph()
  • affichez le; qu’est ce qu’un layout ? Essayez en plusieurs

  • afficher son nombre de noeuds

    print("Nombre de noeuds: ", nx.number_of_nodes(G))
  • affichez le plus haut degré de G
    print("Plus haut degré du graphe: ", max([d for n,d in np.array(G.degree)]))
  • affichez (en texte) la distribution des degrés des noeuds de G
    print("Distribution des degrés: ")
    degree_sequence = [d for n, d in G.degree()]  # degree sequence
    hist = {}
    for d in degree_sequence:
        if d in hist: hist[d] += 1
        else: hist[d] = 1
    print("degree #nodes")
    for d in hist:
        print('%d %d' % (d, hist[d]))
  • affichez le coefficient de clustering du noeud 4
    print("Indiv. clustering coefficients: ", str(nx.clustering(G)[4]))

  • affichez le coefficient de clustering moyen de G
    print("Indiv. clustering coefficients: ", str(nx.clustering(G)[4]))
  • affichez le diamètre de G
    print("Diameter: ", nx.diameter(G))
  • affichez la conductance du groupe de noeuds [4,5,6,10,16]
    print("Conductance [4,5,6,10,16]: ", nx.cuts.conductance(G, [4,5,6,10,16]))
  • extraire S, le sous graphe de G composé par les noeuds donnés à l’exercice précédent
    S = nx.subgraph(G, [4,5,6,10,16])
  • affichez la connectivité algébrique de G. Conclusion?
    print("Algebraic connectivity: ", nx.algebraic_connectivity(G))
  • chercher la fonction “articulation_points” dans la doc networkx; quel est son but? Exécutez la sur G
    print("Points d'articulation de G: ", list(nx.articulation_points(G)))
  • chercher la fonction “bridges” dans la doc networkx, quel est son but? Exécutez la sur G
    print("Ponts de G: ", list(nx.bridges(G)))

  • créez un graphe H, copie de G. Dans H, supprimez le noeud 0, puis affichez la connectivité algébrique de H pour vérifier sa propriété traitant de la connectivité. Qu’en concluez vous?
    H = G.copy()
    H.remove_node(0)
    print("Algebraic connectivity of H: ", nx.algebraic_connectivity(H))
  • affichez le nombre de composant connectés de H
    print("Number of connected components in H:", nx.number_connected_components(H))
  • donner un numéro identique aux noeuds (dans un attribut) en fonction de leur appartenance à un même composant (cf exercice précédent). Affichez ces attributs
    component = []
    nx.set_node_attributes(G, component, 'component')
    c = 0
    for set in nx.connected_components(H):
        for n in set:
            H.nodes[n]['component']=c
        c+=1

Questions/commentaires: erwan.le-merrer@inria.fr