Header

UZH-Logo

Maintenance Infos

Higher-Order Visualization of Causal Structures in Dynamics Graphs


Perri, Vincenzo; Scholtes, Ingo (2019). Higher-Order Visualization of Causal Structures in Dynamics Graphs. arXiv.org 1908.05976, University of Zurich.

Abstract

Graph or network representations are an important foundation for data mining and machine learning tasks in relational data. Many tools of network analysis, like centrality measures, information ranking, or cluster detection rest on the assumption that links capture direct influence, and that paths represent possible indirect influence. This assumption is invalidated in time-stamped network data capturing, e.g., dynamic social networks, biological sequences or financial transactions. In such data, for two time-stamped links (A,B) and (B,C) the chronological ordering and timing determines whether a causal path from node A via B to C exists. A number of works has shown that for that reason network analysis cannot be directly applied to time-stamped network data. Existing methods to address this issue require statistics on causal paths, which is computationally challenging for big data sets.
Addressing this problem, we develop an efficient algorithm to count causal paths in time-stamped network data. Applying it to empirical data, we show that our method is more efficient than a baseline method implemented in an OpenSource data analytics package. Our method works efficiently for different values of the maximum time difference between consecutive links of a causal path and supports streaming scenarios. With it, we are closing a gap that hinders an efficient analysis of big time series data on complex networks.

Abstract

Graph or network representations are an important foundation for data mining and machine learning tasks in relational data. Many tools of network analysis, like centrality measures, information ranking, or cluster detection rest on the assumption that links capture direct influence, and that paths represent possible indirect influence. This assumption is invalidated in time-stamped network data capturing, e.g., dynamic social networks, biological sequences or financial transactions. In such data, for two time-stamped links (A,B) and (B,C) the chronological ordering and timing determines whether a causal path from node A via B to C exists. A number of works has shown that for that reason network analysis cannot be directly applied to time-stamped network data. Existing methods to address this issue require statistics on causal paths, which is computationally challenging for big data sets.
Addressing this problem, we develop an efficient algorithm to count causal paths in time-stamped network data. Applying it to empirical data, we show that our method is more efficient than a baseline method implemented in an OpenSource data analytics package. Our method works efficiently for different values of the maximum time difference between consecutive links of a causal path and supports streaming scenarios. With it, we are closing a gap that hinders an efficient analysis of big time series data on complex networks.

Statistics

Downloads

7 downloads since deposited on 17 Sep 2019
6 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Working Paper
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Date:16 August 2019
Deposited On:17 Sep 2019 12:29
Last Modified:25 Sep 2019 00:45
Series Name:arXiv.org
ISSN:2331-8422
OA Status:Green
Related URLs:https://arxiv.org/abs/1908.05976
Other Identification Number:merlin-id:18278

Download

Green Open Access

Download PDF  'Higher-Order Visualization of Causal Structures in Dynamics Graphs'.
Preview
Content: Published Version
Filetype: PDF
Size: 1MB