Emergence Course 2006 Forum on Serendip

1) Small World Phenomenon
a) 1967 experiment by psychologist Stanley Milgram
i) Small world phenomenon: strangers discover they have a mutual acquaintance
ii) Theory: in the network of social acquaintances, any particular person can be reached through a short number of steps from friend to friend
iii) Test: one letter to each of 100 random people with the goal of eventually reaching a target person.? Letters could be passed along only to someone known on a first name basis.
iv) Result: average of 6 steps - 6 degrees of separation
v) Not so surprising?? Consider a Branching Network - a person has 100 friends, each of whom has 100 friends, each of whom has 100 friends, etc;
(1) 1 degree of separation = 100 people
(2) 2 degrees = 10,000 people
(3) 3 degrees = 1,000,000 people
(4) Exponential growth of nodes
vi) Real world: many friends share friends - clustering - redundancy in the network
vii) Paradox: while the real world social network is highly clustered, it is still possible to travel the network in relatively few steps

2) Random Graphs
a) Formal theory of random graphs: 1959 mathematicians Paul Erdõs & Alfred Renyi
b) Random Graphs: a network of nodes randomly connected by links
c) Connectivity of Random Graphs
i) Imagine a bunch of buttons tossed on the floor, and imagine that you tie a random number of threads to different pairs of buttons. - When you pick up one button, the buttons that lift off the floor with it are its connected component.
ii) Tie only one thread in a set of buttons: largest connected component is 2 - as a fraction of a large network that's equivalent to zero
iii) Connecting every button to every other button would produce a complete graph (completely inter-connected network)
iv) While the average links per node is less than 1, network connectivity is statistically zero because randomly added links are most likely to connect isolated links
v) Phase transition at 1: As the average links per node exceeds one, the fraction of nodes in the network that are all connected - that are in the largest connected component - increases rapidly
(1) the critical point is 1: the threshold between relative isolation and a connected network
(2) Phase transitions occur in many complex systems: magnetism, outbreaks of disease, spreading of cultural fads, stock market trends
vi) Importance
(1) An isolated network means local events stay local, but in an interconnected network, local events may affect the entire network
(2) Global connectivity isn?t incremental ? it occurs rapidly

3) Random-Biased Networks
a) 1950?s mathematician Anatol Rapoport considered social networks as he studied the spread of disease through human populations
b) homophily - the tendency of people to congregate with similar people
c) A person is more likely to befriend a friend of a friend than a complete stranger
d) Triadic closure - linking nodes in a social network are more likely to create triads
i) Example: if A is linked to B and B is linked to C, when C gains a new link, it has a higher probability to link to A than to another node in the network
e) Unlike random networks, social networks will over time develop triads (a bias away from a random network)
f) Random-biased networks
i) utilize the power of random network theory, while accounting for some of the non-random ordering principals by which people tend to create links
ii) consider the ways in which the network evolves: a network's eventual configuration depends on its current configuration - the probability of certain configuration is based on the prior configuration

4) Universality Classes
a) Example: Magnetism
i) The direction of spin of an electron determines the orientation of its magnetic field. The spins of the electrons of a magnet are all lined up pointing in the same direction.
ii) Creating a magnet
(1) Electrons prefer to align their spins, but are so weak that each can only affect its closest neighbors - in other words, while each node's information about the network is local, magnetism requires global coordination
(2) Frustrated state: as groups of electrons form (all pointing in the same direction), neighboring groups tend to point in opposite directions, unable to affect one another's spins & balancing out magnetic fields
(3) To magnetize a piece of metal, you need an outside source of magnetism and a specific amount of energy (force or heat) to re-start the transitions - too much energy and all spins will flip around randomly
iii) Transition to magnetism: each node (electron spin) is still only able to act locally, but at the transition point they all behave as though they can communicate globally
(1) Correlation length: the distance at which each node appears to communicate
(2) Criticality: the critical point when the correlation length crosses the entire system - each node affects every other
(3) Global coordination without central authority
(4) Phase transition - a sudden transition state, as opposed to gradual change
b) Similarity to the spontaneous coordination of clapping crowds, freezing of liquids, transition to superconductivity, & random graph connectivity
c) Universality classes - classes of (perhaps dissimilar) systems which display common properties may be studied in abstract rather than in detail - we can gain understanding with simple models

5) Small World Networks
a) Alpha Model: Duncan Watts and Steven Strogatz
i) Clustering
(1) How does the importance of mutual friends affect the creation of new links in a network. They began by graphing network development at the two extremes
(a) The top curve represents when as little as one mutual friend give A & B a strong chance of linking
(b) The bottom curve occurs when all nodes are just as likely to link
(2) Once the extremes defined the boundaries of the range of possibilities, the intermediate values could be sketched in.
(a) Each curve defines a different rule for node linking based on the tendency for mutual friends to affect the chances of a link
(b) This family of rules can be expressed as an equation with a tunable parameter, alpha
(3) Mapping the average path lengths for networks created with a range of alpha values
(a) Low alpha values created highly-clustered networks of unconnected components
(b) High values of alpha created basically random graphs
(c) There is a critical alpha value that creates a network of numerous small clusters connected globally with a relatively small path length for reaching any node from any other
(4) Comparing average path length and clustering coefficient
(a) Path length (L) spikes at a critical alpha value
(b) There is high clustering for lower values of alpha
(c) To the left of the spike in path length, networks are fragmented (paths are short because they don't cross the network, only their clusters
(d) To the right of the spike in path length, there is a region where clustering is still relatively high, but path length dramatically drops - small world networks
b) Beta Model: Duncan Watts and Steven Strogatz
(1) Networks on a periodic lattice - easier to understand than a random network
(a) Path length across the network is quite long when only neighbors are linked (left side)
(b) A completely random network on the right
(c) With only a few random rewirings, clustering coefficient remains high but path length dramatically drops (middle)
(2) Understanding Alpha
(a) Regardless of the size of the network, it takes only 5 random rewirings to reduce average path length by half
(b) Diminishing return: to reduce average path length by another half requires another 50 links
(c) Clustering coefficient slowly drops as links are re-wired randomly
(d) The space between the drop in path length and in clustering coefficient is where small world networks exist
(e) So, alpha from the last model was the probability that the network would have long-range random shortcuts, which have the effect of reducing path length

6) Six Degrees from Kevin Bacon
a) Bacon Number
i) If an actor has been in a movie with Kevin Bacon, the Bacon # is 1
ii) If an actor hasn?t been in a movie with Kevin Bacon, but has been in a movie with someone with a Bacon # of 1, their Bacon # is 2
iii) Etc
b) Distance Degree Distribution
i) The large majority of actors have a Bacon # of 4 or less
ii) The largest Bacon # is 10
iii) The average is less than 4
c) Small world networks: path length is close to that of a random graph, but the clustering coefficient is high
i) Movie actors
ii) Power grid dynamics
iii) Neural network of C. Elegans (earth worm)

7) Scale-Free Networks
a) Degree distribution: distribution of # of neighbors per node
b) Poisson distribution: the mathematical form describing the degree distribution of a random graph - fairly normal distribution
c) Barabasi and Albert demonstrated that many networks do not follow the Poisson distribution - they follow a power law distribution
i) Power laws don't have a peak - they start at their maximum and decrease to infinity
ii) Power laws have a slower decay rate than normal distribution, so extremes are more likely
iii) Unlike normal distribution, power laws do not have cut-offs for value (scale-free), so any number of links may be possible in a power-law distribution
iv) Scale-free networks have some super-connected nodes (hubs) and many nodes with fewer links
(1) Internet
(2) Metabolic networks of certain organisms
(3) Airlines
d) Barabasi and Albert also demonstrated how scale-free networks develop over time
i) In a random graph, poorly-connected nodes are just as likely to make new connections as well-connected nodes, and everything evens out in the end
ii) Real life: the rich get richer - with resources, it's easier to accumulate more
iii) Preferential growth model: the evolution of real networks
(1) If a node has twice as many links as another, it is exactly twice as likely to attain a new link
(2) New nodes should be added - network growth
(3) Over time, a network evolved this way demonstrates a power law distribution
e) Drawbacks
i) Since most networks have a finite number of nodes, there must be a cut-off at some point
(1) In real life, that cut-off is far below the number of nodes, since a person only has the time & energy for a certain number of friends
ii) Barabasi and Albert assumed that creating and maintaining links comes at no cost
(1) this assumption works for some types of real-life networks like the Internet, but not for others like biological systems
iii) Information is assumed to be widely available, but in real-life systems information is usually local

8) Affiliation Networks
a) Duncan Watts, Steven Strogatz, and Mark Newman attempted to create a random network that would better account for social structure
i) People identify themselves with many different social groups
ii) The more groups people share, the closer they are, the more likely they are to be friends
iii) Define the groups and the individuals associated with the groups, and the distance between people will be defined by those associations
iv) Two types of nodes, actors and groups
v) Bipartite (two-mode) network
vi) Random affiliation networks will always be small world networks

9) Searching Networks
a) Broadcast Search: each node sends a signal to every other node, ensuring that all nodes will be contacted during the search, and the shortest path may be found
i) Not an efficient way to search a network
ii) Likely to overload a system
b) Directed Search: in Milgram's experiment, each of the 100 starting people were given one letter only, and they were to pass it along to one person they new who they supposed would be closer to the target
i) A directed search requires some kind of information about your neighbor - not about the whole network, but local information by which to choose a link to follow
ii) Directed searches may not find the shortest path
c) Jon Kleinberg wanted to know how individuals find the path
i) Uniform random connections: random links are as likely between any 2 nodes, as used in previous small-world networks
(1) Since nodes are locally informed, a node without a long-distance shortcut cannot assist in a directed search
(2) Proved mathematically that a network created with uniform random connections cannot perform a directed search
ii) People judge distance from one node to another in many different ways: social, physical, race, class, profession, education
iii) Kleinberg's model used a lattice and random links were created based on probability which increased as distance between nodes decreased
(1) Only a specific probability constant of 2 would produce short, searchable paths
(2) At this critical value, each node has as many local nodes as shortcuts to further nodes, making directed searches possible
d) Duncan Watts, Mark Newman, and Peter Dodds
i) People measure distance through a hierarchy of the social groups to which they belong
ii) Model of affiliation groups that accounts for social distance
(1) The higher up the hierarchy you have to go to find a common branch, the further apart two groups are in distance
(2) Used in an affiliation network, this accounts for affiliations of difference strengths
(3) Two nodes may be close in one affiliation group and not in another
(4) Close affiliation in one context is enough to consider distance to be close
(5) It's the multi-dimensional nature of social relations that allows directed searches to occur
(6) The network was highly searchable regardless of the number of social dimensions or homophily parameter (probability that nodes will link to dissimilar nodes)

10) Epidemics and Failures
a) Biological diseases and computer viruses perform broadcast searches
i) The susceptibility of a node varies, depending on how contagious a disease is, or what kinds of computer systems
b) SIR model
i) Epidemiological model
ii) Members of the population are Susceptible (vulnerable but not yet infected), Infectious, or Removed (recovered or dead)
iii) Assumes random interactions between members
(1) Probability of infection is determined by the sizes of infected and susceptible populations
iv) Logistic growth
(1) Slow growth phase: few infected people to spread quickly
(2) Explosive phase: sudden cross of threshold value
(3) Burnout Phase: leveling out - few people left to infect
v) Ignores population structure
c) Epidemics in Small World Networks
i) Comparison of infectiousness on types of networks
(1) Random graph represents the SIR model, with a logistic growth
(2) Lattice - disease can spread only in two dimensions - only very infectious diseases become epidemics, and they spread very slowly
(3) Clustered model: it took only a few random links added to a lattice to cause a jump in infectiousness approaching that of a random network
ii) Conclusions
(1) Locally, disease growth behaves as though it is on a lattice
(2) When a disease reaches a shortcut, then it behaves as though it is on a random network
(3) Focus disease prevention on shortcuts: airlines, livestock movement, HIV needle-exchange program (needles shared not only among friends but also between strangers)
d) Percolation Models
i) Each site (node) has an occupation probability, which represents susceptibility
ii) Each bond (link) is either open or closed, with a probability based on the infectiousness of the disease
iii) From a random start point, imagine fluid pumped into the system through open bonds to all other susceptible sites. All affected sites are considered part of the cluster, where infection occurs.
iv) This model helps demonstrate how these parameters affect the spread of disease
v) Epidemics depend on both factors to create a percolating cluster, without which outbreaks will be small and isolated

11) Information Cascades & Collective Behavior
a) Financial crises like the stock market bubble have been documented for two centuries
i) What makes people act against common sense and follow the "rush"?
b) Cooperation
i) Diner's Dilemma: you go out to dinner with friends and you plan to split the bill evenly - what will you order?
(1) If everyone gets the cheap meal then the bill will be low - collective good
(2) If you're the only one to get the expensive meal, you're going to get it at a bargain
(3) If you're the only one getting the cheap meal, you're going to overpay for it
ii) Tragedy of the Commons: there's a common field free to all villagers to use to pasture their livestock
(1) Grazing one extra sheep will make it easier to feed/clothe your family (increase your personal wealth) - everyone has personal incentive to add livestock
(2) If everyone continues to add livestock, soon the pasture will be over-grazed and unable to sustain any livestock
(3) Individuals are concerned with their own interests, and only able to control their own actions, but are subject to the consequences of everyone else's decisions
iii) Social movements, such as the Leipzig parades that were pivotal in bringing down the Berlin Wall, are often un-centralized / uncoordinated
c) Failures
i) Power grid failures - cumulative small failures, unexpected result
ii) Challenger shuttle - a convergence of minor, routine issues (normal accidents)
d) Information Externalities
i) 1950's social psychologist Solomon Asch experiments: show a group of people a picture, and ask them a question about it for which the answer should be obvious.
(1) When all of the people except 1 are not subjects – they're pretending to be subjects and unanimously give the same wrong answer: 1/3 of the time the subject would agree with the others and give the false answer
(a) There were signs of distress (perspiration, agitation)
(2) Regardless of the size of the group of people, when there was at least one other person giving the right answer, the subjects were most likely to give the right answer
(3) People pay attention to their peers when making decisions
(a) In trying to minimize our personal risks, we tend to rely on majority opinions
(b) Problem-solving mechanism: sometimes we lack information, sometimes too much information to process
e) Coercive Externalities
i) In Asch's experiment, when only 1 person was secretly instructed to give a false answer, the others laughed at him
ii) Spiral of Silence: West Germany 1960?s & 1970?s Elisabeth Noelle-Neumann
(1) Two political parties with a constant level of support by the electorate, yet the more vocal of the two was perceived to be the majority
(2) The perceived minority became less willing to speak out publicly, reinforcing the perception that they were in the minority and further silencing them
(3) The strongest predictor on election day wasn't which party each voter supported but which party each voter expected to win
f) Market Externalities
i) Unlike cars and copiers, technology like fax machines are not self-contained - a fax is useless unless you want to communicate with someone else with a fax machine
(1) Individuals make the purchasing decision, but the evaluation of that decision is based on what the collective is doing
ii) Complimentaries: products that increase one another's value, like PCs and software
g) Coordination Externalities
i) Some decisions are affected by situations like the Diner's Dilemma and the Tragedy of the Commons
ii) Trade-off between personal gain and collective good
iii) To contribute to the collective good,
(1) an individual must care about the future
(2) and believe that participation will cause others to do so
iv) Individuals must pay attention to what others are doing: if enough people seem to be doing something for the collective good, then an individual will judge it worth doing
h) Information Cascade
i) A shock in the network becomes a cascade across the system
(1) Cooperation
(2) Financial crises
(3) Social fads
ii) Threshold models of decision making
(1) Asch's experiment demonstrated that it's not the absolute number of external influences, but the fractional number
(2) Size is important, therefore, only in proportion to how much influence each neighboring node will have
(3) Disease metaphor breaks down: unlike disease, which infects a node at a probability based on infectiousness & susceptibility - the same probability each time the node is exposed - and not cumulative like an information cascade
(4) Social contagion follows a threshold rule, where it takes a certain number of exposures for a node to switch from one Boolean condition to the other
iii) What are the consequences at the population level?
(1) Each node has its own threshold level - there will be a distribution of threshold values, with more nodes in the middle range and a few at the extremes
(2) A single node will start the shock to the network, lower threshold nodes will pass it along, and cumulative exposures may trigger slightly higher threshold nodes, etc
iv) What features of a social network allow cascades?
(1) Localized contagion happens in isolated groups: cults
(2) Innovator - the starting node
(3) Threshold is the fraction of a node's neighbors that must be active
(4) Early adopters - threshold proportional to # neighbors is low enough to activate with only 1 active neighbor
(5) A node's degree (# of neighbors) becomes important
(6) A cascade can only happen if the innovator is connected to an early adopter
v) Percolation model: early adopters form percolating clusters.
(1) If the network has a percolating cluster, then a cascade is possible
vi) Phase diagram: all possible systems
(1) Horizontal axis: average value of threshold distribution
(2) Vertical axis: average degree (# network neighbors)
(3) Shaded region: where global cascades can occur
(4) Phase transitions occur at the upper and lower boundaries
(a) At the lower boundary,
(i) there are few neighbors and the threshold is easily met
(ii) the phase transition is the same as for biological diseases
(iii) as with disease, network connectivity is what restricts the cascade
(iv) as with disease, well-connected individuals help spread the contagion
(v) as with disease, cascades tend to be localized - propagates through the vulnerable cluster, but fewer connections keep it from spreading
(b) At the upper boundary
(i) greater connectivity always makes diseases more likely to spread, but makes global cascades impossible (since each neighbor's proportional influence is therefore diminished and the threshold is less likely to be met)
(ii) though cascades are rare, when they occur they tend to traverse the system since the network is highly connected

12) Adaptation
a) Toyota-Aisin crisis
i) 1980's Toyota manufacturing strategies
(1) Just-in-time inventory systems - produce parts as needed
(2) Simultaneous engineering - changes to design on-the-fly - adaptation
(3) High division of labor - member companies specializing in specific parts
(4) High level of cooperation between member firms, exchange of personnel
ii) Aisin - sole provider of P-Valves, specialized tools & expertise in design
iii) Aisin's only factory burned down overnight
(1) All production at all Toyota factories stopped
iv) Within 3 days, member companies coordinated & worked with Aisin engineers to produce P-Valves at near normal levels
b) Hierarchy functions when market is well-understood
c) Once there is ambiguity, decisions and problem-solving often have to occur at lower levels of production rather than through hierarchy
i) Communication in a hierarchy requires many steps through the structure to reach one node from another
(1) Ambiguity requires more communication
(2) Individuals have capacity constraints
(3) Hierarchy will bottleneck trying to resolve high levels of ambiguity
ii) Randomly adding shortcuts
(1) Dramatically reduces overall path length for some nodes, but still doesn't account for capacity constraints or for the stratification of information
iii) Team building: shortcuts between neighbors
(1) Local teams at each level of the hierarchy need to communicate / solve problems
(2) Effective where most message-passing is at the local level
(3) Example: members of the same work team or the same ISP
iv) Periphery: shortcuts at the top of the hierarchy
(1) When message-passing is between distant nodes, congestion is at the top of the hierarchy
(2) The top level is connected to create cooperation and sharing of the communication lode
(3) Example: airline network, postal service
v) Multiscale connectivity
(1) Message-passing across each level
(2) All levels manage information
(3) Problem-solving is part of production