UC Irvine

Graph theory has extensive applications across various fields, such as social science, biology, and physics. One prominent graph-related task is the search for subgraphs possessing significantly higher edge densities than the mean; such subgraphs are referred to as communities. Community detection is an NP-hard problem, and existing algorithms addressing this problem are categorized between those that try to find a partition of non-overlapping communities, and those that find overlapping communities.

In this work, we reimagine the definition of community and propose a novel algorithm for overlapping community detection based on graphlet sampling using BLANT, a subgraph sampling method developed at UCI by the Wayne Hayes's Lab. By adopting a definition that emphasizes uniformly dense subgraphs and allows for edges extending beyond the community boundaries, our algorithm offers an extensive collection of dense overlapping communities. Furthermore, it introduces a community overlap graph, providing users with insights into the degree of overlap and empowering them to identify relevant communities based on their specific use cases. Our algorithm, BLANT-clusters, demonstrates the ability to discover larger and denser communities compared to existing state-of-the-art methods. We discuss the strengths and weaknesses of our algorithm and provide a comparative analysis with current approaches. Finally, we conclude by outlining potential future work and applications for subsequent iterations of this method, highlighting the potential capability of achieving near-optimal community discovery.