Example methods disclosed herein to localize anomalies in a communication network include identifying a first set of abnormal nodes in the communication network, and including respective ones of the first set of abnormal nodes having a number of normal direct descendent nodes that is less than a combined number of abnormal direct descendent nodes and indeterminate direct descendent nodes in a set of candidate nodes. Such disclosed example methods also include iteratively selecting ones of the set of candidate nodes to include in a set of root cause abnormal nodes representing sources of the anomalies in the communication network. In such disclosed example methods, the ones of the set of candidate nodes are selected based on sizes of respective subsets of the abnormal nodes from the first set of abnormal nodes covered by the candidate nodes.