Integrated information theory of consciousness is a complex mathematical model of information transfer in neural networks.
Some of its conclusions are obvious: neither fully disconnected nor the complete structures have integrated information because it's "too primitive".
Only intricate, multilevel structures may be related to consciousness.
The procedure for calculating the measure of integrated information in IIT is enough complicated. I wondered what relatively simple well-known graph measures can be used to estimate integrated information.
It is known that the number of edges of complete graph is $n\cdot(n-1)/2$, so "optimal" structures should have number of edges not far from $n\cdot(n-1)/4$
But this tells us nothing about the internal structure of the graph, which can be quite different for the same number of edges.
It seems that we should think about some graph clustering measure. But clustering coefficient shows a rather ambiguous results. So I have "invented" own measure which is very naive but shows more interesting results.
Let $g$ is a connected subgraph of graph $G$ with $n_g$ edges ("internal links") and $m_g$ - the number of edges connecting $g$ with $G\diagdown g$ ("external links"). So my measure for clustering of $g$ is just $\varkappa=n_g/m_g$
My first question is: Is there already such a definition? Does it make some nontrivial sense?
At the moment, it is impossible for me to offer a measure of clustering all the graph based on $\varkappa$ for subgraphs. But (log) histograms of possible values $\varkappa$ for a given order of subgraphs look interesting.
Is there simple explanation for the specific form of the envelope of (log) histograms? Whether the spectrum of $\varkappa$ is to be a non-trivial measure of structuring of the graph?
One way to quantify the complexity of a data structure (like your graph) is to determine its compressibility or "information content" as defined by Algorithmic Information Theory. What you'll need to do is encode each graph into a binary string. A simple convention is give here, where adjacency matrix is transformed into a string of trinary-values elements. E.g. 100#010#001 codes the 3x3 identity matrix.
You will then need to feed each string into a lossless compression algorithm and get its resulting size. The size of the file should correlate to the complexity of your graph (given the SAME number of nodes).
Anyway, one idea to help you out.