Cours “Network science” - Erwan Le Merrer

Cours “Network science” - Erwan Le Merrer

TP4 du 03/12/2020

NetworkX et sa documentation ici.

Propos principal: extraire les communautés d’un graphe réel.

Détection de communautés

  • téléchargez le fichier des caratères de Games of Thrones “book 1” ici. Importez le dans GoT
    import pandas as pd
    got_data = pd.read_csv('graphs/asoiaf-book1-edges.csv')
    print(got_data.head())

    GoT = nx.Graph()
    for row in got_data.iterrows():
        GoT.add_edge(row[1]['Source'],row[1]['Target'],
            weight=row[1]['weight'])
  • afficher l’assortativité de GoT. Conclusion?
    print(nx.degree_assortativity_coefficient(GoT))
  • afficher le graphe correspondant au k-core, avec k=11
    print("k-cores: ", nx.core_number(GoT))
    G = nx.k_core(GoT,11)

    nx.draw(G, nx.spring_layout(G), with_labels=True)
    plt.show()
  • combien des 10 noeuds les plus centraux selon la betweenness centrality appartiennent au précédent 11-core? Conclusion?
    nb = 0
    top10 = [x for x,v in sorted(nx.betweenness_centrality(GoT).items(), key=lambda x:x[1], reverse=True)][:10]
    for i in top10:
        if i in G.nodes: nb+=1
    print("%d/%d" % (nb,len(top10)))    

    # exécutez l'algorithme de détection de communautés qui utilise la notion de modularité. Conclusion sur sa détection de communauté?
    from networkx.algorithms import community
    parts = list(community.greedy_modularity_communities(GoT))
    print("Number of communities detected: ", len(parts)) # 187, ie, all in it !!!
  • exécutez l’algorithme de détection de communautés qui utilise la notion de modularité. Conclusion sur sa capacité à détecter les communautés de ce graphe?
    nb = 0
    top10 = [x for x,v in sorted(nx.betweenness_centrality(GoT).items(), key=lambda x:x[1], reverse=True)][:10]
    print("%d/%d" % (len(set(top10).intersection(G.nodes)), len(top10)))
  • regardez l’algorithme de girvan_newman: les communautés sont créées à partir de la suppression d’arêtes. Quel est le critère pour sélectionner les arêtes à supprimer prioritairement?
    from networkx.algorithms import community
    parts = list(community.greedy_modularity_communities(GoT))
    print("Number of communities detected: ", len(parts)) # 187, ie, all in it !!!
  • utilisez le pour créer un partitionnement en 10 communautés
    parts_gn = community.girvan_newman(GoT)
    k = 9
    import itertools
    for communities in itertools.islice(parts_gn, k):
        comms = tuple(sorted(c) for c in communities)
        print("Nb of computed communities: ", len(comms))
  • affichez la troisième de ces 10 communautés, en utilisant la fonction qui extrait un sous graphe de GoT
    G_comm = GoT.subgraph(comms[2])
    nx.draw(G_comm, nx.spring_layout(G_comm), with_labels=True)
  • reprenez la boucle For qui sert à créer les 10 partitions avec Girvan Newman, et insérez la mesure de qualité du partitionnement courant avec la fonction coverage. Que mesure t elle exactement? A combien de communautés aurait il été judicieux de s arrêter au regard de cette mesure?
    parts_gn = community.girvan_newman(GoT)
    c = None
    for communities in itertools.islice(parts_gn, k):
        comms = tuple(sorted(c) for c in communities)
        print("Nb of computed communities: ", len(comms))
        print(c)
        c = communities
        print(community.quality.coverage(GoT,c))
    # ---> assez fort drop après 5 communautés, de 0.97 à 0.93

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