Cours “Network science” - Erwan Le Merrer

TP3 du 20/11/2020

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))

Propagation épidémique sur un graphe

une épidémie chez les personnages de GoT: programmez un modèle épidémique SIS simplifié (avec une seule variable delta et pas de boucles sur les états), en simulation par ronde. Passez en par un statut booléen ‘infected’ sur chaque noeud. Affichez un tableau contenant l’état ‘infected’ des noeuds après chaque ronde

    delta = 0.9
    infecte = False
    nx.set_node_attributes(GoT, infecte, 'infected')
    
    def infection_simulation(patient_zero,nb_rounds,delta,G):
        GoT.nodes[patient_zero]['infected'] = True

        for i in range(nb_rounds):
            for i in GoT.nodes():
                # infection des voisins
                if(GoT.nodes[i]['infected']):
                    for j in list(GoT.neighbors(i)):
                        if random.random() < 1-delta: GoT.nodes[j]['infected'] = True
                # guerison
                if(GoT.nodes[i]['infected']):
                    if random.random() < delta: GoT.nodes[j]['infected'] = False       
        # end of round
        return([GoT.nodes[x]['infected'] for x in GoT.nodes()])

    # démarrez une infection à partir de 'Daryn-Hornwood' (ie, infected=True) (delta=0.9), combien d'infectés après 10 rounds?
    print(sum(infection_simulation('Daryn-Hornwood',10,delta,GoT)))
    
    # même chose à partir de 'Eddard-Stark', combien d'infectés? Conclusion?
    print(sum(infection_simulation('Eddard-Stark',10,delta,GoT)))

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