# Category Archives: Network theory

Google Scholar is definitely missing citations to my papers.

The cited-by results for “Some Negative Remarks on Operational Approaches to Quantum Theory” [arXiv:1401.7254] on Google Scholar and on INSPIRE are completely nonoverlapping. Google Scholar can tell that “An Information-Theoretic Formalism for Multiscale Structure in Complex Systems” [arXiv:1409.4708] cites “Eco-Evolutionary Feedback in Host–Pathogen Spatial Dynamics” [arXiv:1110.3845] but not that it cites My Struggles with the Block Universe [arXiv:1405.2390]. Meanwhile, the SAO/NASA Astrophysics Data System catches both.

This would be a really petty thing to complain about, if people didn’t seemingly rely on such metrics.

EDIT TO ADD (17 November 2014): Google Scholar also misses that David Mermin cites MSwtBU in his “Why QBism is not the Copenhagen interpretation and what John Bell might have thought of it” [arXiv:1409.2454]. This maybe has something to do with being worse at detecting citations in footnotes than in endnotes.

# Multiscale Structure via Information Theory

We have scienced:

B. Allen, B. C. Stacey and Y. Bar-Yam, “An Information-Theoretic Formalism for Multiscale Structure in Complex Systems” [arXiv:1409.4708].

We develop a general formalism for representing and understanding structure in complex systems. In our view, structure is the totality of relationships among a system’s components, and these relationships can be quantified using information theory. In the interest of flexibility we allow information to be quantified using any function, including Shannon entropy and Kolmogorov complexity, that satisfies certain fundamental axioms. Using these axioms, we formalize the notion of a dependency among components, and show how a system’s structure is revealed in the amount of information assigned to each dependency. We explore quantitative indices that summarize system structure, providing a new formal basis for the complexity profile and introducing a new index, the “marginal utility of information”. Using simple examples, we show how these indices capture intuitive ideas about structure in a quantitative way. Our formalism also sheds light on a longstanding mystery: that the mutual information of three or more variables can be negative. We discuss applications to complex networks, gene regulation, the kinetic theory of fluids and multiscale cybernetic thermodynamics.

There’s much more to do, but for the moment, let this indicate my mood:

# 10 LINKS 20 GOTO 10

My “Worked Physics Homework Problems” book now stands at 372 pages. If you ever wonder what I do instead of meeting people.

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:

# Colloquium on Complex Networks

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.

# Complexity Swag

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.

# How Not to be a Network-Theory n00b

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.
Continue reading How Not to be a Network-Theory n00b

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

# Liveblagging: Geoffrey West

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.

# Connections, Episode 10

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).

# On the arXivotubes

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,

# In Happier News, the ArXivotubes

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.

# Happenings

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.

# On the arXivotubes

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?