1. A computing system comprising at least one computing device and at least one data store in communication with the at least one computing device, the at least one data store having stored therein computer-readable instructions that, upon execution by the at least one computing device, cause at least: identifying a first set of computing nodes of a provider network for installation of network analysis agents; selecting allocations of the network analysis agents for the installation on the first set of computing nodes; receiving network route tracing data from the allocated network analysis agents comprising information usable to identify network paths between pairs of computing nodes in the first set of computing nodes; based on the network route tracing data, quantifying non-redundant network paths between the pairs of computing nodes in the first set of computing nodes; determining which of the pairs of computing nodes in the first set of computing nodes are linked by a number of non-redundant network paths that exceed a target number of non-redundant network paths; de-allocating the network analysis agents installed on those pairs of computing nodes in the first set of computing nodes that are determined to be linked by the number of non-redundant network paths that exceed the target number; and replacing the de-allocated network analysis agents with additional network analysis agents on randomly selected computing nodes.