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}
]