Partitioning Communication Streams Into Graph Snapshots

Jeremy D. Wendt, Richard V. Field, Cynthia A. Phillips, Arvind Prasadan, Tegan Wilson, Sucheta Soundarajan, Sanjukta Bhowmick

Research output: Contribution to journalArticlepeer-review

Abstract

We present EASEE (Edge Advertisements into Snapshots using Evolving Expectations) for partitioning streaming communication data into static graph snapshots. Given streaming communication events (A talks to B), EASEE identifies when events suffice for a static graph (a <italic>snapshot</italic>). EASEE uses combinatorial statistical models to adaptively find when a snapshot is stable, while watching for significant data shifts &#x2013; indicating a new snapshot should begin. If snapshots are not found carefully, they poorly represent the underlying data &#x2013; and downstream graph analytics fail: We show a community detection example. We demonstrate EASEE&#x0027;s strengths against several real-world datasets, and its accuracy against known-answer synthetic datasets. Synthetic datasets&#x0027; results show that (1) EASEE finds known-answer data shifts very quickly; and (2) ignoring these shifts drastically affects analytics on resulting snapshots. We show that previous work misses these shifts. Further, we evaluate EASEE against seven real-world datasets (330&#x00A0;K to 2.5B events), and find snapshot-over-time behaviors missed by previous works. Finally, we show that the resulting snapshots&#x0027; measured properties (e.g., graph density) are altered by how snapshots are identified from the communication event stream. In particular, EASEE&#x0027;s snapshots do not generally &#x201C;densify&#x201D; over time, contradicting previous influential results that used simpler partitioning methods.

Original languageEnglish (US)
Pages (from-to)1-18
Number of pages18
JournalIEEE Transactions on Network Science and Engineering
DOIs
StateAccepted/In press - 2022

Keywords

  • datasets
  • graph sampling
  • network evolution
  • social networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Partitioning Communication Streams Into Graph Snapshots'. Together they form a unique fingerprint.

Cite this