  Considering a clique as a conservative definition of community structure, we
examine how graph partitioning algorithms interact with cliques. Many popular
community-finding algorithms partition the entire graph into non-overlapping
communities. We show that on a wide range of empirical networks, from different
domains, significant numbers of cliques are split across the separate
partitions produced by these algorithms. We then examine the largest connected
component of the subgraph formed by retaining only edges in cliques, and apply
partitioning strategies that explicitly minimise the number of cliques split.
We further examine several modern overlapping community finding algorithms, in
terms of the interaction between cliques and the communities they find, and in
terms of the global overlap of the sets of communities they find. We conclude
that, due to the connectedness of many networks, any community finding
algorithm that produces partitions must fail to find at least some significant
structures. Moreover, contrary to traditional intuition, in some empirical
networks, strong ties and cliques frequently do cross community boundaries;
much community structure is fundamentally overlapping and unpartitionable in
nature.
