The human brain -- what kind of graph would it be? I've read an article about a comparison between human brain and artificial neural networks. It's said that human brain contains $\approx 10^{11}$ neurons and each neuron is connected to $\approx 10^4$ others! Is it possible? What kind of graph would it be?
 A: The network you are describing is called the connectome.  The study of real-world networks, such as brain networks, is a enormous task, largely due to the sheer size of the network.  However, there are other complicating factors:


*

*There are different ways to interpret what constitutes an "edge" (e.g. physical connectivity, electrical signalling, or chemical signalling).

*Different people have different connectomes.  Brains change over time (particularly during child development).

*There are different technologies and methods for mapping the connectome, which don't always agree.
However, there are some things that can be said about the connectome.  For example:


*

*The organisation of these networks (e.g. clustering), allows for robustness and flexibility.

*They display "broad scale" degree distribution (like scale-free, but there is a kind of cut-off on the maximum degree).
I'm sure there are many other things that can be said about connectomes that I'm not familiar with.  They tend, however, to be rather general in flavour.
References:


*

*M. Kaiser, A tutorial in connectome analysis: Topological and spatial features of brain networks, NeuroImage, 57 (2011) 892–907.

*T. B. Leergaard, C. C. Hilgetag and O. Sporns, Mapping the connectome: multi-level analysis of brain connectivity, Front. Neuroinform. (2012).

*Yasser Iturria-Medina et al., Studying the human brain anatomical network via diffusion-weighted MRI and Graph Theory, NeuroImage, 40 (2008) 1064–1076.

*O. Sporns, Networks of the Brain, MIT Press, 2011.
A: A graph with a lot of vertices ... Unless you provide further information about the local, or global behavior, nothing much else can be said.
