A Novel Graphlet-Based Community Detection Algorithm

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-there is even disagreement on the technical definition of what constitutes a community of nodes. We define a community as any set of nodes in which the edge density is uniformly higher by a substantial margin than the network's overall edge density. In this article, we introduce an entirely novel algorithm with no relation to any existing algorithm: 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, the community has an edge density that is 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.