Iceberg Clique queries in large graphs

This paper investigates the Iceberg Clique (IC) queries in a large graph, specially, given a user-specified threshold θ, an IC query reports the cliques where the number of vertices exceeds ⌊θ|V|⌋. Toward this end, a practical IC query theorem is formally proposed and proved. With this proposed query theorem, a formal context and its corresponding iceberg concept lattice are first constructed from an input graph topology by Modified Adjacency Matrix; then, we prove that the IC queries problem is equivalent to finding the iceberg equiconcepts whose number of elements exceeds ⌊θ|V|⌋. Theoretical analysis and experimental results demonstrate that the proposed query algorithm is feasible and efficient for finding the iceberg cliques from large graphs.