Link 1
Introduction
Feb 7 2000, SHOULD have been a big day for Yahoo. Instead of millions of users that daily flock to it, billions tried to enter. Such an exploding popularity could have made Yahoo the most valuable company of the emerging economy. There was however a problem, they all tried to enter at the same time, and not one of them asked for stock quote or pecan pie recipe. They rather sent a message in scripted computer language “I heard you!”. Hundreds of yahoo computers at Santa Clara and California were kept busy by these “ghosts”, while millions of legitimate users waited for a few minutes before they switched.
The next day Amazon.com, eBay, CNN.com, ETrade, and Excite, fell under the same spell. Of course making billions of real users hit yahoo.com in their browsers at 10.20pm is not a possibility. There simply weren’t enough computers to do that, at that time.
The consensus suggested it may be a group of sophisticated hackers, fascinated by the challenge of the security systems, who hijacked 1000’s of computers, at schools, research and turned them into zombies telling yahoo “I heard you!” thousands of time. Every second Yahoo was thrown huge amounts of data, which was much more than it could handle.
FBI following the leads based on a chat room voice bragging about next targets, arrived at the suburban home of a Canadian teenager, hiding behind the pseudonym mafia boy, a fifteen year old who successfully halted operations of billion dollar companies. The attempt succeeded with brute force, a lot of nerve and a little sophistication.
What is it that triggered the intelligent move to be so successful? What can, if a group of trained and skilled individuals do if they thought so?
Judaism was followed by a very small group of people who were prosecuted by both roman and Jewish authorities for putting Jesus, on the same level as God. Despite the odds now more than 2 billion people call Christianity their religion. This is no different from the above event.
The credit goes to a young chap Paul, who has never met Jesus.
Paul who was doing the prosecutions at the age of 34 underwent a major change and became a follower of what he opposed. He walked from land to land and spread the message. He walked more than 10000 miles in the twelve years of his life. He however did not walk randomly.. he reached out to the biggest communities of the era.
There is something that Paul and mafia boy did in common to bring about such a ground breaking change. They used a key in common, with or without knowing they are doing it, the structure of the network, which is defined by the property of how it grows into what it is.
These are two instances which are governed by the basic laws that govern all the networks. You will see how the emergence of a new company, trend, or the very same idea of the network study is also ruled by the laws of network formation.
This is the beginning of the pursuit of network theory..
Link 2
The Random Universe
Konigsberg, a flowering city in eastern Prussia, The healthy economy allowed city officials to build seven bridges across the river connecting different regions. The people of Konigsberg, enjoying a time of peace and prosperity, amused themselves with mind puzzles, one of which was: "Can one walk across the seven bridges and never cross the same one twice and end where they started?”
Almost 150 years ago, in 1736 Euler offered a rigorous mathematical proof stating that with the seven bridges such a path does not exist. He not only solved the Konigsberg problem but in his brief paper inadvertently started an immense branch of mathematics graph theory. Graph theory is the basis of networks.
Paul Erdos, mathematician from Budapest, wrote more than 1500 papers before his death in 1996. Such a work unparalleled since Euler, contained eight articles published with another Hungarian mathematician, Alfred Renyi. These eight papers addressed for the first time in history the most fundamental question pertaining to our under- standing of our interconnected universe: How do networks form? Their solution laid the foundation of random networks.
Erdos Renyi graph (network formation):
On a given set of n nodes
1) Pick a pair in random of the nc2 pairs, and toss a die.
If the output is one put an edge between them, else don’t
2) Repeat step two until you exhausted all pairs of nodes.
As you can see the graph has almost even distribution of edges over it. The degree distribution is similar to the graph obtained for the example below.
List all your acquaintances’ heights and plot the no. of people in each height range (range ex. 4-5 feet, 5-6 etc). to the height ranges. You observe something like this:
This is known as a bell curve. The extensive work of Erdos and Renyi gives an insight into a whole new universe of properties that have brilliant applications in yet to be known fields.
Barabasi discovered very soon that the human network or what nature follows isn’t quite formed like the above. The journey had just begun.
(Post note: Reading on Paul Erdos might get you started with the random world)
Link Three
Six Degrees of Separation
In 1912 , Frigyes Karinthy, a now celebrated writer from Budapest, sitting at a coffee house wrote anyone in this world can reach any one else in just few handshakes. He offered a bet that the readers
“could name any person among earth's one and a half billion inhabitants and through at most five acquaintances, one of which he knew personally, he could link to the chosen one," writes Karinthy in "Lancszemek."
Stanley Milgram who proves more than 42 successful tests awakened to the fact that, not only are we connected, but we live in a world in which no one is more than a few handshakes from anyone else. That is, we live in a small world.
(PS. One of the brilliant observations of the century, we will come back to look at it)
Link 4
Small Worlds
Duncan Watts, working on his Ph.D. in applied mathematics at Cornell Unive rsity in the mid-1990s, was asked to investigate a peculiar problem: how crickets synchronize their chirping. Male crickets attract females by chirping loudly. Unlike many humans, crickets eschew the spotlight by carefully listening to the other crickets around them, adjusting their chirp to match that of their neighbors.
Put many of them together and from the cacophony a symphony emerges that we often enjoy on the back porch on humid summer nights. Possessing an agile mind, watts has the rare ability to stop, step back, and reflect on his work, changing direction if he needs to. Indeed, the cricket study turned him into a student of social networks and eventually a sociologist. He turned to his guide Steven Strogatz, an applied Mathematics professor at Cornell University, who studied chaos and synchronization. Soon they were off to uncharted territories, taking networks beyond the boundaries set by Erdos and Renyi.
They looked at patterns in terms of clustering co efficient and their change due to addition of edges (not completely at random).
Clustering co efficient: total no. of edges on the graph/ The number of edges on a complete graph of same no. of nodes.
They were surprised to find the distance between any two vertices gets reduced to half of what it is when some edges were added. They found something common to the real world. They realized we live in small groups (they called small worlds) which are connected be feeble number of links.
Intuition told then everyone in this world can be connected with in few steps.
Link 5 (My Favorite)
The Hubs and Connectors
The Brilliant observation (Six degrees of separation):
Craig Fass, Brian Turtle, and Mike were watching “The Air Up” which was airing on television the night, they were at Albright College in Reading, Pennsylvania. They found something startling (Genius I would say their observation was).
Full of excitement, in January of 1994 they mailed a letter to the Jon Stewart Show, an irreverent celebrity talk show popular with college audiences. "We are three men on a mission. Our mission is to
Prove to the Jon Stewart audience, nay, the world, that Bacon is God."
Much to their surprise, they got their fifteen minutes of fame. They were invited to appear on the Stewart show with Kevin Bacon, and charmed the audience with their ability to connect Bacon to any actor whose name was thrown at them.
The Kevin Bacon game would have remained mere movie trivia had two computer science students not watched the Stewart show. Glen Wasson and Brett Tjaden, from the University of Virginia, immediately realized that determining the distance between any two actors was a viable computer science project, if one had access to a complete database of all actors and movies ever released. The Internet Movie Database, or IMDb.com, a cinephile powerhouse offering more information about actors and movies than one could ever need, was already in place. It took Wasson and Tjaden a few weeks of programming to set up The Oracle of Bacon Website, which became the unbeatable master of the game. If you type in the name of any two actors, in milliseconds it provides the shortest path between them, listing the chain of actors and movies through which they are connected. In no time the Website was receiving over 20,000 visits per day.
Though, Kevin Bacon was not at the centre of Hollywood, he was not even near. Studies showed he was the 876 most connected actor. It was luck as it chose him to be the ambassador of the six degrees.
It was found that there are very few nodes in networks that actually causes the six degrees of separation possible, like Kevin Bacon. These were called hubs. They connect the remote two ends of the network in just a few steps. These were found to be the ones which hold the network intact. Removing a few of these would trigger increase of distance between any two points big enough that they can’t be traced in short time.
For example:
Erdos is a Hub of the scientific society. An Erdos number 0 was assigned to Erdos. who co authored with Erdos was given erdos no.1. A co author to erdos no.1 is erdos no. 2 and so on. They seemed to map out the entire scientic society in just a few steps. Einstein had erdos no. 4.
However it’s amazing that Erdos has a Kevin Bacon no. 4. He starred in a documentary “N is a Number” with a guy who starred with some guy who had a Kevin bacon no. 2.
Link 6
The 80/ 20 Rule
Vilfredo Pareto, the influential economist, once pointed out the 80/20 rule (not inexact fraction by himself). In his garden 80% of the peas were produced by 20% of the peapods. He said this was the case many real scenarios than we can normally see. He said, 80 percent of Italy's land was owned by only 20 percent of the population. 80% of a company’s profit is produced by 20% of the employees, 80% customer service problems are produced by 20% of the customers. 80% of the crimes are produced by 20% of the criminals.
When Hawoong Jeong started building little robot to map the Web, He had naive expectations about what the network behind the Web would look like. Guided by the insights of Erdos and Renyi, he and Barabasi expected to find that WebPages are connected to each other randomly.
They were most surprised when they plotted the histogram of the number of nodes (websites) to the number of incoming links. It looked like:
There were 80% of the websites with almost the same number of links as each other (around 3-4). And 20% of them with more than 1000 and 2-3 with more than a million. Further findings returned an even more biased result. The web is not random which means every voice is not equally heard.
A bell curve is close to a democratic setup. Scientists observed that nature occasionally produces quantities that follow power law distribution.
Each power law is characterized by a unique exponent, telling us, for example, how many very popular WebPages are out there relative to the less popular ones.
Kenneth Wilson was an assistant professor, physics department of Cornell University, working on renormalization found the two missing critical exponents of the power law. A work which won him the 1982 Nobel Prize in physics. Thus, putting the finishing tip at the top of the pyramid.
Link 7
Rich get Richer
In 1999, while learning about the structure of other real networks, Barabasi realized what was not making the real world fit into the Erdos and Strogatz graphs. These two graphs already had the nodes in place. He said in real world networks, nodes are added in time and edge formation is not based on any specific criteria.
So he simulated a new graph where:
Nodes come in one at a time and have two edges each (Graph created over time) At any time when a node comes, the probability of it having an edge with any other node is directly proportional to the number of edges the other node has (preferential attachment).
This means that the node that comes first has maximum time to form the edges and the one that comes last the least. This in turn reinforces the edge forming ability of the nodes due to preferential attachment. This led to a new graph that more closely modeled the real world graphs. He called it Scale free model.
What it meant, a node coming as early in the network has the most chances of becoming the hub. An example cited by Barabasi of his familiarity that he would turn to a NY times review than a CNN since he would was reading NY times since his early time.
As a result of the pattern, he observed any new investment in the world went towards the node with more preference (degree) for example an advertisement of an apple pie on the yahoo recipes page is seen by very much more number of people than the number of people who see it on some healthy diets blog.
This followed a Pareto principle, and the need of preferential attachment destroyed the random world of Erdos and Renyi, leading to a world where Rich get richer.
First, power laws gave legitimacy to the hubs. Then the scale-free model elevated the power laws seen in real networks to a mathematically backed conceptual advance. Supported by a sophisticated theory
of evolving networks that allows us to precisely predict the scaling exponents and network dynamics, we have reached a new level of comprehension about our complex interconnected world, bringing us closer than ever to understanding the architecture of complexity. But the scale-free model raised new questions. One in particular kept resurfacing: How do latecomers make it in a world in which only
the rich get richer? The quest for the answer took us to a very unlikely place: the birth of quantum mechanics at the beginning of the twentieth century.
Link 8
Einstein's legacy
If the earliest nodes have a preference over the nodes that arrive late. Google a latecomer in the web has grown to be the biggest hub in short time. Google intrigued Barabasi because it violated the basic prediction of the scale-free model, that the first mover has an advantage. In the scale-free model the most connected nodes are those that appeared first. They have had the longest time to collect links and develop into hubs. Google, launched only in 1997, was a latecomer to the Web. Popular search engines like AltaVista or Inktomi had been dominating the market long before Google's arrival, clearly making it a second mover. In less than three years, however, Google became the biggest node and the most popular search engine.
He did find that in real world links are broken and formed. And this is driven by the fitness of the nodes. A fit node say that has a fitness number n, makes a link before all the nodes that‘re less fit than it. This recursively happens as the nodes come in with different fitness numbers. This has happened with Google. Barabasi is reminded a famous line on Google homepage “I’m feeling lucky”.
Bianconi, a member of Barabasi’s research group, with unusual fascination for physics, who quantum mechanically treated the network as a Bose-Einstein condensate, was able to clearly explain the network behavior. The nodes acted as levels and edges as particles, mathematics derived beyond a particular point (with the growth of a fit node into a hub) newly coming edges would fall under same level (node). While searching for real world examples they found, Bill Gates and Paul Allen’s Microsoft windows as one such. Beyond a particular time with increasing Windows, usage more than 94%,all the incoming computers used Windows whether they liked it or hated it.
Link 9
Achilles' heel
On learning about networks, Barabasi investigated whether there is a way to collapse these. His pursuit led him to find a big difference in the stabilities of the Erdos Renyi and Scale free networks.
An Erdos Renyi Network would collapse after a specific number of edges were randomly removed every time. He tried with Scale free networks, it was amazing to find that the network remained intact even after 98% of the edges were removed.
What is the source of this amazing topological robustness? The distinguishing feature of scale-free networks is the existence of hubs, the few highly connected nodes that keep these networks together. Failures, however, do not discriminate between nodes but affect small nodes and large hubs with the same probability. If I blindly pick ten balls from a bag in which there are 10 red and 9,990 white balls, chances are ninety nine in a hundred that I will have only white balls in my hand.Therefore, if failures in networks affect with equal chance all nodes, small nodes are far more likely to be dismantled, since there are many more of them. Small nodes contribute little to a network's integrity.
He then tried hitting the hubs. Not to his surprise the networks collapsed soon after he removed a few hubs.
This in turn became the basic strategy of the US military as a valuable defense method.
So, how vulnerable are we?
Fortunately, our understanding of attacks indicates that cascading failures and local breakdowns can be addressed.
Link 10
Viruses and Fads
The search for reasons for the spread of aids, which further led to the study of the sexual network gave a startling discovery, the sexual networks were indeed following a power law.This meant they were scale free. If not they could stop the spread of the disease, they started treating the hubs, and this has indeed slowed down the spread.
Barabasi observed that, the same structure of the scale free network supports the spread of even a weak infection. This network simply overthrows the threshold of virus/bacteria as in random network, in which they die out when their virulence is below a threshold. Once a virus reaches a hub it spreads to all its links and so on. So, unconfirmed reports suggest a single air host responsible for carrying the AIDS virus to America who is said to be a hub with 250 sexual partners a year.
It is the same in internet network as above, a best example the spread of the luv virus that spread around the world in days and still exists in few parts of the world despite anti love virus cures being available.
Link 11
The Awakening Internet
From deduced maps of the internet. It was found it was a scale free network growing at a huge rate. With increased number of resources online, the question rises as to how to use them efficiently.
Experts predict that there are will be around 10,000 telemetric devices for each human on the planet. This number is not particularly significant in and of itself, we've had sensors for a long time, ranging from surveillance cameras in supermarkets to car detectors buried in the pavement at traffic signals that switch the lights at the intersection. What is changing is that for the first time these various sensors are feeding information into a single integrated system. There will soon be over 3 billion Internet connected cell phones and close to 16 billion Internet-connected computers embedded in everything from toasters to fashion designs. The tiny sensors of this planetary skin will spy on everything from the environment to our highways and bodies. Most importantly, however, they are all connected.
Our planet is evolving into a single vast computer made of billions of interconnected processors and sensors. The question being asked by many is, when will this computer become self-aware? When will a thinking machine, orders of magnitude faster than a human brain, emerge spontaneously from billions of interconnected modules? It is impossible to predict when the Internet will become self aware, but clearly it already lives a life of its own. It grows and evolves at an unparalleled rate while following the same laws that nature uses to spin its own webs. Indeed, it shows many similarities to real organisms. Just like the millions of reactions taking place in a cell, terabytes of information are passed along its links every day. The surprising thing is that some of this information is very difficult to find. That brings us to yet another network: the World Wide Web.
Link 12
The Fragmented Web
The web is a directed graph. Mapping the directions and hubs leads to web which is fragmented into 4 continents. One with the core, to where most of the links point. The core points to a OUT continent which is a dead end (no links lead to any where out side it). All the IN links point to the core and a few to OUT continent. And the fourth quarter is a bunch of disconnected islands with few links towards IN, OUT and central continents.
Far from being a homogenous sea of nodes and links, the Web is fragmented into four continents, each of which hosts many villages and cities that appear as overlapping communities. Any of us willing to take
up a virtual presence belongs to one or several of them. To be sure, we are far from fully understanding this fine structure of the Web. But many forces, from commercial interests to scientific curiosity, increasingly motivate us to do better. As we dig deeper, I am sure that we will encounter many surprises, offering us an even clearer view of this complex, amorphous, ever changing online universe.
Something exhibited by governments trying to have a say in what the websites should show and should not, has an effect on the links formed by the hubs.
Link 13
The map of life (by the six degrees of separation)
In FEBRUARY 1987 the journal Nature reported a landmark discovery: the gene for manic depression, or by its more recent name, bipolar disorder. Manic depression affects 1 to 5 percent of adults in the
United States, and as many as 25 to 50 percent of those attempt suicide at least once. Because the risk of developing manic depression is five to ten times higher if first-degree relatives have the disease, the prevailing view is that manic depression is a genetic disorder. So as soon as methods for linking illnesses to specific genes emerged, the race was on to find the manic depression gene. The much coveted "first" seemed to have gone to the authors of the 1987 Nature paper, who located the gene on chromosome 11 while studying a large Amish family in Lancaster, Pennsylvania. Yet two years later the research group recanted the results. The blunder did not discourage other gene hunters, however. If anything, it gave them extra motivation to find the real gene. In 1996, almost a decade after the first published study, three independent research groups reported links to genes on other chromosomes. Another Amish study implicated chromosomes 6, 13, and 15; a study focusing on the isolated population of Costa Rica's Central Valley documented links to chromosome 18; and results derived from a large Scottish family indicated the involvement of chromosome 4. Research on another prominent mental disorder, schizophrenia, followed a similar pattern, linking the disease to two different regions of chromosome 1, with a different research group implicating chromosome 5 a few years later. Absentminded scientists? Bad research? Far from it.
These are not conflicting results. They simply demonstrate that most illnesses, rang- ing from manic depression to cancer, are not caused by a single malfunctioning gene. Rather, several genes interacting through a complex network hidden within our cells are simultaneously responsible. Faced with the gigantic task of figuring out the building blocks of the cell, from genes to proteins, scientists until recently focused on biology rather than networks. But with the pieces now in hand, post genomic
biology is taking a step back to grasp the big picture. New and exciting discoveries that are revolutionizing biology and medicine tell us loud and clear: If we want to understand life—and ultimately cure disease— we must think networks.
When studying about the Protein interaction network, they were surprised to find they could map every protein in 3 to 4 steps. They found what they call P53 gene, which produces P53 protein to be an evolutionary protein that was not left behind. This had a particular function in every protein interaction. This protein when it fails to provide command to destroy the Existing DNA cells to produce new Cancer occurs. The entire map of the network isn’t mapped out yet. However, the link of the proteins between different diseases and provided a vision towards treating diseases.
Link 14
The Network Economy
Economy too is driven by a scale free from. Where the dominance is a characteristic of being a hub. Any changes to hubs greatly affect the economies. While the failure or selling of minor companies is of very less importance.
Such a hierarchy is found in the work structure of the companies. Here people who are directors of more than one firm play as hubs bringing the changes in the economy.
Link 15
Web without a Spider
In 1994, or even in early 1998, nobody could have anticipated the flood of discoveries that would completely reshape our understanding of our interconnected world in the following years. Not even in my wildest dreams I could conjure power laws or scale-free networks, he says. There is how ever a self balancing act by the natural networks, as observed by not hunting the sea otters. When these nodes carry load and there is a bearing capacity for each link, a scale free network can breakdown due to a cascading effect when the hierarchy of capacity breaks is found.
Today we know that, though real networks are not as random as Erdos and Renyi envisioned, chance and randomness do play an important role in their construction. Real networks are not static, as all graph theoretical models were until recently. Instead, growth plays a key role in shaping their topology. They are not as centralized as a star network is. Rather, there is a hierarchy of hubs that keep these networks together, a heavily connected node closely followed by several less connected ones, trailed by dozens of even smaller nodes. No central node sits in the middle of the spider web, controlling and monitoring every link and node. There is no single node whose removal could break the web. A scale-free network is a web without a spider.
In the twentieth century we went as far as we could to uncover and describe the components of complex systems. Our quest to understand nature has hit a glass ceiling because we do not yet know how to fit the pieces together. The complex issues with which we are faced, in fields from communication systems to cell biology, demand a brand new framework. Embarking on the journey ahead without a map would be hopeless. Fortunately the ongoing network revolution has already provided many of the key maps. Though there are still many "dragons" ahead, the shape of a new world has become discernible, continent by continent. Most important, we have learned the laws of web cartography, allowing us to draw new maps whenever we are faced with new systems. Now we must follow these maps to complete the journey, fitting the pieces to one another, node by node and link by link, and capturing their dynamic interplay. We have ninety-eight years to succeed at this, and make the twenty-first the century of complexity.
- Barabasi
( Compiled by Arvind M )
Let us assume that
our n jobs are sorted by non-decreasing finish times fi .
