  Network inference is a rapidly advancing field, with new methods being
proposed on a regular basis. Understanding the advantages and limitations of
different network inference methods is key to their effective application in
different circumstances. The common structural properties shared by diverse
networks naturally pose a challenge when it comes to devising accurate
inference methods, but surprisingly, there is a paucity of comparison and
evaluation methods. Historically, every new methodology has only been tested
against \textit{gold standard} (true values) purpose-designed synthetic and
real-world (validated) biological networks. In this paper we aim to assess the
impact of taking into consideration aspects of topological and information
content in the evaluation of the final accuracy of an inference procedure.
Specifically, we will compare the best inference methods, in both
graph-theoretic and information-theoretic terms, for preserving topological
properties and the original information content of synthetic and biological
networks. New methods for performance comparison are introduced by borrowing
ideas from gene set enrichment analysis and by applying concepts from
algorithmic complexity. Experimental results show that no individual algorithm
outperforms all others in all cases, and that the challenging and non-trivial
nature of network inference is evident in the struggle of some of the
algorithms to turn in a performance that is superior to random guesswork.
Therefore special care should be taken to suit the method to the purpose at
hand. Finally, we show that evaluations from data generated using different
underlying topologies have different signatures that can be used to better
choose a network reconstruction method.
