Not logged in.
Quick Search - Contribution
Contribution Details
Type | Conference or Workshop Paper |
Scope | Discipline-based scholarship |
Published in Proceedings | Yes |
Title | When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks |
Organization Unit |
|
Authors |
|
Presentation Type | paper |
Item Subtype | Original Work |
Refereed | Yes |
Status | Published in final form |
Language |
|
ISBN | 9781450348874 |
Page Range | 1037 - 1046 |
Event Title | the 23rd ACM SIGKDD International Conference |
Event Type | conference |
Event Location | Halifax, NS, Canada |
Event Start Date | September 13 - 2017 |
Event End Date | September 17 - 2017 |
Place of Publication | New York, New York, USA |
Publisher | ACM Press |
Abstract Text | We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in the Web, travel patterns in transportation systems, information cascades in social networks, biological pathways, or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: When is a network abstraction of sequential data justified?Addressing this open question, we propose a framework that combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms baseline Markov order detection techniques. An application to eight real-world data sets on pathways and temporal networks shows that it allows to infer graphical models that capture both topological and temporal characteristics of such data. Our work highlights fallacies of network abstractions and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and knowledge discovery algorithms. |
Digital Object Identifier | 10.1145/3097983.3098145 |
Export |
BibTeX
EP3 XML (ZORA) |