I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices.
Here is an example of a randomized algorithm which is the best I could think of for now. Supposing that there are $|V|$ vertices, and the max clique is of size $|V| - k$ this returns a clique of size around $|V| - 2k$ with high probability, which is nontrivial if $k < |V|/2$ and approaches $|V|$ itself as $k$ shrinks.
Starting with the set of all vertices, arbitrarily choose pairs with no edge, then eliminate one member at random, and repeat until you have a clique.
Since one of the members of each conflicting pair must be outside the maximum clique, the expected number of vertices outside the clique removed after $2k$ iterations is at least $k$. We can therefore expect the algorithm to terminate in $2k$ rounds or so (with a concentration inequality argument and some leeway). This leaves us with a clique of the size mentioned above.
Is there a way to make this algorithm deterministic? Can we do better than this ~twofold expansion in the size of the "bad" vertices?