Please note: This PhD seminar will be given online.
Aida
Sheshbolouki, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
In this seminar, I will talk about a project at the intersection of exploratory graph analysis and streaming graph processing. I will begin with presenting the statistical analysis of bipartite streaming graphs aimed to draw temporal emergence patterns of 2,2-bicliques known as butterflies (particularly, the “butterfly densification power law” and its origins). Next, I will introduce “sGrapp,” a streaming graph approximation framework for butterfly counting, which is inspired by the identified temporal patterns. sGrapp is based on (a) a novel stream processing scheme which adapts to the temporal distribution of the stream and (b) a novel algorithm for exact butterfly counting in streaming graph snapshots. This new exact counting algorithm is also extended to compute butterfly support (i.e., the number of butterflies incident on each vertex) in streaming graph snapshots. Experimental studies of sGrapp show outstanding performance in terms of accuracy and throughput. The results signify outperforming the only existing butterfly approximation method specialized for bipartite streaming graphs.