  Complex networks obtained from the real-world networks are often
characterized by incompleteness and noise, consequences of limited sampling as
well as artifacts in the acquisition process. Because the characterization,
analysis and modeling of complex systems underlain by complex networks are
critically affected by the quality of the respective initial structures, it
becomes imperative to devise methodologies for identifying and quantifying the
effect of such sampling problems on the characterization of complex networks.
Given that several measurements need to be applied in order to achieve a
comprehensive characterization of complex networks, it is important to
investigate the effect of incompleteness and noise on such quantifications. In
this article we report such a study, involving 8 different measurements applied
on 6 different complex networks models. We evaluate the sensitiveness of the
measurements to perturbations in the topology of the network considering the
relative entropy. Three particularly important types of progressive
perturbations to the network are considered: edge suppression, addition and
rewiring. The conclusions have important practical consequences including the
fact that scale-free structures are more robust to perturbations. The
measurements allowing the best balance of stability (smaller sensitivity to
perturbations) and discriminability (separation between different network
topologies) were also identified.
