J’ai rencontré il y a peu de temps Matthieu Lapaty, chercheur CNRS qui travaille en ce moment sur la détection d’anomalie dans un graphe évoluant dans le temps. Je lui ai parlé de la monnaie ğ1 et il a pensé que ce serait un bon jeu de données pour tester les métriques qu’il développe avec son équipe dont Nicolas Gensollen. J’ai rencontré ce dernier et lui ai présenté rapidement la monnaie libre pour qu’il puisse appliquer ses algorithmes dessus. Je poste avec son accord un email dans lequel il me demande des renseignements supplémentaires pour évaluer la qualité de ses métriques.
En gros, il s’agit de dire s’il y a une explication simple aux événements suivants :
Et pour chaque “candidat” (ligne parmi la liste ci-dessus)
Pour ceux qui sont intéressés par le détail, ils peuvent lire notre échange de mail en entier ci-dessous.
TL;DR, échange de mail
et ma réponse :
Je propose donc à @cgeek, @kimamila, @elois, @Galuel, @nanocryk, @Moul, @1000i100, @Inso et à tous ceux qui seraient intéressés (je pense notamment à @gerard94) d’examiner ces événements pour faire avancer notre compréhension théorique des graphes évoluant dans le temps.
Pour commencer et être sûr que j’ai bien compris, ils ont agglutiné des transactions en groupes pour en déduire la présence d’événements (rencontres physiques, etc), c’est bien ça ?
Une chose dont ils peuvent évidemment se servir, mais je ne le vois mentionné nulle part dans vos messages (que j’ai lus en diagonale, j’ai peut-être zappé), c’est les commentaires sur les transactions. Je suppose qu’ils les ont vues et que c’est la toute première chose qu’ils ont analysé, mais c’est encore mieux quand c’est dit explicitement.
Pour celui-ci, c’était le démarrage de la monnaie, tout le monde s’est fait des dons un peu dans tous les sens, ne serait-ce que pour tester. Une véritable anomalie par rapport à un fonctionnement normal, en fait.
C’est visiblement une série de dons d’Antonio Ferreira à l’équipe de dev comme en témoigne son commentaire sur chacune des transactions (d’où ma question au début : ont-ils regardé les commentaires) :
Du coup, ce n’est pas vraiment un « événement », c’est juste qu’Antonio a subitement décidé de faire des dons, ce qui arrive d’ailleurs je pense fréquemment. Quand on fait un don, on se dit, (« tiens y en aurait pas d’autres qui mériteraient aussi ? ») et hop la chaîne est amorcée.
Si, bien sûr. Nicolas a créé un compte sur le forum, il ne va pas tarder à venir commenter directement ici. Mais en attendant, tu peux lire un peu les papiers de http://www.complexnetworks.fr/
Il y aura sûrement un papier qui parle de cette métrique, peut être même qui mentionne le jeu de données de la monnaie libre. Ce sera l’occasion pour comprendre en détail le sens mathématique de la notion de “outlier” ou “anomalie”. Mais pour ça, il va falloir attendre quelques mois ! (c’est long la recherche)
Merci @HugoTrentesaux pour ton aide et pour nous avoir fait découvrir cette monnaie et son environnement, c’est un sujet particulièrement enrichissant.
Comme @HugoTrentesaux l’a précisé dans son premier post, Matthieu et moi travaillons sur la détection d’anomalies dans des graphes temporels, aussi appelés flux d’interactions. On s’intéresse donc de près aux systèmes où des entités interagissent dynamiquement entre elles. Les appels téléphoniques, les échanges de paquets IP sur le réseau, ou encore les transactions monétaires en sont des exemples.
Il y a beaucoup de littérature sur ces objets mais pas encore de formalisme universellement adopté comme c’est le cas pour les graphes statiques ou les séries temporelles par exemple. Matthieu et son équipe ont travaillé ces dernières années sur un formalisme permettant de décrire très finement ces séquences d’interactions qu’ils ont appelés des “stream-graphs”. Pour ceux que ça intéressent, ils ont publié il y a quelques temps un long papier posant les bases de ce formalisme (lien). Des concepts élémentaires de la théorie des graphes comme le nombre de nœuds, le degré d’un nœud, ou encore le coefficient de clustering y sont redéfinit pour encoder à la fois la composante structurelle et temporelle des flux d’interactions. Ce sont ces “métriques” que l’on utilise pour détecter des “anomalies”.
Une anomalie dans notre formalisme est un “sous-stream” (l’équivalent d’un sous-graphe mais avec la composante temporelle), ou plus simplement “les interactions d’un sous ensemble des nœuds durant un intervalle de temps”. On a donc mis au point des algorithmes qui échantillonnent des sous-stream du flux principal, et utilisent les concepts stream-graphs pour les comparer les uns aux autres.
Pour faire simple, l’objectif est de trouver des métriques qui suivent plus ou moins une loi normale sur les échantillons. Une anomalie (aussi appelée outlier) pour une métrique est alors purement statistique: il s’agit d’un sous-stream dont la valeur de sa métrique est très éloignée de la moyenne.
Il y a pas mal de subtilités sous-jacentes dont je n’ai volontairement pas parlé pour ne pas trop alourdir ce post mais que je peux développer si besoin ou s’il y a des gens que ça intéresse. En ce qui concerne les 10 échantillons que j’ai proposé à Hugo, il y a un certain nombre de sous-stream catégorisés comme “anormaux” mélangés avec d’autres sous-streams “normaux”. @jytou a effectivement mis le doigt sur deux échantillons “anormaux”: un correspondant au démarrage de la monnaie (qui revient très souvent dans les anomalies détectées vu le contenu du bloc 0), et un autre ou Mententon03 semble réaliser beaucoup plus de transactions qu’à la normale (ce qui n’est effectivement pas un “événement” en soit, mais bien une “anomalie” à nos yeux).
Nous en sommes encore à un stade expérimental pour la validation de nos méthodes. L’objectif de ce petit test est donc de vérifier que l’ont peut trouver des explications aux anomalies détectées, soit en les reliant à des événements (apéros monnaie libre ou autres), soit en vérifiant que la séquence de transactions détectées est inhabituelle pour au moins une des personnes impliquées dans les échanges. On souhaite aussi vérifier que l’on n’est pas en mesure de trouver des explications quel que soit le sous-stream présenté, d’où la présence d’échantillons “normaux”.
J’espère que ça éclaircit un peu les choses. N’hésitez pas à me poser des questions si nécessaire.
ca va simplifier la recherche des trucs étranges, y a -t’il une dimension d’apprentissage? comment comparer des évenement en debut de blockchain ou les transactions sont bcp plus rare qu’en fin? mais surtout, est-il possible de categoriser l’etrangeté des évenement et “d’apprendre” a celui ci, similaire a une “back propagation” d’un réseau de neuronnes? avec l’aide d’un controleur qui dirait, ca c’est normal, ca ca ne l’est pas?
Merci pour ta réponse @Junidev. L’hétérogénéité de la donnée est effectivement une des “subtilités” que j’ai préféré passer sous silence dans mon premier post. Cette hétérogénéité est présente à la fois temporellement (le volume de transactions dans le système évolue, effets de saisons, etc…), et structurellement (certains utilisateurs interagissent beaucoup plus que d’autres, avec des fréquences ou des patterns spécifiques, etc…). Les algos sur lesquels on travaille ont pour but de normaliser localement (structurellement et temporellement) les métriques des échantillons avant de les comparer.
Cela peut être assez subtil. Dans des échanges téléphoniques par exemple, quelqu’un qui n’appelle presque jamais personne mais passe soudainement plusieurs coups de fil pour le 1er janvier a-t-il un comportement anormal?
On a souvent cette dualité du “suis-je anormal par rapport à mon activité classique?” et du “suis-je anormal par rapport aux autres maintenant?”. Les “anomalies les plus anormales” étant bien entendu celles qui traduisent à la fois une déviation forte par rapport à leurs comportements d’habitude et par rapport à celui des autres au même moment.
Pour ce qui est de l’apprentissage, c’est une évolution naturelle vers laquelle on souhaite bien sûr tendre. Pour le moment, on en est encore à une étape préliminaire sans apprentissage, mais on peut très bien imaginer des algos de classification (réseaux de neuronnes et autres) utilisant des features basés sur des propriétés stream-graphs.
Bonjour @Max
Non, on se base uniquement sur les transactions pures. En gros, la blockchain est transformée en une suite de triplets “t a b” signifiant que a a réalisé une transaction vers b à l’instant t. C’est la seule information que l’algorithme possède. @jytou a suggéré plus haut d’avoir recours aux commentaires des transactions pour la validation des anomalies détectées. Je vais regarder cela d’un peu plus près. Pour le moment je préférais ne pas les utiliser puisqu’ils ne sont pas systématiquement présents et pas toujours très informatifs (en tout cas pour cet objectif).
C’est vrai qu’entre les private jokes, les messages codés, sans compter les transactions sans commentaires, c’est une information à caractère plutôt aléatoire. Mais ça peut permettre ponctuellement de comprendre l’intention de la transaction. Par ailleurs, certaines transactions sont marquées par gchange et gannonce comme par exemple la 2ème transaction de ce bloc : https://g1.presles.fr/blockchain/block/45629
@NicolasGensollen est-ce que ton code pour récupérer la liste des transactions est disponible ? J’aimerais bien l’adapter avoir facilement des informations comme :
Voici la requete elastic search pour aller chercher les 10 000 premières transactions directement sur la blockchain, trié par date, avec le compte source, le compte destinataire, le montant, et le commentaire
ca a l’air interessant