Generating Graph Snapshots from Streaming Edge Data

ABSTRACT

We study the problem of determining the proper aggregation granularity for a stream of time-stamped edges. Such streams are used to build time-evolving networks, which are subsequently used to study topics such as network growth. Currently, aggregation lengths are chosen arbitrarily, based on intuition or convenience. We describe ADAGE, which detects the appropriate aggregation intervals from streaming edges and outputs a sequence of structurally mature graphs. We demonstrate the value of ADAGE in automatically finding the appropriate aggregation intervals on edge streams for belief propagation to detect malicious files and machines.

References

1. R. S. Caceres. Temporal Scale of Dynamic Networks. PhD thesis, University of Illinois at Chicago, 2013.
2. E. Keogh, S. Chu, D. Hart, and M. Pazzani. An online algorithm for segmenting time series. In ICDM, pages 289--296, 2001.
3. J. Kiernan and E. Terzi. Constructing comprehensive summaries of large event sequences. TKDE, 3(4):21:1--21:31, 2009.

Index Terms

• Human-centered computing

  • Collaborative and social computing

    • Collaborative and social computing theory, concepts and paradigms

      • Social networks

• Information systems

  • Information systems applications

    • Data mining