Cours “Network science” - Erwan Le Merrer

Cours “Network science” - Erwan Le Merrer

TD3 du 17/11/2021

NetworkX et sa documentation ici.

Propos principal: les mesures d’influence dans les graphes. Puis un modèle de propagation épidémique simplifié.

Influence dans un graphe réel

  • 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 les caractéristiques quelques de base de GoT (avec des fonctions de la librairie)
    print(GoT.number_of_nodes())
    print(nx.is_connected(GoT))
    print(nx.is_directed(GoT))
  • Regardons les quatres centralités suivantes sur GoT: degree, betweenness, eigenvector centrality et second order centrality. Classez les personnages par ordre d’influence décroissante pour chaque centralité (attention à l’ordre pour second order centrality!). Les classements sont ils les mêmes?
    print(sorted(nx.degree_centrality(GoT).items(), key=lambda x:x[1], reverse=True))
    print(sorted(nx.eigenvector_centrality(GoT).items(), key=lambda x:x[1], reverse=True))
    print(sorted(nx.betweenness_centrality(GoT).items(), key=lambda x:x[1], reverse=True))
    print(sorted(nx.second_order_centrality(GoT).items(), key=lambda x:x[1], reverse=False))

Attaque sur l’influence

  • vous allez attaquer ce réseau social pour essayer de gagner de l’influence pour un caractère fictif, le noeud 0. Connectez un noeud 0 à ‘Daryn-Hornwood’, dans un nouveau graphe Gs
    Gs = GoT.copy()
    Gs.add_edge('Daryn-Hornwood', 0)
  • exécutez une centralité eigenvector centrality sur le graphe attaqué Gs, et affichez le rang de 0 dans le classement de l’influence des noeuds. L’attaque est elle efficace?
    rank_ec = sorted(nx.eigenvector_centrality(Gs).items(), key=lambda x:x[1], reverse=True)
    keys = [i for i,v in rank_ec]
    print("Rank with eigenvector_centrality for single node addition, connected to Daryn-Hornwood: ", keys.index(0))
  • même manipulation, en connectant à la place 0 avec Eddard-Stark dans un graphe G. Le rang de 0 est il meilleur? Pourquoi?
    G = GoT.copy()
    G.add_edge('Eddard-Stark', 0)
    rank_ec = sorted(nx.eigenvector_centrality(G).items(), key=lambda x:x[1], reverse=True)
    keys = [i for i,v in rank_ec]
    print("Rank with eigenvector_centrality for single node addition, connected to Eddard-Stark: ", keys.index(0))
  • créez un graphe en étoile de 10 noeuds, avec 0 pour centre. Connectez le à GoT par une arête entre 0 et Eddard-Stark (cf fonction compose)
    A1 = nx.star_graph(9)
    G =nx.compose(GoT, A1)

    G.add_edge('Eddard-Stark', 0)
  • quel est le nouveau rang de 0? Différence par rapport à l’attaque simple?
    rank_ec = sorted(nx.eigenvector_centrality(G).items(), key=lambda x:x[1], reverse=True)
    keys = [i for i,v in rank_ec]
    print("Rank with eigenvector centrality and star graph attack: ", keys.index(0))
  • trouver un exemple de de centralité qui est moins sensible que eigenvector centrality à cette attaque (ie, le rang de 0 est bas)
    rank_soc = sorted(nx.second_order_centrality(G).items(), key=lambda x:x[1], reverse=False)
    keys = [i for i,v in rank_soc]
    print("Rank with second order centrality and star graph attack: ", keys.index(0))

Détection de l’attaque

  • tester si le sampling à base de marches aléatoires pour détecter les attaques (cf poly) classe les noeuds qui ont servi à l’attaque parmi les plus probablement “faux” de G (ie, quid de leur fréquence d’échantillonnage? Afficher le sampling rate pour 1000 marches aléatoires partant chacune d’un noeud aléatoire de G
    import random
    
    def walk_h_hops(i,h,G):
        path = []
        next = random.choice(list(G.neighbors(i)))
        while h>0:
            path.append(next)
            next = random.choice(list(G.neighbors(next)))
            h-=1
        return path
    
    samples = []
    nb_samples = 1000
    for t in range(nb_samples):
        samples.append (walk_h_hops(random.choice(list(G.nodes)), 1000, G)[-1] )
    for i in G.nodes():
        print("Node %s: normalized sampling rate=%f" % (i,samples.count(i)/nb_samples))

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