Isoperimetric number v.s synchronization

The isoperimetric number or Cheeger constant is an indicator of the “bottleneckedness” of a network.

This measure is an NP measure and can only be calculated partially. It gives an estimation of the existence of a big enough group of nodes with too few connections to the rest of the network, meaning that this group of nodes will act as a bottleneck.

There is a curious relationship between the Isoperimetric number i(A) of a network A and the capacity to synchronize. This relationship is connected with a very interesting number that is associated with any network which is the algebraic connectivity which is the is the second-smallest eigenvalue of the Laplacian matrix of A. If this value is zero implies that the network is disconnected. The bigger it is this value the better will synchronize the network. Then, the interesting relationship is that i(A) \geq \frac{1}{2}\lambda_2 ; where \lambda_2 is the second smallest eigenvalue of the net Laplacian. Therefore a network that synchronize well will have a big i(A) meaning that will not have bottlenecks.

That seems to imply that a network with bottlenecks synchronize worst that one without them.
Our brain dedicates a big part of its volume to connect different parts of the cortex (white matter) and other different regions. The white matter made of axons seems to try to give a good connection opportunity to the neurons, reducing bottlenecks.

Is this, maybe, the way the brain has to increase the Isoperimetric number of the network and reduce bottlenecks, increasing the possibility to have different parts of it in synchrony?…..uhhmmmm
An interesting point, is that the isoperimetric number is given by the group of nodes with smaller connectivity to the rest of the network, that implies that a good network can be seriously deteriorated by a significant group of nodes with a bottleneck. Even if we have only one of this nodes…..uhmmmm again
We will have to consider as well the inhibitory connections, which are an important part of synchronization in the brain. Too low inhibition produces explosion and too high inactivity.Actually inhibition is a way to control the network structure (when a neuron is inhibited all connections through it are closed) in a time dependent way. Neuron dynamics change connectivity and connectivity changes neuron dynamics, what makes the result horridly complex.

Friendship network image

Look to this page http://www.facebook.com/note.php?note_id=469716398919

It is a very interesting entry of a person in Facebook who has made a diagram on the friendship network in the world (using facebook data). I have it right now as my screen saver. It is great.

I am not sure but looking to the diagram I think you can appreciate it is small-world and scale free.

  • Small world: there are clear big connections but between the big connected points there are also clear small connections to many other points. So, the typical patterns of small world is maintained, a big number of links to your neighborhood plus always a very small number to other remote locations.
  • Scale free: It is difficult to say it without looking to the distribution of the number of links coming out of any single point. If this distribution follows a power law  P(k) \sim k^{-c}, then, we can say that the network is scale free. For the Barabassi & Adler scale free networks the constant c is between 2 and 3. Well, this is difficult to say looking to the diagram, but another curious property of these networks is that the number of links per node looks like a fractal, meaning that if you erase the nodes with highest number of links the remaining nodes maintain the link connectivity architecture (the overall aspect of the network). A consequence of that: the distribution of links coming out of a node (what is called the degree of the node) is a heavy tail distribution, that is, it is quite possible to have nodes with very, very small number of links and with very big, big numbers as well. In contrast, with the light tail distributions where it is impossible to have so small and big values (for example, the human heights distribution is light tail as it is impossible to find people  10 m tall or 10 cm tall, but, curiously 🙂 the richness distribution is heavy tail, I don’t need to give examples….)
Well, too much by now…….I hope it was interesting