Module 44: Motif distributions in daily Bitcoin transaction graphs

Faculty Contact: John O'Donovan

Research Areas:

Abstract:
Bitcoin is a tantalizing object of study—a huge quantity of high-quality data is freely available, but because de-anonymization is impractical, traditional approaches to studying economic networks do not apply. The network that we propose to study is the transaction network, defined in [3]. Each vertex in the transaction network is a Bitcoin transaction, and weights on the edge t1 → t2 are the amount of Bitcoin flowing from output addresses in t1 to input addresses in t2. In other words, this edge weight is the amount of Bitcoin involved in the transaction t2 which was “financed” by transaction t1. Using a Blockchain explorer, it is possible to download the transaction graph from any given day (or any other time interval).

Network motifs, introduced in [4] in 2002, provide a way to quantify the local structure of a complex network. An n-motif is a connected, n-node digraph, typically with n ≤ 5. One way to quantify local graph structure is to calculate the motif distribution; that is, the fraction of n-node subgraphs which are isomorphic to each possible n-motif. Graphs with similar motif distributions have similar structure at the local level. Daily transaction graphs typically have ∼ 106 nodes, making it computationally infeasible to calculate their motif distributions exactly. Fortunately, a sampling algorithm exists [5], making it possible to uniformly sample a fixed fraction of n-node subgraphs. Therefore it is possible estimate the motif distributions for each daily transaction graph. In general terms, we want to study how local-level structure in the Bitcoin transaction graph correlates with macro-level properties of the currency. We propose using motif distributions to quantify local graph structure. Macro-level properties of interest include the direction and magnitude of daily Bitcoin price fluctuations, as well as the number of daily Bitcoin transactions. Specifically, we aim to test the following hypotheses:

  • Hypothesis 1: Motif distributions in daily transaction graphs will differ between (i) days with a large price increase, (ii) days with a moderate price increase, (iii) days with a small price change, (iv) days with a moderate price decrease, and (v) days with a large price decrease.
  • Hypothesis 2: Motif distributions in daily transaction graphs will differ between (i) days with a large transaction volume, (ii) days with a moderate transaction volume, and (iii) days with a small transaction volume.

If we can confirm either hypothesis to a reasonable level of significance, we ask an additional question:

  • Can we train a machine learning algorithm to predict daily price movement or daily transaction volume from daily motif distribution?

References

  1. D. Ron and A. Shamir, “Quantitative analysis of the full bitcoin transaction graph,” in International Conference on Financial Cryptography and Data Security, pp. 6–24, Springer, 2013.
  2. A. Biryukov, D. Khovratovich, and I. Pustogarov, “Deanonymisation of clients in bitcoin p2p network,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 15–29, ACM, 2014.
  3. F. Reid and M. Harrigan, “An analysis of anonymity in the bitcoin system,” in Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on, pp. 1318–1326, IEEE, 2011.
  4. S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, “Network motifs in the transcriptional regulation network of escherichia coli,” Nature genetics, vol. 31, no. 1, p. 64, 2002.
  5. S. Wernicke, “A faster algorithm for detecting network motifs,” in International Workshop on Algorithms in Bioinformatics, pp. 165–177, Springer, 2005.

 

Active Quarters:

  • Spring 2018: Kevin Smith