  Most real complex networks -- such as protein interactions, social contacts,
the internet -- are only partially known and available to us. While the process
of exploring such networks in many cases resembles a random walk, it becomes a
key issue to investigate and characterize how effectively the nodes and edges
of such networks can be covered by different strategies. At the same time, it
is critically important to infer how well can topological measurements such as
the average node degree and average clustering coefficient be estimated during
such network explorations. The present article addresses these problems by
considering random and Barab\'asi-Albert (BA) network models with varying
connectivity explored by three types of random walks: traditional, preferential
to untracked edges, and preferential to unvisited nodes. A series of relevant
results are obtained, including the fact that random and BA models with the
same size and average node degree allow similar node and edge coverage
efficiency, the identification of linear scaling with the size of the network
of the random walk step at which a given percentage of the nodes/edges is
covered, and the critical result that the estimation of the averaged node
degree and clustering coefficient by random walks on BA networks often leads to
heavily biased results. Many are the theoretical and practical implications of
such results.
