September 14, 2016

Publications

Filtz, E., Polleres, A., Karl, R., Haslhofer, B.: Evolution of the Bitcoin Address Graph – An Exploratory Longitudinal Study. International Data Science Conference (DSC 2017), Salzburg, Austria, 2017. (pdf)

Bitcoin is a decentralized virtual currency, which can be used to execute pseudo-anonymous payments globally within a short period of time and comparably low transaction costs. In this paper, we present initial results of a longitudinal study conducted over the Bitcoin address graph, which contains all addresses and transactions from the beginning of Bitcoin in January 2009 until 31st of August 2016. Our analysis reveals a highly-skewed degree distribution with a small number of outliers and illustrates that the entire graph is expanding rapidly. Furthermore, it demonstrates the power of address clustering heuristics for identifying real-world actors, who prefer to use Bitcoin for transferring rather than storing value. We believe that this paper provides novel insight into virtual currency ecosystems, which can inform the design of future analytics methods and infrastructures.

Haslhofer, B., Karl, R., Filtz, E. O Bitcoin Where Art Thou? Insight into Large-Scale Transaction Graphs. SEMANTICS 2016, Leipzig. (pdf)

Bitcoin is a rising digital currency and exemplifies the growing need for systematically gathering and analyzing public transaction data sets such as the blockchain. However, the blockchain in its raw form is just a large ledger listing transfers of currency units between alphanumeric character strings, without revealing contextually relevant real-world information. In this demo, we present GraphSense, which is a solution that applies a graph-centric perspective on digital currency transactions. It allows users to explore transactions and follow the money flow, facilitates analytics by semantically enriching the transaction graph, supports path and graph pattern search, and guides analysts to anomalous data points. To deal with the growing volume and velocity of transaction data, we implemented our solution on a horizontally scalable data processing and analytics infrastructure. Given the ongoing digital transformation in financial services and technologies, we believe that our approach contributes to development of analytics solutions for digital currency ecosystems, which is relevant in fields such as financial analytics, law enforcement, or scientific research.

Filtz, E., Savenkow, V., Umbrich, J. On finding the k shortest paths in RDF data. Intelligent Exploration of Semantic Data Workshop (IESD 2016), co-located with ISWC 2016, Kobe, Japan. (pdf)

Finding relationships between entities in RDF data is in the heart of many exploration tasks. General path enumeration algorithms are typically used for computing such relationships, nding top k short-est paths being of special interest. The k shortest paths problem has been thoroughly studied for the weighted graph case, the two most pop-ular generic algorithms are due to Eppstein and to Yen. Along with the Dijkstra’s shortest path algorithm upon which they build, these two algorithms are available in most libraries and graph databases. In the RDF context, however, the graph is unlabeled but can have multi-edges, and the found paths can contain cycles, so applying the mentioned algorithms is either impossible (Yen’s) or suboptimal. It is a folklore knowledge that the traditional breadth rst search (BFS) can be easily adapted to compute the k shortest paths. However, for dense graphs and large k, both
time and memory consumption become critical. We discuss two BFS adaptations which are easy to implement and substantially boost performance when solving the k shortest paths problem.