  In this paper, we investigate the problem of (k,r)-core which intends to find
cohesive subgraphs on social networks considering both user engagement and
similarity perspectives. In particular, we adopt the popular concept of k-core
to guarantee the engagement of the users (vertices) in a group (subgraph) where
each vertex in a (k,r)-core connects to at least k other vertices. Meanwhile,
we also consider the pairwise similarity between users based on their profiles.
For a given similarity metric and a similarity threshold r, the similarity
between any two vertices in a (k,r)-core is ensured not less than r. Efficient
algorithms are proposed to enumerate all maximal (k,r)-cores and find the
maximum (k,r)-core, where both problems are shown to be NP-hard. Effective
pruning techniques significantly reduce the search space of two algorithms and
a novel (k,k')-core based (k,r)-core size upper bound enhances performance of
the maximum (k,r)-core computation. We also devise effective search orders to
accommodate the different nature of two mining algorithms. Comprehensive
experiments on real-life data demonstrate that the maximal/maximum (k,r)-cores
enable us to find interesting cohesive subgraphs, and performance of two mining
algorithms is significantly improved by proposed techniques.
