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.
200 University Avenue West
Waterloo, ON N2L 3G1