  Complex networks are at the core of an intense research activity. However, in
most cases, intricate and costly measurement procedures are needed to explore
their structure. In some cases, these measurements rely on link queries: given
two nodes, it is possible to test the existence of a link between them. These
tests may be costly, and thus minimizing their number while maximizing the
number of discovered links is a key issue. This paper studies this problem: we
observe that properties classically observed on real-world complex networks
give hints for their efficient measurement; we derive simple principles and
several measurement strategies based on this, and experimentally evaluate their
efficiency on real-world cases. In order to do so, we introduce methods to
evaluate the efficiency of strategies. We also explore the bias that different
measurement strategies may induce.
