Tag Archives: network

AAA Recap, 2013

I guess it’s that time of the year. You know, when I recap, in my bittersweet way, the annual meeting of the American Anthropological Association? I am an anthropologist, yes, but I am deeply torn in my feelings for my discipline, my department, and my flagship (?) professional organization. The question mark arises because I am also a physical anthropologist and a demographer, so an argument can be made that my flagship professional organization is actually AAPA or PAA, but there is something about the unmarked category that is AAA. It’s supposed to represent anthropologists, broadly construed. I honestly don’t think that it does a very good job at this, but the reasons behind that are complex and I’ve only allocated myself a bit of time to blog since I’m desperately trying to catch up from all the travel I’ve done recently.

The meeting this year was in Chicago, which is a pretty amazing town. I stayed in the the Blackstone Renaissance Hotel, which was recently renovated in a lovely Art Deco theme. We did Chicago stuff. Tube steaks were eaten, the quantity of cheese that can be crammed into a deep-dish pizza was marveled at, beer was drunk.

AAA is a pretty bizarre scene. For starters, it’s at the weirdest time. It seems like the peculiar timing of AAA during November must be disruptive for just about every academic anthropology department, particularly because it is nearly a week-long endeavor. It seems that the life in an American university carries on just fine without the anthropologists around for a week in the middle of the Fall term, thank you very much. A couple innovations this year struck me as particularly incongruous, given the content of much current scholarship in anthropology. First, anyone who registered for the meeting as a non-member was given a yellow badge holder to mark them as outsiders. This seemed a bit gratuitous. I’m not sure what’s gained from such marking — they already pay a substantially higher rate for the privilege of attending, do they also need to be shamed for their lack of faith? Second, in the hall outside the main bunch of conference rooms, there was a television that played a loop of anthropologists talking about how important anthropology is. This struck me as unnecessarily propagandistic and it’s not at all clear to me who the target audience for this performance was. Presumably, those of us who were there already think that anthropology is a worthwhile endeavor. Seems to me that it’s the rest of the world we need to convince. Once again, there appears to be almost nothing considered newsworthy to emerge from this meeting of 6,000+ scholars with the exception of a paper on the similarities in street-scanning behaviors by police and fashion scouts.

Another strange feature of AAAs is that computers, cables, remotes, laser-pointers, etc. were not provided in the conference rooms but needed to be provided by the session chairs. This is the first time I’ve experienced this in years at a major conference and it definitely slowed us down quite a bit at the start of our session. I’m not sure what was going on with that. Maybe the budget to pay for AV services was already spent on the fancy video production that reminded us how important we all are?

This year, I organized and chaired a session, which was sponsored by EAS, on social network analysis in evolutionary anthropology. Unfortunately for the EAS party-goers from the previous night, the session ran at 08:00 on Saturday morning. Despite this challenge, the room was packed and the audience generally seemed into it. We had great talks by Stanford’s own Elly Power and Ashley Hazel. Elly talked about her amazing dissertation research on using social capital to understand costly displays of religious devotion in southern India. Ashley talked about her dissertation work in the School of Natural Resources and the Environment on mobility and the changing landscape of STI risk in Kaokoland, northern Namibia. David Nolin, one of our discipline’s most talented young methodologists, presented a very clever test of generalized reciprocity using dichotomous exchange data from his work in Lamalera in Indonesia. Ben Hannowell, yet another talented methodologist to come out of the WSU/UW IGERT program, discussed his collaborative work with Zack Almquist on inferring dominance structure from tournament graphs. The always marvelous Rebecca Sear talked about her recent synthetic work on the effects of kin on fertility (kinship, of course, is the classic application of networks in anthropology since genealogies are just special cases of graphs). John Ziker presented a network-based approach to understanding food sharing and reciprocity from his terrific ethnographic work in Siberia. I closed out the talks with my own combination history of anthropological (and ethological) contributions to social network analysis and pep talk to encourage anthropologists to be confident about their methods and have the courage to innovate new ones the way people like John Barnes or Clyde Mitchell or Elizabeth Bott or Kim Romney or Russ Bernard did!

After schmoozing for a bit post-session, I headed over to the Saturday EAS session on methodological advances in experimental games. While I didn’t see all the talks, the ones I saw were pretty cool. In general, I have mixed feelings about experimental economic games. There are lots of results and some fairly convincing stories to go along with some of the results. However, absent of context, I really wonder what they are measuring and, if they are indeed measuring something, whether it is actually interesting. This session made some real progress in dealing with this question and I think it really highlighted the comparative advantage of anthropologists in the multi-disciplinary landscape of twenty-first century behavioral science. While economists such as Loewenstein (1999) might lament the fact that there is no way to play context-less games and that this jeopardizes the validity and generality of such experimental games, anthropologists are experts in thinking specifically about context and its effect on behavior. Furthermore, anthropologists are still the go-to researchers for providing contextual diversity. In this session, we heard about experimental games played in Bolivia, Siberia, Fiji, and on the streets of Las Vegas. One talk in this session that particularly impressed me was given by Drew Gerkey, who is currently a post-doc at SESYNC in Annapolis, Maryland (and soon to be an assistant professor at Oregon State University — Go Beavs!). I was at SESYNC earlier in the week and got a chance to talk pretty extensively with him about this work. Drew makes the point that seems obvious now that I’ve heard (a sign of an important idea) that, in the evolution of cooperation literature, the counterfactual scenario to cooperation is frequently untenable. One does not simply go it alone when one is a hunter/fisher in Siberia. Drew also designed a number of very clever experimental games that fit the types of social dilemmas faced by his Siberian interlocutors. Very nice work indeed.

In addition to the sessions I attended, it was nice to see and chat with various smart, fun people I know who sometimes find their way to AAAs. I missed my partner in crime from last year’s AAA, Charles Roseman, who left the day I arrived, probably too bloated from the binge on Chicago’s amazing food he no doubt shared with Fernando Armstron-Fumero to be of much use to anyone. However, I got to see Siobhan Mattison, Brooke Scelza, Brian Wood, Rick Bribiescas, Mary Shenk, Aaron Blackwell, Pete Kirby and, briefly, Shauna Burnsilver and Dan Hruschka. Despite my general misgivings about the conference, it is nice to have an excuse to see so many cool people in one place at one time.

Why the Prediction Market Failed to Predict the Supreme Court

There is a very interesting piece in the New York Times today by David Leonhardt on the apparent backlash against prediction markets such as Intrade and Betfair. In principle, these markets make predictions by aggregating the disparate information of many independent bettors who offer prices for a particular outcome. Prediction markets have enjoyed a fair amount of success in recent elections. The University of Iowa has even set up an influenza prediction market.  But prediction markets are hardly perfect and have had some pretty big recent failures. It turns out that Intrade failed in a pretty spectacular manner to predict the outcome of the recent Supreme Court ruling about the constitutionality of the Affordable Care Act. Leonhardt suggests that some of the failures of online prediction markets is attributable to relatively small number of people who actually trade on the market:

But the crowd was not everywhere wise. For one thing, many of the betting pools on Intrade and Betfair attract relatively few traders, in part because using them legally is cumbersome. (No, I do not know from experience.) The thinness of these markets can cause them to adjust too slowly to new information.

This may have been an issue with the ACA decision but the primary problem with the incorrect prediction is that the crowd doesn’t actually know much about the workings of the very closed social network that is the United States Supreme Court. Writes Leonhardt:

And there is this: If the circle of people who possess information is small enough — as with the selection of a vice president or pope or, arguably, a decision by the Supreme Court — the crowds may not have much wisdom to impart. ‘There is a class of markets that I think are basically pointless,’ says Justin Wolfers, an economist whose research on prediction markets, much of it with Eric Zitzewitz of Dartmouth, has made him mostly a fan of them. ‘There is no widely available public information.’

This point gets at a larger critique of market-based solutions to problems suggested by my Stanford colleague Mark Granovetter over 25 years ago (Granovetter 1985). This is the problem of embeddedness. The idea of embeddedness was anticipated by the work of substantivist economist Karl Polanyi, but Granovetter really laid out the details. Granovetter writes (1985: 487): “A fruitful analysis of human action requires us to avoid the atomization implicit in the theoretical extremes of under- and oversocialized conceptions [of human action]. Actors do not behave or decide as atoms outside a social context, nor do they adhere slavishly to a script written for them by the particular intersection of social categories that they happen to occupy. Their attempts at purposive action are instead embedded in concrete, ongoing systems of social relations.” Atomization is independent bettors making decisions about the price they are willing to pay for a certain outcome.

The argument for embeddedness emerges in Granovetter’s paper from the problem of trust in markets. Where does trust come from in competitive markets? The fundamental problem here regards the micro-foudnations of markets where “the alleged discipline of competitive markets cannot be called on to mitigate deceit, so the classical problem of how it can be that daily economic life is not riddled with mistrust and malfeasance has resurfaced.” (p. 488). The obvious solution to this is that actors choose to deal with alters whom they trust and that the most effect way to develop trust is to have prior dealings with an alter.

Granovetter’s embeddedness theory is a modest one. He notes that, unlike the alternative models, his “makes no sweeping (and thus unlikely) predictions of universal order or disorder but rather assumes that the details of social structure will determine which is found.” (p. 493)

These ideas about the careful analysis of social structure and networks of interlocking relationships are fundamental for understanding when the crowd will be wise and when it will not. They are also essential for developing effective development interventions and, for that matter, making markets work for the public good in general.  The theory of embeddedness allows for the possibility that markets can work but if we are to understand when they work and when they don’t, we need to think about social structure as more than just a bit of friction in an ideal market and take its measurement more seriously. People are not ideal gases. (Dirty little secret: most gases are not ideal gases). This gets at some problems that I have been thinking about a lot recently relating to the implications of additive, observational noise vs. process noise and its implications for prediction of multi-species epidemics, but that must wait for another post…

 

 

New Grant, Post-Doc Opportunity

Biological and Human Dimensions of Primate Retroviral Transmission
One of the great enduring mysteries in disease ecology is the timing of the AIDS pandemic. AIDS emerged as a clinical entity in the late 1970s, but HIV-1, the retrovirus that causes pandemic AIDS, entered the human population from wild primates many decades earlier, probably near the turn of the 20th century. Where was HIV during this long interval? We propose a novel ecological model for the delayed emergence of AIDS. Conceptually, in a metapopulation consisting of multiple, loosely interconnected sub-populations, a pathogen could persist at low levels indefinitely through a dynamic balance between localized transmission, localized extinction, and long-distance migration between sub-populations. This situation might accurately describe a network of villages in which population sizes are small and rates of migration are low, as would have been the case in Sub-Saharan Africa over a century ago.
We will test our model in a highly relevant non-human primate system. In 2009, we documented three simian retroviruses co-circulating in a metapopulation of wild red colobus monkeys (Procolobus rufomitratus) in Kibale National Park, Uganda, where we have conducted research for over two decades. We will collect detailed data on social interactions, demography, health, and infection from animals in a core social group.
We will also study a series of 20 red colobus sub-populations, each inhabiting a separate, isolated forest fragment. We will determine the historical connectivity of these sub-populations using a time series of remotely sensed images of forest cover going back to 1955, as well as using population genetic analyses of hypervariable nuclear DNA markers. We will assess the infection status of each animal over time and use viral molecular data to reconstruct transmission pathways.
Our transmission models will define the necessary conditions for a retrovirus to persist, but they will not be sufficient to explain why a retrovirus might emerge. This is because human social factors ultimately create the conditions that allow zoonotic diseases to be transmitted from animal reservoirs and to spread. We will therefore conduct an integrated analysis of the root eco-social drivers of human-primate contact and zoonotic transmission in this system. We will study social networks to understand how social resources structure key activities relevant to human-primate contact and zoonotic transmission risk, and we will explore knowledge, beliefs, and perceptions of human-primate contact and disease transmission for a broad sample of the population. We will reconcile perceived risk with actual risk through a linked human health survey and diagnostic testing for zoonotic primate retroviruses.
The ultimate product of our research will a data-driven set of transmission models to explain the long-term persistence of retroviruses within a metapopulation of hosts, as well as a linked analysis of how human social factors contribute to zoonotic infection risk in a relevant Sub-Saharan African population. Our study will elucidate not only the origins of HIV/AIDS, but also how early-stage zoonoses in general progress from “smoldering” subclinical infections to full-fledged pandemics.

I am thrilled to report that our latest EID project proposal, Biological and Human Dimensions of Primate Retroviral Transmission, has now been funded (by NIAID nonetheless!).  I will briefly describe the project here and then shamelessly tack on the full text of our advertisement for a post-doc to work as the project manager with Tony Goldberg, PI for this grant, in the College of Veterinary Medicine, University of Wisconsin, Madison.  This project will complement the ongoing work of the Kibale EcoHealth Project. The research team includes: Tony, Colin Chapman (McGill), Bill Switzer (CDC), Nelson Ting (Iowa), Mhairi Gibson (Bristol), Simon Frost (Cambridge), Jennifer Mason (Manchester), and me. This is a pretty great line-up of interdisciplinary scholars and I am honored to be included in the list.

Biological and Human Dimensions of Primate Retroviral Transmission

One of the great enduring mysteries in disease ecology is the timing of the AIDS pandemic. AIDS emerged as a clinical entity in the late 1970s, but HIV-1, the retrovirus that causes pandemic AIDS, entered the human population from wild primates many decades earlier, probably near the turn of the 20th century. Where was HIV during this long interval? We propose a novel ecological model for the delayed emergence of AIDS. Conceptually, in a metapopulation consisting of multiple, loosely interconnected sub-populations, a pathogen could persist at low levels indefinitely through a dynamic balance between localized transmission, localized extinction, and long-distance migration between sub-populations. This situation might accurately describe a network of villages in which population sizes are small and rates of migration are low, as would have been the case in Sub-Saharan Africa over a century ago.

We will test our model in a highly relevant non-human primate system. In 2009, we documented three simian retroviruses co-circulating in a metapopulation of wild red colobus monkeys (Procolobus rufomitratus) in Kibale National Park, Uganda, where we have conducted research for over two decades. We will collect detailed data on social interactions, demography, health, and infection from animals in a core social group.

We will also study a series of 20 red colobus sub-populations, each inhabiting a separate, isolated forest fragment. We will determine the historical connectivity of these sub-populations using a time series of remotely sensed images of forest cover going back to 1955, as well as using population genetic analyses of hypervariable nuclear DNA markers. We will assess the infection status of each animal over time and use viral molecular data to reconstruct transmission pathways.

Our transmission models will define the necessary conditions for a retrovirus to persist, but they will not be sufficient to explain why a retrovirus might emerge. This is because human social factors ultimately create the conditions that allow zoonotic diseases to be transmitted from animal reservoirs and to spread. We will therefore conduct an integrated analysis of the root eco-social drivers of human-primate contact and zoonotic transmission in this system. We will study social networks to understand how social resources structure key activities relevant to human-primate contact and zoonotic transmission risk, and we will explore knowledge, beliefs, and perceptions of human-primate contact and disease transmission for a broad sample of the population. We will reconcile perceived risk with actual risk through a linked human health survey and diagnostic testing for zoonotic primate retroviruses.

The ultimate product of our research will a data-driven set of transmission models to explain the long-term persistence of retroviruses within a metapopulation of hosts, as well as a linked analysis of how human social factors contribute to zoonotic infection risk in a relevant Sub-Saharan African population. Our study will elucidate not only the origins of HIV/AIDS, but also how early-stage zoonoses in general progress from “smoldering” subclinical infections to full-fledged pandemics.

Post Doctoral Opportunity

The Goldberg Lab at the University of Wisconsin-Madison invites applications for a post-doctoral researcher to study human social drivers of zoonotic disease in Sub-Saharan Africa.   The post-doc will be an integral member of a new, international, NIH-funded project focused on the biological and human dimensions of primate infectious disease transmission in Uganda, including social drivers of human-primate contact and zoonotic transmission.  This is a unique opportunity for a post-doctoral scholar with training in the social sciences to study human-wildlife conflict/contact and health and disease in a highly relevant ecological setting.  The following criteria apply.

  1. Candidates must have completed or be near to completing a PhD in the social sciences, in a discipline such as anthropology, geography, sociology, behavioral epidemiology, or a relevant discipline within the public health fields.
  2. Candidates must have a demonstrated interest in health and infectious disease.
  3. Candidates must have prior field experience in Sub-Saharan Africa.
  4. Candidates must be willing to relocate to Madison, Wisconsin for three years.
  5. Candidates must be willing to spend substantial time abroad, including in Sub-Saharan Africa and at partner institutions in the United Kingdom.
  6. Candidates must have experience with collection and analysis of both quantitative and qualitative data.  Familiarity with methods such as social network analysis, GIS, participatory methods, and survey design would be advantageous.

The successful candidate will help lead a dynamic international team of students and other post-docs in a multi-institutional, multidisciplinary project.  Duties involve a flexible combination of fieldwork, analyses, and project coordination, in addition to helping to mentor students from North America, Europe, and Africa.  The successful applicant will be expected to explore new research directions of her/his choosing, assisted by a strong team of collaborators.

University of Wisconsin-Madison is a top-notch institution for research and training in the social and health sciences.  Madison, WI, is a vibrant city with outstanding culture and exceptional opportunities for outdoor recreation.

Applicants should send a current CV, a statement of research interests and qualifications (be sure to address the six criteria above), and a list of three people (names, addresses, e-mails) who can serve as references.

Materials and inquiries should be sent to Dr. Tony L. Goldberg (tgoldberg@vetmed.wisc.edu).  Application materials must be received by September 12, 2011 for full consideration; the position is available starting immediately and requires a three-year commitment.

My Erdős Number

Paul Erdős was the great peripatetic, and highly prolific, mathematician of the 20th century. A terrific web page run by Jerry Grossman at Oakland University provides details of the Erdős Project. Erdős was a pioneer in graph theory, which provides the formal tools for the analysis of social networks.  A collaboration graph is a special graph in which the nodes are authors and an edge connects authors if they co-author a publication. Erdős was such a prolific collaborator that he forms a major hub in the mathematics collaboration graph, linking many disparate authors in the different realms of pure and applied mathematics.

For whatever reason, today I used Grossman’s directions for finding one’s number. <drum roll> My Erdős number is 4.  The path that leads me to Erdős is pretty sweet, I have to say.  This past year, I published a paper in PNAS with Marc Feldman.  Marc wrote a number of papers (here’s one) with Sam Karlin (who, I’m proud to say, came and slept through at least one talk I gave at the Morrison Institute). Karlin wrote a paper with Gábor Szegő, who wrote a paper with Erdős.  Lots of Stanford greatness there that I feel privileged to be a part of. It turns out that I have independent (though longer) paths through my co-authors Marcel Salathé and Mark Handcock as well.

Nearly Neutral Networks and Holey Adaptive Landscapes

My holiday reading on modularity has led me into some of the literature on the evolution of complexity.  Some of the most interesting work in theoretical biology that I’ve read in a while relates to the ideas of nearly neutral networks and holey adaptive landscapes, an area developed by Sergey Gavrilets at the University of Tennessee.  The various papers of his to which I refer can be accessed on his website.  I find his explanations very clear, but recognize that this work is fairly technical stuff and my understanding of it is greatly facilitated by previous experience with similar models in the context of epidemics on networks (believe it or not). Nonetheless, a reasonably accessible introduction can be found in his 2003 chapter, “Evolution and speciation in a hyperspace: the roles of neutrality, selection, mutation and random drift.” I have based much of my discussion here on this paper along with his 1997 paper in JTB.

The father of American population genetics and Modern Evolutionary Synthesis pioneer Sewall Wright first came up with the metaphor of the adaptive landscape in 1932.  The basic idea is a kind of topographic map where the map coordinates are given by the genotype and the heights above these coordinates are given by the fitnesses associated with particular genotype combinations.  A landscape, of course, is a three dimensional object.  It has a length, a width (or latitude and longitude) and height.  This particular dimensionality turns out to be very important for this story.

A major concern that arises from the idea of an adaptive landscape is how populations get from one peak to another.  In order to do this, they need to pass through a valley of low fitness and this runs rather counter to our intuitions of the way natural selection works.  The usual way around this apparent paradox is to postulate that populations are small and that random genetic drift (which will be more severely felt in small populations) moves the population away from its optimal point on the landscape.  Once perturbed down into a valley by random forces, there is the possibility that the population can climb some other adaptive peak.

This is a slightly unsatisfying explanation though.  Say that we have a finite population of a diploid organism characterized by a single diallelic locus. Finite populations are subject to random drift. The size of the population is N.  Assume that the fitnesses are w_{AA}=1, w_{Aa}=1-s, and w_{aa}=1. This is actually a very simple one-dimensional adaptive landscape with peaks at the ends of the segment and a valley in between.  Assume that the resident population is all AA.  What happens to a mutant a allele? We know from population genetics theory that the probability that a completely neutral (i.e., s=0) mutant allele reaching fixation is 1/2N.  Russ Lande has shown that when the s>0 this probability becomes:

 U = \frac{1}{2N} \frac{e^{-Ns}\sqrt{4Ns/\pi}}{erf(\sqrt{Ns})},

where erf() is the error function  erf(t) = 2/\sqrt{\pi} \int_0^t e^{-y^2} dy.

When Ns=20 (say a population size of 200 and a fitness penalty of s=0.1), this probability is approximately U=10^{-8}.  So for quite modest population size and fitness disadvantage for the heterozygote, the probability that the population will drift from AA to aa is very small.  This would seem to spell trouble for the adaptive landscape model.

Gavrilets solved this conundrum — that moving between peaks on the adaptive landscape appears to require the repeated traversing of very low-probability events — apparently by thinking a little harder about the Wrightean metaphor than the rest of us.  Our brains can visualize things very well in three dimensions.  Above that, we lose that ability.  Despite all the Punnett squares we may have done in high school biology, real genotypes, of course, are not 2 or 3 dimensional.  Instead, even the simplest organism has a genotype space defined by thousands of dimensions.  What does a thousand dimensional landscape look like? I haven’t the faintest idea and I seriously doubt anyone else does either.  Really, all our intuitions about the geometry of such spaces very rapidly disappear when we go beyond three dimensions. 

Using percolation theory from condensed matter physics, Gavrilets reveals a highly counter-intuitive feature of such spaces’ topology. In particular, there are paths through this space that are very nearly neutral with respect to fitness.  This path is what is termed a “nearly neutral network.” This means that a population can drift around genotype space moving closer to particular configurations (of different fitness) while nonetheless maintaining the same fitness.  It seems that the apparent problem of getting from one fitness peak to another in the adaptive landscape is actually an artifact of using low-dimensional models. In high-dimensional space, it turns out there are short-cuts between fitness peaks.  Fitness wormholes?  Maybe.

Gavrilets and Gravner (1997) provide an example of a nearly neutral network with a very simple example motivated by Dobzhansky (1937).  This model makes it easier to imagine what they mean by nearly neutral networks in more realistic genotype spaces.

Assume that fitness takes on one of two binary values: viable and non-viable. This assumption turns our space into a particularly easy type of structure with which to work (and it turns out, it is easy to relax this assumption).  Say that we have a three diallelic loci (A, B, and C).  Say also that we have reproductively isolated “species” whenever there is a difference of two homozygous loci — i.e., in order to be a species a genotype must differ from the others by at least homozygous loci.  The reproductive isolation that defines these species is enforced by the fact that individuals heterozygous at more than one locus are non-viable. While it may be a little hard to think of this as a “landscape”, it is.  The species nodes on the cube are the peaks of the landscape.  The valleys that separate them are the non-viable nodes on the cube face.  Our model for this is a cube depicted in this figure.

Now using only the visible faces of our projected cube, I highlight the different species in blue.

The cool thing about this landscape is that there are actually ridges that connect our peaks and it is along these ridges that evolution can proceed without us needing to postulate special conditions like small population size, etc. The paths between species are represented by the purple nodes of the cube.  All the nodes that remain black are non-viable so that an evolutionary sequence leading from one species to another can not pass through them.  We can see that there is a modest path that leads from one species to another — i.e., from peak to peak of the fitness landscape. Note that we can not traverse the faces (representing heterozygotes for two loci) but have to stick to edges of the cube — the ridges of our fitness landscape.  There are 27 nodes on our cube and it turns out that 11 of them are viable (though the figure only shows the ones visible in our 2d projection of the cube).

So much for a three-dimensional genotype space. This is where the percolation theory comes in. Gavrilets and Gravner (1997) show that as we increase the dimensionality, the probability that we get a large path connecting different genotypes with identical fitness increases.  Say that the assignment of fitness associated with a genotype is random with probability p that the genotype is viable and 1-p that it is non-viable.  When p is small, it means that the environment is particularly harsh and that very few genotype combinations are going to be viable. In general, we expect p to be small since most random genotype combinations will be non-viable. Percolation theory shows that there are essentially two regimes in our space.  When p<p_c, where p_c is a critical threshold probability, the system is subcritical and we will have many small paths in the space.  When  p>p_c, we achieve criticality and a giant component forms, making a large viable evolutionary path  traversing many different genotypes in the space.  These super-critical landscapes are what Gavrilets calls “holey”. Returning to our three dimensional cube, imagine that it is a chunk of Swiss cheese.  If we were to slice a face off, there would be connected parts (i.e., the cheese) and holes.  If we were, say, ants trying to get across this slice of cheese, we would stick to the contiguous cheese and avoid the holes. As we increase the dimensionality of our cheese, the holes take up less and less of our slices (this might be pushing the metaphor too far, but hopefully it makes some sense).

A holey adaptive landscape holds a great deal of potential for evolutionary change via the fixation of single mutations.  From any given point in the genotype space, there are many possibilities for evolutionary change.  In contrast, when the system is sub-critical, there are typically only a couple of possible changes from any particular point in genotype space.

To get a sense for sub-critical and supercritical networks, I have simulated some random graphs (in the graph theoretic sense) using Carter Butts‘s sna package for R.  These are simple 1000-node Bernoulli graphs (i.e., there is a constant probability that two nodes in the graph will share an undirected edge connecting them).  In the first one, the probability that two nodes share an edge is below the critical threshold p_c.

 

We see that there are a variety of short paths throughout the graph space but that starting from any random point in the space, there are not a lot of viable options along which evolution can proceed. In contrast to the sub-critical case, the next figure shows a similar 1000-node Bernoulli graph with the tie probability above the critical threshold — the so-called “percolation threshold.”

Here we see the coalescence of a giant component.  For this particular simulated network, the giant component contains 59.4% of the graph.  In contrast, the largest connected component in the sub-critical graph contained 1% of the nodes.  The biological interpretation of this graph is that there are many viable pathways along which evolution can proceed from many different parts of the genotype space. Large portions of the space can be traversed without having to pass through valleys in the fitness landscape.

This work all relates to the concept of evolvability, discussed in the excellent (2008) essay by Massimo Pigliucci.  Holey adaptive landscapes make evolvability possible.  The ability to move genotypes around large stretches of the possible genotype space without having to repeatedly pull off highly improbable events means that adaptive evolution is not only possible, it is likely.  In an interesting twist, this new understanding of the evolutionary process provided by Gavrilets’s work increases the role of random genetic drift in adaptive evolution.  Drift pushes populations around along the neutral networks, placing them closer to alternative adaptive peaks that might be attainable with a shift in selection.

Super cool stuff.  Will it actually aid my research?  That’s another question altogether…

Another fun thing about this work is that this is essentially the same formalism that Mark Handcock and I used in our paper on epidemic thresholds in two-sex network models. I never cease being amazed at the utility of graph theory.

References

Dobzhansky, T. 1937. Genetics and the Origin of Species. New York: Columbia University Press.

Gavrilets, S. 2003. Evolution and speciation in a hyperspace: the roles of neutrality, selection, mutation and random drift. In Crutchfield, J. and P. Schuster (eds.) Towards a Comprehensive Dynamics of Evolution – Exploring the Interplay of Selection, Neutrality, Accident, and Function. Oxford University Press. pp.135-162.

Gavrilets, S., and J.Gravner. 1979. Percolation on the fitness hypercube and the evolution of reproductive isolation. Journal of Theoretical Biology 184: 51-64.

Lande, R.A. 1979. Effective Deme Sizes During Long-Term Evolution Estimated from Rates of Chromosomal Rearrangement. Evolution 33 (1):234-251.

Pigliucci, M. 2008. Is Evolvability Evolvable? Nature Genetics 9:75-82.

Wright, S. 1932. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the 6th International Congress of Genetics. 1: 356–366.

 

Plotting Networks in R

Using the network package, you can plot graphs in a flexible and powerful way.  Often, when plotting a network, we want to vary the color, size, or shape of the vertices based on some attributes.  Let's say that we have a freewheeling sexual network (easier to simulate) and we would like to color the vertices of the graph according to their HIV sero-status.  Let's also say that we want to make the shape of each vertex reflect the sex of the individual.  We use the following code:

R:
  1. # begin with randomly constructed edgelist
  2. set.seed(12345)
  3.  
  4. n1 <- round(1+10*runif(50))
  5. n2 <- round(1+10*runif(50))
  6. eee <- cbind(n1,n2)[order(n1),]
  7. net <- network(eee,directed=FALSE) # this will be a dense network!
  8. hiv <- rbinom(50,size=1,prob=0.2)  # random infections!
  9. sex <- rbinom(50,size=1,prob=0.5)  # random sexes!
  10. set.vertex.attribute(net,"hiv",hiv+1)
  11. set.vertex.attribute(net,"sex",sex+3)
  12.  
  13. ## now plot
  14. plot(net,
  15. vertex.col="hiv",
  16. vertex.sides="sex",
  17. vertex.cex=5,
  18. vertex.rot=-30,
  19. edge.lwd=1)

I definitely wouldn't want to be part of that party.

Extracting adjacency matrices with valued edges

This may seem obvious to an expert statnet user, but it took me a bit of careful reading of Carter's paper and some trial and error to figure it out. We are using the frequency of behaviors based on ethological observations as edge weights and would like to be able to extract a matrix of the edge weights.

R:
  1. set.seed(123)
  2. ## generate a network with 21 nodes and 50 edges.
  3. ## some edges are either self-loops or redundant
  4. ## just a quick and dirty way to get an example network object
  5.  
  6. n1 <- round(1+20*runif(50))
  7. n2 <- round(1+20*runif(50))
  8. n3 <- rpois(50,3)
  9. eee <- cbind(n1,n2)[order(n1),]
  10. net <- network(eee,directed=FALSE)
  11. set.edge.attribute(net,"meaningful.measure",n3)
  12. as.matrix(net,attrname="meaningful.measure")

This last command returns a 50x50 matrix of the edge weights.

Extracting an edge list from a network object

I've been using the statnet suite of tools a lot recently.  As with any powerful software, there is quite a learning curve.  I will write some notes in my blog to help me remember tricks that I learn along the way.  And who knows? They might even be useful to other people!

For a variety of reasons, we have found it easy to import our networks as adjacency matrices.  The problem is that when there are attributes associated with the edges, it is much easier to deal with an edge list.  While using summary(net) yields an edge list as part of the summary, it was not clear to me how to get such a list as a manipulable object.  I wrote the statnet_help list and Carter Butts (co-author of network) pointed out to me that getting an edgelist is quite simple. Having read in our adjacency matrix

R:
  1. mat <-read.table("mat5.txt",header=TRUE)
  2. mat <- as.matrix(mat)
  3. net <- network(mat, directed=FALSE)

We can get the edge list like this:

R:
  1. bbb <- as.matrix(net,matrix.type="edgelist") 

Easy...