Message Boards Message Boards

Networks' complexity measures with Wolfram Language?

GROUPS:

I would like to measure how complex various networks are. There are certainly many approaches, but I am interested in what we can do with tools available in the Wolfram Language. There are many discussions in the New Kind of Science book about networks. But since its publication Wolfram Language evolved significantly.

Imagine we have something more general, like a mixed multi-edge graph:

network[v_, e_] := Graph[RandomInteger[{1, v}, {e, 2}] /.
   {x_Integer, y_Integer} :> RandomChoice[{DirectedEdge[x, y], UndirectedEdge[x, y]}]]

SeedRandom[131]; g = network[20, 60]

enter image description here

Symmetries should affect complexity, and some general measure should detect that in, say, pure trees or symmetric and/or planar graphs:

TreeGraph[RandomInteger[#] <-> # + 1 & /@ Range[0, 100], GraphLayout -> "RadialDrawing"]

enter image description here

GraphData["IcosahedralGraph"]

enter image description here

Does anyone know or have any ideas for some complexity measure that we can quickly compute with Wolfram Language?

Perhaps @Hector Zenil, @Todd Rowland or @Marco Thiel could point to the right direction. Maybe there were some Wolfram Science Summer School projects about this.

POSTED BY: Vitaliy Kaurov
Answer
2 years ago

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.

POSTED BY: Todd Rowland
Answer
2 years ago

Dear Vitaliy,

I know that this does not really answer your question, but regarding symmetries in graphs I found this paper on Symmetry in Complex Networks quite interesting. I have not tried that out in Mathematica; it would be nice to get figure one in that paper for larger graphs. Mathematica does have the Command GraphAutomorphismGroup, which is also explored in this paper.

GraphAutomorphismGroup is computationally very expensive (at least as costly as isomorphism problems).

GraphAutomorphismGroup[ExampleData["NetworkGraph"]]
PermutationGroup[{Cycles[{{32, 33}}], Cycles[{{31, 32}}], Cycles[{{30, 31}}], Cycles[{{29, 30}}], Cycles[{{16, 18}}], Cycles[{{5, 11}, {6, 7}}]}]

works fine, but it would be nice to mark the symmetries in the graph directly. This here works very quickly:

GraphAutomorphismGroup[ExampleData[{"NetworkGraph", "CoauthorshipsInNetworkScience"}]]

but

GraphAutomorphismGroup[ExampleData[{"NetworkGraph", "MetabolicNetworkSaccharomycesCerevisiae"}]]

hasn't finished yet on my computer. Also Groupoids have been used to classify symmetry in graphs, for example by Ian Stewart. Note that for the directed multigraph that you have defined GraphAutomorphismGroup does not work.

Cheers,

Marco

POSTED BY: Marco Thiel
Answer
2 years ago

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

enter image description here

POSTED BY: Szabolcs Horvát
Answer
2 years ago

Hi Szabolcs,

yes, there are indeed quite interesting papers on synchronisation and symmetries in networks. Here are two more of them:

Nonlinear Dynamics on Networks - Groupoid formalism

and

Symmetry groupoids and patterns of synchrony

As a matter of fact, I also enjoyed this one:

http://www.tbiomed.com/content/8/1/21

By the way, I really need to try out the IGraph/M in Mathematica. Haven't got around to that. But I use several others of your great suggestions, such as MaTex.

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.

The authors say that it is due to the fact that many growing networks are locally tree like.

Many networks  for example the internet and the world wide web  are `growing' 4 (that is, new vertices are added to the network over time). Generically, any growth process which allows for new vertices to be added to the network one at a time naturally leads to a network with locally tree-like regions. Such locally tree-like areas are common in real-world networks and their presence is important because, while the majority of large graphs are asymmetric, it is common for large random trees to exhibit a high degree of symmetry [23], deriving from the presence of identical branches about the same fork. Thus we expect a certain degree of tree-like symmetry to be present in many real-world networks. In the following sections we determine the extent to which real-world symmetry is locally tree-like. We begin by considering the structure of network automorphism groups.

Please tell me what you think after you read it.

Cheers,

Marco

POSTED BY: Marco Thiel
Answer
2 years ago

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.

POSTED BY: Hector Zenil
Answer
7 months ago

Hi Vitaliy,

What do you mean by complexity? For instance, the complexity of random walks in the network (is this bounded or unbounded?). Or how complicated are the paths between any pair of nodes (the total number of paths is a finite number). Can complexity be associated with robustness (the effort to break the network into two connected components)? If this is the case, then one may look at combinatorial and spectral measures of robustness to elect one as a complexity measure or even create a new one, under this concept. However, this would measure only a kind of edge complexity. For tree-like networks and for networks with a complicated core and leaf vertices this would probably be misleading.

POSTED BY: Augusto Carreira
Answer
2 years ago

I meant something like Kolmogorov complexity or similar. I was hoping @Hector Zenil will comment something - he has been doing research in this domain.

POSTED BY: Vitaliy Kaurov
Answer
2 years ago

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.

POSTED BY: Charlie Brummitt
Answer
2 years ago

Following up on Charlie's post, there is a close relation to Kolmogorov randomness and other types of randomness, so any of the measures he mentions will satisfy Vitaliy's original question.

POSTED BY: Todd Rowland
Answer
2 years ago

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.

POSTED BY: Vitaliy Kaurov
Answer
2 years ago

Not related to the complexity of the graph but to the time complexity of determining graph isomorphism. For example, to generate the isomorphism group may be only feasible by brute force, but the algorithmic complexity of the whole process is minimal because the size of the program that runs the brute force search is of fixed small size.

POSTED BY: Hector Zenil
Answer
7 months ago

It looks very relevant.

I hope to find out as soon as Babai's algorithm in Mathematica is available.

POSTED BY: Buck Field
Answer
2 years ago

I am so sorry that I am joining the discussion so late. I thought I would get a notification if I was mentioned in some post or I may have overlooked it.

Yes! I have done a lot of research on graph complexity and I think I can probably safely say that I have an edge in the subject as I think I have come up with complexity characterizations of graphs and networks that are robust enough while I have revealed ways in which graph and network cannot be characterized, e.g. with Entropy. In this paper, we show how Entropy can easily be fooled or one has to make an arbitrary choice of a feature of interest, in which case you can replace your 'complexity function' (Entropy) by simply a function of the selected feature (e.g. edge density, degree sequence normality, etc).

Low Algorithmic Complexity Entropy-deceiving Graphs

So one may think, as it is suggested, that using ByteCount@Compress[network] would then make things better, and they would if there were lossless compression algorithms based upon measures other than Shannon Entropy rate! Indeed, Compress, just as LZW (and thus gzip, png and so on) are compression algorithms that look for statistical repetition and are thus nothing else but Entropy rate estimators up to the moving window length of the compression algorithm (LZW is proven to be 'universal' because the window length is a function of the running computer memory, but obviously is finite, but even if 'universal' in that sense, it is not 'universal' in the Turing algorithmic sense).

Notice also that one major issue with most (if not all, I suspect) other measures is that they are either based on linear structures such as degree sequence, or the linearize the network in some way (even as to flatten their adjacency matrices), while some others are not robust to change of network description or provide disparate values for isomorphic graphs, so loads of issues.

So what options we have? The only option around is to approximate thus the algorithmic complexity of graph (because its invariance theorem guarantees robustness) using some of the methods I introduced that are truly related to algorithmic complexity beyond Shannon Entropy, this is by way of Algorithmic Probability. Notice that the proposal for graph complexity that we introduced is a native measure of the graph dimension (e.g. dimension 2 when looking at its adjacency matrix) and thus does not linearize artificially the graph, and it we have shown both theoretically and numerically that the measure is robust and retrieves the expected complexity both for labelled and unlabelled graphs. Papers showing how and giving the technical details and sometimes some code or data to do this by your own:

Methods of Information Theory and Algorithmic Complexity for Network Biology (H. Zenil, N.A. Kiani and J. Tegnér) Seminars in Cell and Developmental Biology, vol. 51, pp. 32-43, 2016. Available here.

Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility (H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit) PeerJ Computer Science, 1:e23, 2015 Available here.

and

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. Paper available here. Preprint available here.

Finally, to explain all this, I have created 2 videos available here. And, specifically, for Graph Complexity, here.

Some WL code, and even an online complexity calculator is available here.

Sorry for the late reply @VitaliyKaurov!

POSTED BY: Hector Zenil
Answer
7 months ago

Group Abstract Group Abstract