have you tried the corrected rand index ? that is implemented in a publically available R package.