Butterfly Counting on Uncertain Bipartite Graphs

Butterfly Counting on Uncertain Bipartite Graphs

When: Friday 29th April 2022, at 2:00 to 3:00pm
Speaker: Mr Alexander Zhou
Host: A/Prof. Hongzhi Yin
Location: On campus in 78-632(631); zoom option: https://uqz.zoom.us/j/88011798074

Abstract:

On bipartite networks, where the nodes are split cleanly into two groups, the butterfly (a 2x2 biclique) is the fundamental building block graphlet structure being used for examining network health or identifying more complex community structures. Butterfly counting has been a popular problem for many years, but as uncertain networks (where edges only exist with varying certainty) continue to surge in popularity new techniques are required to bring this old problem into a new space. In this talk we explore the Uncertain Butterfly Counting Problem, which has use cases in the fields of biology, E-Commerce, transportation and other areas. We examine (1) Exact solutions to the problem in which we improve both the theoretical and practical time cost by leveraging the inherent structural properties of butterflies and the probability theory introduced by uncertain networks; (2) Approximate solutions via two separate sampling frameworks via local counting which can rapidly converge to the global count whilst taking a fraction of the time.

Biography:

Alexander Zhou is a current 3rd Year PhD Candidate at the Hong Kong University of Science and Technology under the supervision of Prof. Lei Chen after completing his undergraduate studies at the University of Queensland. His research interests are on graph databases, taking a keen interest in communities and important subgraph structures on these networks. During his PhD studies he has published twice as first author in the top database conference VLDB and collaborated with others on multiple other top conference publications.