The Web Conference (WWW) is the premier international venue focused on understanding the current state and the evolution of the Web through the lens of computer science, computational social science, economics, policy, and many other disciplines. The 31th Web Conference (WWW 2022) will be hosted by Lyon, France from April 25th to 29th. This year, the conference received 1822 submissions and accepted 323 of them as full papers. The acceptance ratio is 17.7%. Our below submission was selected to present on the conference. Congratulations to all authors! The first author Zhengren Wang is a year-three undergraduate student.

Title: Listing Maximal k-Plexes in Large Real-World Graphs

Authors: Zhengren Wang, Yi Zhou, Mingyu Xiao and Bakhadyr Khoussainov

In this paper, we study the problem of listing maximal k-plexes in large real-world graphs, which is highly significant in many domains such as data mining, bio-informatics and ad-hoc wireless network. We propose ListPlex, an algorithm that lists all maximal k-plexes with a guaranteed worst-case running time bound. From algorithmic perspective, we suggest strong prune rules to reduce the search space of our algorithm. From the computational system perspective, we propose new data structures to reduce cache misses and increase parallelism. Experiments show that ListPlex outperforms the state-of-the-art approaches and all optimization techniques bring evident speedup.