This work demonstrates that the theoretical framework of complex networks typically used to study systems such as social networks or the World Wide Web can be also applied to material science, allowing deeper understanding of fundamental physical relationships. In particular, through the application of the network theory to carbon nanotubes or vapour-grown carbon nanofiber composites, by mapping fillers to vertices and edges to the gap between fillers, the percolation threshold has been predicted and a formula that relates the composite conductance to the network disorder has been obtained. The theoretical arguments are validated by experimental results from the literature. ; Effort sponsored by the Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant number FA8655-06-1-3009. We acknowledge also the Foundation for Science and Technology, Lisbon, through the 3 Quadro Comunitario de Apoio, the POCTI and FEDER programs, the PTDC/CTM/69316/2006 grant and the NANO/NMed-SD/0156/2007 project. JS acknowledges FCT grant SFRH/BD/60623/2009.