Named entities in a document are identified. Each named entity is classified as either anonymous or public based on analysis including at least syntactic analysis of one or more portions of the document containing the named entity. In one suitable approach, each named person entity is classified by default as anonymous, and each named entity that is not a named person is classified by default as public. Named entities are selectively re-classified based on evidence contained in the document indicating that the default classification is incorrect. The classification of a named entity as either anonymous or public is propagated to multiple occurrences of that named entity in the document Those named entities classified as anonymous are anonymized.