I wonder how relevant this will turn out to be: Mathematician claims breakthrough in complexity theory

László Babai, a mathematician and computer scientist at the University of Chicago in Illinois, has developed a mathematical recipe or "algorithm" that supposedly can take two networks—no matter how big and tangled—and tell whether they are, in fact, the same, in far fewer steps than the previous best algorithm. ... Babai has shown that a problem that was thought to be on the harder NP end of the spectrum is closer to the easier P end, instead.

Statistical physicists have focused on random models of networks. You could construct a "null model" that capture some aspect of the network (such as all graphs that have the same degree distribution) and see how different your network is to that null model on certain dimensions (e.g., clustering, motifs, path length distribution, hierarchical structure, or whatever you think might be important for your network). If your network is not statistically significantly different from your null model, then your network is a "simple" as your null model (which may have few parameters and hence is quite "simple"); otherwise, you have a lower bound on the "complexity" of your network.

This paper shows the relationship between complexity and the graph automorphism group size:

Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks H. Zenil, F. Soler-Toscano, K. Dingle and A. Louis Physica A: Statistical Mechanics and its Applications, vol. 404, pp. 341–358, 2014.

Available online here, and preprint here.

Networks are notoriously difficult to measure in their complexity in any satisfactory way. One cannot rely on visualizations like you can with cellular automata. Keep in mind that even strings have no satisfactory measure, but there are measures for any expression like

StringLength[Compress[expr]]

The ones you can use for strings (with their drawbacks) you can also use for networks, and Wolfram Language is inherently one dimensional so there is, at least from some perspective, little difference when talking about general complexity.

Instead of asking for general measures of complexity, it makes more sense to talk about specific types of networks, and what sorts of algorithms construct them, or how they are being used, and custom tailor the method to that.