  K-clique percolation is an overlapping community finding algorithm which
extracts particular structures, comprised of overlapping cliques, from complex
networks. While it is conceptually straightforward, and can be elegantly
expressed using clique graphs, certain aspects of k-clique percolation are
computationally challenging in practice. In this paper we investigate aspects
of empirical social networks, such as the large numbers of overlapping maximal
cliques contained within them, that make clique percolation, and clique graph
representations, computationally expensive. We motivate a simple algorithm to
conduct clique percolation, and investigate its performance compared to current
best-in-class algorithms. We present improvements to this algorithm, which
allow us to perform k-clique percolation on much larger empirical datasets. Our
approaches perform much better than existing algorithms on networks exhibiting
pervasively overlapping community structure, especially for higher values of k.
However, clique percolation remains a hard computational problem; current
algorithms still scale worse than some other overlapping community finding
algorithms.
