## Category Archives: Network theory

In network science, one can study the dynamics of a network — nodes being added or removed, edges being rewired — or the dynamics on the network — spins flipping from up to down in an Ising model, traffic flow along subway routes, an infection spreading through a susceptible population, etc. These have often been studied separately, on the rationale that they occur at different timescales. For example, the traffic load on the different lines of the Boston subway network changes on an hourly basis, but the plans to extend the Green Line into Medford have been deliberated since World War II.

In the past few years, increasing attention has been focused on adaptive networks, in which the dynamics of and the dynamics on can occur at comparable timescales and feed back on one another. Useful references:

I might be going to this, because it’s in the neighbourhood and I suppose I ought to see what colourful examples other people use in these situations, having given similar talks a couple times myself.

MIT Physics Department Colloquium: Jennifer Chayes

“Interdisciplinarity in the Age of Networks”

Everywhere we turn these days, we find that dynamical random networks have become increasingly appropriate descriptions of relevant interactions. In the high tech world, we see mobile networks, the Internet, the World Wide Web, and a variety of online social networks. In economics, we are increasingly experiencing both the positive and negative effects of a global networked economy. In epidemiology, we find disease spreading over our ever growing social networks, complicated by mutation of the disease agents. In problems of world health, distribution of limited resources, such as water, quickly becomes a problem of finding the optimal network for resource allocation. In biomedical research, we are beginning to understand the structure of gene regulatory networks, with the prospect of using this understanding to manage the many diseases caused by gene mis-regulation. In this talk, I look quite generally at some of the models we are using to describe these networks, and at some of the methods we are developing to indirectly infer network structure from measured data. In particular, I will discuss models and techniques which cut across many disciplinary boundaries.

9 September 2010, 16:15 o’clock, Room 10-250.

By Gad, the future is an amazing place to live.

Where else could you buy this?

Or this?

(Via Clauset and Shalizi, naturally.)

I have a confession to make: Once, when I had to give a talk on network theory to a seminar full of management people, I wrote a genetic algorithm to optimize the Newman-Girvan Q index and divide the Zachary Karate Club network into modules before their very eyes. I made Movie Science happen in the real world; peccavi.

Copied from my old ScienceBlogs site to test out the mathcache JavaScript tool.

Ah, complex networks: manufacturing centre for the textbook cardboard of tomorrow!

When you work in the corner of science where I do, you hear a lot of “sales talk” — claims that, thanks to the innovative research of so-and-so, the paradigms are shifting under the feet of the orthodox. It’s sort of a genre convention. To stay sane, it helps to have an antidote at hand (“The paradigm works fast, Dr. Jones!”).

For example, everybody loves “scale-free networks”: collections of nodes and links in which the probability that a node has $k$ connections falls off as a power-law function of $k$. In the jargon, the “degree” of a node is the number of links it has, so a “scale-free” network has a power-law degree distribution.

Random fun items currently floating up through the arXivotubes include the following. Exercise: find the shortest science-fiction story which can connect all these e-prints, visiting each node only once.

Robert H. Brandenberger, “String Gas Cosmology” (arXiv:0808.0746).

String gas cosmology is a string theory-based approach to early universe cosmology which is based on making use of robust features of string theory such as the existence of new states and new symmetries. A first goal of string gas cosmology is to understand how string theory can effect the earliest moments of cosmology before the effective field theory approach which underlies standard and inflationary cosmology becomes valid. String gas cosmology may also provide an alternative to the current standard paradigm of cosmology, the inflationary universe scenario. Here, the current status of string gas cosmology is reviewed.

Dimitri Skliros, Mark Hindmarsh, “Large Radius Hagedorn Regime in String Gas Cosmology” (arXiv:0712.1254, to be published in Phys. Rev. D).

The most dangerous aspect of being trapped in the digital library’s virtual basement stacks is that you don’t want to come out.

Simon A. Levin (1992), “The Problem of Pattern and Scale in Ecology” Ecology 73, 6: pp. 1943–67. [JSTOR] [PDF].

It is argued that the problem of pattern and scale is the central problem in ecology, unifying population biology and ecosystems science, and marrying basic and applied ecology. Applied challenges, such as the prediction of the ecological causes and consequences of global climate change, require the interfacing of phenomena that occur on very different scales of space, time, and ecological organization. Furthermore, there is no single natural scale at which ecological phenomena should be studied; systems generally show characteristic variability on a range of spatial, temporal, and organizational scales. The observer imposes a perceptual bias, a filter through which the system is viewed. This has fundamental evolutionary significance, since every organism is an “observer” of the environment, and life history adaptations such as dispersal and dormancy alter the perceptual scales of the species, and the observed variability. It likewise has fundamental significance for our own study of ecological systems, since the patterns that are unique to any range of scales will have unique causes and biological consequences. The key to prediction and understanding lies in the elucidation of mechanisms underlying observed patterns. Typically, these mechanisms operate at different scales than those on which the patterns are observed; in some cases, the patterns must be understood as emerging form the collective behaviors of large ensembles of smaller scale units. In other cases, the pattern is imposed by larger scale constraints. Examination of such phenomena requires the study of how pattern and variability change with the scale of description, and the development of laws for simplification, aggregation, and scaling. Examples are given from the marine and terrestrial literatures.

Gyorgy Szabo, Gabor Fath (2007), “Evolutionary games on graphs” Physics Reports 446, 4-6: 97–216. [DOI] [arXiv].

Game theory is one of the key paradigms behind many scientific disciplines from biology to behavioral sciences to economics. In its evolutionary form and especially when the interacting agents are linked in a specific social network the underlying solution concepts and methods are very similar to those applied in non-equilibrium statistical physics. This review gives a tutorial-type overview of the field for physicists. The first three sections introduce the necessary background in classical and evolutionary game theory from the basic definitions to the most important results. The fourth section surveys the topological complications implied by non-mean-field-type social network structures in general. The last three sections discuss in detail the dynamic behavior of three prominent classes of models: the Prisoner’s Dilemma, the Rock-Scissors-Paper game, and Competing Associations. The major theme of the review is in what sense and how the graph structure of interactions can modify and enrich the picture of long term behavioral patterns emerging in evolutionary games.

SÃ©bastien Lion, Minus van Baalen (2007), “From Infanticide to Parental Care: Why Spatial Structure Can Help Adults Be Good Parents” American Naturalist 170: E26–E46. [HTML] [PDF].

I’m sitting in MIT’s lecture hall 34-101, where a Venerable Personage is introducing today’s physics colloquium speaker, Geoffrey West (Santa Fe Institute). Like most colloquium speakers (or so it seems to me) West has a string of academic honors to his name; perhaps more unusual is his membership in Time magazine’s “100 most influential people” list, for which he was profiled by Murray Gell-Mann. (At that, he had more luck than Richard Dawkins.) West’s talk will concern scaling laws in living systems, and its abstract is as follows:

Life is very likely the most complex phenomenon in the Universe manifesting an extraordinary diversity of form and function over an enormous range. Yet, many of its most fundamental and complex phenomena scale with size in a surprisingly simple fashion. For example, metabolic rate scales as the 3/4-power of mass over 27 orders of magnitude from complex molecules up to the largest multicellular organisms. Similarly, time-scales, such as lifespans and growth-rates, increase with exponents which are typically simple powers of 1/4. It will be shown how these “universal” 1/4 power scaling laws follow from fundamental properties of the networks that sustain life, leading to a general quantitative, predictive theory that captures the essential features of many diverse biological systems. Examples will include animal and plant vascular systems, growth, cancer, aging and mortality, sleep, DNA nucleotide substitution rates. These ideas will be extended to social organisations: to what extent are these an extension of biology? Is a city, for example, “just” a very large organism? Analogous scaling laws reflecting underlying social network structure point to general principles of organization common to all cities, but, counter to biological systems, the pace of social life systematically increases with size. This has dramatic implications for growth, development and sustainability: innovation and wealth creation that fuel social systems, if left unchecked, potentially sow the seeds for their inevitable collapse.

Now, let’s see if I can keep up!

SCALING BEHAVIOR

“I think it’s patently obvious that I’m not one of the hundred most influential people in the world,” West says, “which should be obvious after I’ve finished my talk.” There follows an amount of fumbling as West and the distinguished personage try to turn on the overhead projector — “We need an experimentalist!” — before the big red button is found, and the projector screen glows into life.

This is the sort of thing which tends to get taken off the Network once the Powers Which Be notice that it exists, so we should enjoy it now. Here and there, in chunks of different sizes, we can find James Burke’s original Connections (1978) TV series. Embedded on this page is the tenth and last episode, “Yesterday, Tomorrow and You.” I could say many things about it, but for now, I’ll just note that “network robustness” has become a subject of quantitative investigation, that I can’t escape the feeling the arguments which perennially perturb the science-blogging orbit still aren’t addressing the points which Burke raised thirty years ago, and that you can’t go wrong with Ominous Latin Chanting.

Xiaojuan Sun, Matjaz Perc, Qishao Lu, and JÃ¼rgen Kurths, “Spatial coherence resonance on diffusive and small-world networks of Hodgkin-Huxley neurons” (arXiv:0803.0070, accepted for publication in Chaos).

I’ve had clustering behavior in randomly generated networks on my mind, recently, so arXiv:0802.2508 naturally caught my eye. It’s entitled “Criticality of spreading dynamics in hierarchical cluster networks without inhibition.” Marcus Kaiser, Matthias Goerner and Claus C. Hilgetag write,

Luciano da Fontoura Costa, “Communities in Neuronal Complex Networks Revealed by Activation Patterns” (arXiv:0801.4684):

Recently, it has been shown that the communities in neuronal networks of the integrate-and-fire type can be identified by considering patterns containing the beginning times for each cell to receive the first non-zero activation. The received activity was integrated in order to facilitate the spiking of each neuron and to constrain the activation inside the communities, but no time decay of such activation was considered. The present article shows that, by taking into account exponential decays of the stored activation, it is possible to identify the communities also in terms of the patterns of activation along the initial steps of the transient dynamics. The potential of this method is illustrated with respect to complex neuronal networks involving four communities, each of a different type (Erdös-Rény, Barabási-Albert, Watts-Strogatz as well as a simple geographical model). Though the consideration of activation decay has been found to enhance the communities separation, too intense decays tend to yield less discrimination.

The “simple geographical model” is one I’ve played with myself, since it’s so easy to implement (and serves as a null hypothesis for some problems of interest). Throw $$N$$ nodes into a box of $$d$$ dimensions, and connect two nodes if they are closer than some fixed threshold. In this case, the box was 2D, but a 3D version is just as easy to implement.

Abbie Smith is reporting back after finding some truly frightening people in Oklahoma City. Russell Blackford has been appointed editor-in-chief of The Journal of Evolution and Technology, and Tyler DiPietro has written an informative post on the “hiring problem” in algorithm analysis and a practical application of Kolmogorov complexity.

I spent an hour after lunch today experimenting with a toy model of the science blogosphere, investigating how preferential attachment can skew the gender distribution of “Top 10″ lists even when individual bloggers are egalitarian and gender-blind. I’ve got the equations for my next SUSY QM post worked out, and a path through them mapped.

Salvo Assenza, Jesus Gomez-Gardenes and Vito Latora say in their e-print, “Enhancement of cooperation in highly clustered scale-free networks” (arXiv:0801.2416),

We study the effect of clustering on the organization of cooperation, by analyzing the evolutionary dynamics of the Prisoner’s Dilemma on scale-free networks with a tunable value of clustering. We find that a high value of the clustering coefficient produces an overall enhancement of cooperation in the network, even for a very high temptation to defect. On the other hand, high clustering homogenizes the process of invasion of degree classes by defectors, decreasing the chances of survival of low densities of cooperator strategists in the network.

Suddenly, with regard to cooperation issues, I have gone from $$N$$ papers behind to $$N + 1$$ papers behind. Question: If we construct a time-dependent network model of a population, can we represent both kin recognition and the effect of spatial distribution by node clustering?

If I didn’t have to be modifying and debugging a network-growth simulation today, I’d be reading these papers. The first is not too far from one subject I’m researching right now. Axelsen et al. (arXiv:0711.2208) write about “a tool-based view of regulatory network topology”:

The relationship between the regulatory design and the functionality of molecular networks is a key issue in biology. Modules and motifs have been associated to various cellular processes, thereby providing anecdotal evidence for performance based localization on molecular networks. To quantify structure-function relationship we investigate similarities of proteins which are close in the regulatory network of the yeast Saccharomyces cerevisiae. We find that the topology of the regulatory network show weak remnants of its history of network reorganizations, but strong features of co-regulated proteins associated to similar tasks. This suggests that local topological features of regulatory networks, including broad degree distributions, emerge as an implicit result of matching a number of needed processes to a finite toolbox of proteins.

The second, Gaume and Forterre’s “A viscoelastic deadly fluid in carnivorous pitcher plants” (arXiv:0711.4724, also in PLoS ONE), is pertinent to my eventual life goal of building an army of atomic super-plants.

Binocular rivalry is a phenomenon which occurs when conflicting information is presented to each of our two eyes, and the brain has to cope with the contradiction. Instead of seeing a superimposition or “average” of the two, our perceptual machinery entertains both possibilities in turn, randomly flickering from one to the other. This presents an interesting way to stress-test our visual system and see how vision works. Unfortunately, talk of “perception” leads to talk of “consciousness,” and once “consciousness” has been raised, an invocation of quantum mechanics can’t be too far behind.

I’m late to join the critical party surrounding E. Manousakis’ paper, “Quantum theory, consciousness and temporal perception: Binocular rivalry,” recently uploaded to the arXiv and noticed by Mo at Neurophilosophy. Manousakis applies “quantum theory” (there’s a reason for those scare quotes) to the problem of binocular rivalry and from this hat pulls a grandiose claim that quantum physics is relevant for human consciousness.

A NOTE ON WIRES AND SLINKYS

First, we observe that there is a healthy literature on this phenomenon, work done by computational neuroscience people who aren’t invoking quantum mechanics in their explanations.

Second, one must carefully distinguish a model of a phenomenon which actually uses quantum physics from a model in which certain mathematical tools are applicable. Linear algebra is a mathematical tool used in quantum physics, but describing a system with linear algebra does not make it quantum-mechanical. Long division and the extraction of square roots can also appear in the solution of a quantum problem, but this does not make dividing 420 lollipops among 25 children a correlate of quantum physics.

Just because the same equation applies doesn’t mean the same physics is at work. An electrical circuit containing a capacitor, an inductor and a resistor obeys the same differential equation as a mass on a spring: capacitance corresponds to “springiness,” inductance to inertia and resistance to friction. This does not mean that an electrical circuit is the same thing as a rock glued to a slinky.

MIXING THE QUANTUM AND THE CLASSICAL

One interesting thing about this paper is that the hypothesis is really only half quantum, at best. In fact, three of the four numbers fed into Manousakis’ hypothesis pertain to a classical phenomenon, and here’s why:

Manousakis invokes the formalism of the quantum two-state system, saying that the perception of (say) the image seen by the left eye is one state and that from the right eye is the other. The upshot of this is that the probability of seeing the illusion one way — say, the left-eye version — oscillates over time as

$$P(t) = \cos^2(\omega t),$$

where $$\omega$$ is some characteristic frequency of the perceptual machinery. The oscillation is always going, swaying back and forth, but every once in a while, it gets “observed,” which forces the brain into either the clockwise or the counter-clockwise state, from which the oscillation starts again.

The quantum two-state system just provides an oscillating probability of favoring one perception, one which goes as the square of $$\cos(\omega t)$$. Three of the four parameters fed into the Monte Carlo simulation actually pertain to how often this two-state system is “observed” and “collapsed”. These parameters describe a completely classical pulse train â€” click, click, click, pause, click click click click, etc.

What’s more, the classical part is the higher-level one, the one which intrudes on the low-level processing. Crudely speaking, it’s like saying there’s a quantum two-state system back in the visual cortex, but all the processing up in the prefrontal lobes is purely classical.