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 <i>constitutes</i> a community of nodes. We define a <i>community</i> as any set of nodes in which the edge density is <i>uniformly</i> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi></mml:math>, we build a community that has edge density above <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi></mml:math> by building them from sampled <i>graphlets</i>-small induced subgraphs-that themselves have density above <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi></mml:math>. By conglomerating and merging these graphlets, the community has an edge density that is <i>uniformly</i> 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.