Abstract: Community detection is a long-standing problem with applications from social networks to biology. Given its popularity and that it is NP-complete, heuristics abound, though no gold standard exists. In this talk, I will introduce an entirely novel, graphlet-based algorithm for community detection: given an edge density threshold epsilon, we build a community that has edge density above epsilon by building them from sampled graphlets (small induced subgraphs) that themselves have density above epsilon. By conglomerating and merging these graphlets, we build a community with edge density uniformly above the threshold. We show that this algorithm almost universally outperforms existing algorithms chosen widely across the literature (biological and non-biological) in the problem of overlapping community detection, in that it finds larger and more dense communities in virtually every test case. Finally, we run our code through the 2016 DREAM challenge for community detection in biological networks, and show that it finds substantially more dense communities than the DREAM competition winners.
 

Bio: Wayne Hayes received his Ph.D. in Computer Science from the University of Toronto, where he learned from the Faloutsos brothers how to party late into the night. He did a post-doc with Jim Yorke (where there was less partying despite Jim being one of the literal inventors of Chaos Theory). In 2004 he woke up in sunny Irvine, California, where he has been warping the young minds of Computer Science students for 21 years. In his spare time he enjoys graph theory, star gazing, and analyzing images of galaxies.