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.

Somehow I find it very strange that real-world networks would have any non-trivial symmetries. I'll need to take a look at that paper when I have time. For a real-world network (i.e. something having a lot of noise) I would expect the only symmetries to arise either from "exchangeable" degree-1 nodes connected to the same other node, or maybe sometimes from complete subgraphs.

As for ExampleData[{"NetworkGraph", "MetabolicNetworkSaccharomycesCerevisiae"}], the Bliss algorithm available through IGraph/M handles this easily:

g = ExampleData[{"NetworkGraph", "MetabolicNetworkSaccharomycesCerevisiae"}];

<< IGraphM`

group = IGBlissAutomorphismGroup[g];

These are the generators of the group:

PermutationCycles /@ group

{Cycles[{{200, 249}, {201, 250}}], 
 Cycles[{{480, 484}, {481, 485}, {1041, 1042}, {1113, 1449}}], 
 Cycles[{{536, 539}, {537, 540}, {610, 615}, {611, 616}, {1262, 
    1268}, {1263, 1269}, {1264, 1270}}], 
 Cycles[{{541, 557}, {617, 642}, {949, 1271}, {952, 1272}}], 
 Cycles[{{1315, 1438}}], Cycles[{{1497, 1498}}]}

BTW there are some interesting papers on how graph symmetries affect synchronization networks: http://arxiv.org/abs/1211.5390

EDIT:

Indeed if we look at which nodes of this metabolic network participate in the symmetries, they all turn out to be low-degree periphery nodes, as I would expect. Below you can see the neighbourhood of these nodes.

In[155]:= vi = Flatten /@ First /@ PermutationCycles /@ group

In[156]:= Table[
 vv = VertexList[g][[ind]];
 HighlightGraph[
  NeighborhoodGraph[g, vv, 2],
  vv
  ],
 {ind, vi}
 ]