Dear Zachary,
The following is a remote connection only, but let me mention it anyway.
In Section 7 of
Snijders, T.A.B. & Nowicki, K., Estimation and prediction for stochastic block models for graphs with latent block structure.
Journal of Classification, 14 (1997), 75 - 100.
a procedure is mentioned for classifying vertices into 2 groups ("colors"), which is mentioned to be similar to CONCOV (note the V at the end). For the mentioned procedure, it is proven that if the model is a stochastic block model with 2 colors for undirected graphs, then classification ("color recovery") is asymptotically perfect.
Perhaps the idea there can be used also to prove this type of asymptotically perfect color recovery for CONCOV itself, and then also for CONCOR.
Cheers,
Tom
=========================================
Tom A.B. Snijders
Professor of Statistics and Methodology, Dept of Sociology, University of Groningen
Emeritus Fellow, Nuffield College, University of Oxford
http://www.stats.ox.ac.uk/~snijders