On the Value of Complexity

Science — Zac Townsend @ November 4, 2012 9:23 am

Cesar Hildago again:

One example that I like very much to try to make a distinction between those approaches and other approaches is that of an F-22 jet fighter. This is an example from my friend Francisco Claro. The idea is that an F-22 fighter is actually quite an expensive machine. You need to have a lot of money to buy an F-22. An F-22, being a very expensive machine, is also a very complex machine. It has a lot of parts, and there were a lot of people with a lot of different types of expertise that went in to generate that machine.

If you take the price of an F-22 and you divide it by its weight, you get that, per pound, cost something between silver and gold. It's that expensive! . Now, take your F-22 and crash it against a hill, or crash it against the ocean, blow it up into tiny little bits and pieces. How valuable it is now? It's probably way less valuable than silver. It's probably almost worthless after it's broken down. So, where was the value?

The value cannot be in any of the parts or in any of the materials, or in anything other than the complexity of how these things come together. So actually, value is set by the property of organization. It's more of an entropic, or anti-entropic more precisely, idea of value.

What Doctors Don't Know About the Drugs They Prescribe

Science,Social Science — Zac Townsend @ November 3, 2012 9:20 am

When a new drug gets tested, the results of the trials should be published for the rest of the medical world -- except much of the time, negative or inconclusive findings go unreported, leaving doctors and researchers in the dark. In this impassioned talk, Ben Goldacre explains why these unreported instances of negative data are especially misleading and dangerous.

It might seem less disturbing, but the same could be said about our knowledge about education, social science, housing, etc...

Emergence of Scaling in Random Networks

Networks,Reading,Science — Zac Townsend @ October 31, 2012 10:12 am

This article by Barabasi and Albert provide an explanation for why the distribution of links over nodes in many real-world networks follow a power-law distribution. Power-law distributions are defined by a concentration of the density in a small number of units and then a long-tail.

The distribution function of connectivities for various large networks. (A) Actor collaboration graph with N=212,250 vertices (B) WWW, N=325,729 (C) Power grid data, N =4941, . The dashed lines have slopes (A)=2.3, (B)=2.1 and (C)=4

After going through some example of networks with complex topologies--everything from neurons to the World Wide Web--they note that networks have traditionally been described by the random network model of Erdos and Renyi (the "ER" model). But, the ER model (and the WS model) is not up to the task of explaining the scale-free power law distributions that they find by "exploring several large databases describing the topology of large networks that span fields as diverse as the WWW or citation patterns in science."

More precisely, the authors find that independent of the system by which the networks are created, that the probability P(k) that a node has k links follos P(k) \sim k^{- \gamma}. They explain these distributions by developing a model that includes growth and preferential attachment--in short, 1) that networks start small and grow larger and 2) that no matter if a) because early nodes (those that exist when the network is young) have more random chances to be linked to new nodes or because b) there is "preferential attachment" made to those nodes that are already popular, that there will be some winners with many more links than most other nodes.

Why do the ER and WS models not accurately explain the power-law phenomena? Both models start with a fixed number of nodes and then randomly connect them (ER) or reconnected (WS), whereas this model takes explicit account of the growing number of nodes that occurs in most real world networks. Additionally, the two random network models assume that the probability that any two nodes are connected is random and uniform, whereas this model includes preferential connectivity:

For example, a new actor is most likely to be cast in a supporting role with more established and better-known actors. Consequently, the probability that a new actor will be cast with an established one is much higher than that the new actor will be cast with other less-known actors.

So, how does their model work? It begins with some small number of nodes and then keeps adding new nodes with the probability that the new nodes will be connected to all the previous nodes weighted by the previous nodes popularity. In their language,

  1. To incorporate the growing character of the network, starting with a small number (m_0) of nodes,
    at every time step they add a new node with m(m_0) links, so the new node connects to $m$ different vertices already present in the system.
  2. To incorporate preferential attachment, they assume that the probability \Pi that a new node will be connected to node i depends on the connectivity k_i of that node, so that \Pi (k_i)=\frac{k_i}{\sum_jk_j}.

They continue by developing slight variants of this model--one that assumes growth but not preferential treatment and one that assumes preferential treatment but not growth--and show that neither is sufficient to explain the emergent scale-free power law distributions seen in real-world networks.

Because of preferential treatment, early gains are quite important and older nodes increase their connectivity at the expense of the younger ones. This leads to some nodes "that are highly connected, a “rich-get-richer” phenomenon that can be easily detected in real networks."

Identity and Search in Social Networks

Networks,Reading,Science — Zac Townsend @ October 30, 2012 10:48 am

This articles develops a model for explaining how "ordinary" individuals can search through their social networks and send messages to distant people they do not know.

Travers and Milgram (Sociometry, 1969) ran a experiment where they asked people in Omaha, NE to try to get a letter to randomly selected people in Boston. The Nebraskans were to do this by mailing the letter to an acquaintance they thought would be closer to the target. "The average length of the resulting acquaintance chains for the let ters that eventually reached the target (roughly 20%) was about six." These results suggest that short paths exist between many people and that ordinary people can find those paths. This is pretty cool because although most people know there friends, they don't know there friend's friends (imagine a pre-facebook world). The authors of the article I am reading today call the ability to find targets "searchability." They question the accuracy of previous studies who tried to model social network using 1) hubs or highly connected people that you need only reach and then you will reach the target or 2) geometric lattices (which often have some assumption that every node has the same number of edges, see regular networks from yesterday's post) because neither of these network types, however, is a satisfactory model of society. (As an aside, models should not be judged on whether or not their assumptions comport with reality but on whether they make useful and accurate predictions, see Gary King or Milton Friedman on this point).

The authors build a model from "six contentions about social networks":

  1. People have identities and social groups are collections of identities.
  2. People break their society up in to hierarchies. They use an example of a specialized subgroup with an academic department that in turn is within a university. Formerly they put an upper bound on group size near one hundred, formally g \approx 100. They define the similarity between two individuals i and j as x_{ij}, where x_{ij}=1 if they are in the same group (=2 if they are in the same department in the example above).
  3. Group membership is the the primary basis for social interaction and thus you're more likely to know someone the closer you are to being in the same group. The chance that two people are acquaintances decreases when the groups they belong to are more dissimilar. To build their social network, they keep making connections between people until the average numbers of friends equals z. They make these links by randomly choosing an individual, then choosing a link distance, x, to add to that person with p(x)=c\cdot e^{\alpha x}, and then by choosing a random person in that other level that is x levels away and making the link. \alpha is a "tunable" parameter and is a measure of homophily--the tendency of similar people to group together--in the created social network.
  4. People can belong to different hierarchical groups (I am a member of the City of Newark workforce, the Brown alumni, the Manhattan democrats, Brooklyn) and it is assumed these groups are independent. This is a standard assumption but you can see in my group membership alone that Brown and Brooklyn likely aren't wholly statistically independent. In this way a person's identity is defined by the position people have in various hierarchies defined in the model, represented by the H-dimensional vector \vec{v}_i, where where v_i^h is the position of node i in the h^{th} hierarchy, or dimension. Each node is randomly assigned a location in the various hierarchies and then the links are made as is indicated in point three above (I think it would have made more sense to explain this point than that one).
  5. People construct a social distance to perceive the similarity between themselves and others. This is here defined as the minimum distance that exist between nodes across all hierarchies, or y_{ij}=min_h x^h_{ij}. It is interesting to note that "social distance violates the triangle inequality ... because individuals i and j can be close in dimension $h_1$, and individuals j and k can be close in dimension $h_2$, yet i and k can be far apart in both dimensions. A simple example might be to use my dad as individual j, me as individual i, and one of my dad's work colleagues at Mt. Sinai as k. Although my dad and I are in the same family and he and his co-worker have the same occupation (x_{ij}=x_{jk}=1) the co-worker and I are quite socially distant.
  6. Individuals are only aware of their immediate network across all hierarchies, so that if a person forwards a message to a single neighbor that person does not know how much closer, if at all, the neighbor is to the intended recipient.

With this model, "[i]ndividuals therefore have two kinds of partial information: social distance, which can be measured globally but which is not a true distance (and hence can yield misleading estimates); and network paths, which generate true distances but which are known only locally."

With this model setup, they show that a greedy algorithm (the same as the one Milgram suggests) can efficiently direct a message to a receipt in a short number of steps.

They do some analysis that is worth noting. First, they point out (apparently against the previous literature) that the average length of a message chain, defined as the metric <L> has to be short in an absolute sense. The message chain length cannot scale with population n because of at each point there is a failure/termination rate of 25% (i.e. one and four people get the letter and do not forward it at all). Secondly, through some simple math they show that with a termination rate of 25% and a success rate fixed at above 5% that the average message length chain, <L> must be less than 10.4 independent of population size. With this, they can create diagrams of the parameter space in H and \alpha that meets that requirement. That is, they can create a graph of all the possible hierarchy number and homophily parameters that meet that requirement in <L>, thus:

Our main result is that searchable networks occupy a broad region of parameter space (\alpha ,H) which [...] corresponds to choices of the model parameters that are the most sociologically plausible. Hence our model suggests that searchability is a generic property of real-world social networks.

Proust Wasn’t a Neuroscientist. Neither was Jonah Lehrer.

Ideas,Science — Zac Townsend @ October 29, 2012 2:29 pm

I am not interested in the particulars of Jonah Lehrer's story; however, I am very interested in the inability of scientists to convey science to the public and for journalists to understand science (The main thesis of this article in New York Magazine). Is it that science is just too messy and complicated? What role, if any, could journalist play in presenting and drawing social implications out of science? Malcolm Gladwell writes well, and for that I respect him, but he has essentially simplified complex scientific discussion in to one-sided, absurdly broad, phenomena. Should he stop or does his popularization of science, even if wrong, help the cause?

Collective Dynamics of ‘Small-world’ Networks

Networks,Reading,Science — Zac Townsend @ October 29, 2012 11:50 am

This article explores the dynamics of a network that is somewhere between regular and random.Regular networks are those where every node has the same number of connections. On the other hand, random networks are those that are built by introducing new nodes and randomly assigning edges between the new nodes and the old nodes with some probability, p (see the Erdos-Renyi model).

This paper "interpolates" between these two models by starting with a regular network (a ring lattice to be precise) and then rewiring each edge at random with probability p; in this way the graph is "tuned" between regular (p=0) and complete disorder / randomness (p=1).

To continue, we have to understand two measures that are often used in network theory: L(p) and C(p). L(p) is the average shortest length between all pairs of nodes. That is, if you find the shortest path between all pairs of nodes and then you take the average of those shortest paths you get L(p). C(p) is the clustering coefficient and is a measure of how many links exist between nodes divided by the number of possible such links.

For friendship networks, these statistics have intuitive meanings: L is the average number of friendships in the shortest chain connecting two people; C_v reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness of a typical friendship circle.

The p=0 case is a "highly clustered, large world where L grows linearly with n" while the p=1 case is a "poorly clustered, small world where L grows only logarithmically with n". The key insight here is that allow it appears form these end points that large C and large L (and small C and small C) would always be associated from this simple analysis, it turns out that there is a "broad interval" where things stay clustered but the average length between nodes (L(P)) drops quickly. It's a "small world" because as you move, even just a little but, from a regular network to a random one there are introduced "short cuts" between groups that decreases the length: "The important implication here is that at the local level (as reflected by C(p)), the transition to a small world is almost undetectable."

The rest of the paper (Nature articles are quite short) shows three empirical examples fit this "small world" network model--IMDB film actors, the power gift, and the neural network of a nematode worm. The paper then finishes testing the implication of the network on a simulated disease outbreak where they show that 1) the smaller the L(p) of a network the faster the infection effects the entire population, 2) That a network just needs to be a little not regular for L(p) to drop significantly and 3) If it's a small world disease spread much more quickly than previous models suggest.

We hope that our work will stimulate further studies of smallworld networks. Their distinctive combination of high clustering with short characteristic path length cannot be captured by traditional approximations such as those based on regular lattices or random graphs. Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and man-made systems, often with important dynamical consequences.

Gauging Impact of Gates Foundation Grants After Five Years

Science — Zac Townsend @ December 21, 2010 8:22 am

Five years ago, the Gates Foundation put $450 million in to 43 grants designed to address the world's largest public health problems. Bill Gates notes in this article, "We were naïve when we began." In 2007, instead of making more multimillion-dollar grants, he started making hundreds of $100,000 ones:

That little won’t buy a breakthrough, but it lets scientists “moonlight” by adding new goals to their existing grants, which saves the foundation a lot of winnowing. “And,” he added, “a scientist in a developing country can do a lot with $100,000.”

The article is mostly about what went "wrong" in many of the grants--including those on dried vaccines, a lab in the box, a better banana, etc--and you should read it for a fun slice of the ups and downs of science.

New Advice On How to Survive Nuclear Attack

Politics,Science — Zac Townsend @ December 16, 2010 8:58 am

New "scientific analysis" shows that if a nuclear attack happens near you, that you shouldn't flee. Your chances of survival go up a great deal if you stay inside some structure (even a car, but preferably something like a basement): "a nuclear attack is much more survivable if you immediately shield yourself from the lethal radiation that follows a blast, a simple tactic seen as saving hundreds of thousands of lives." The Times' reporting on the results continue:

The results were revealing. For instance, the scientists found that a bomb’s flash would blind many drivers, causing accidents and complicating evacuation.

The big surprise was how taking shelter for as little as several hours made a huge difference in survival rates.

“This has been a game changer,” Brooke Buddemeier, a Livermore health physicist, told a Los Angeles conference. He showed a slide labeled “How Many Lives Can Sheltering Save?”

If people in Los Angeles a mile or more from ground zero of an attack took no shelter, Mr. Buddemeier said, there would be 285,000 casualties from fallout in that region.

Taking shelter in a place with minimal protection, like a car, would cut that figure to 125,000 deaths or injuries, he said. A shallow basement would further reduce it to 45,000 casualties. And the core of a big office building or an underground garage would provide the best shelter of all.