Cours “Network science” - Erwan Le Merrer
Cours “Network science” - Erwan Le Merrer
TD3 du 20/10/2022
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