The Story of Networks
(Illustration: Creative Networking)
“The same mathematics of networks that governs the interactions of molecules in a cell, neurons in a brain, and species in an ecosystem can be used to understand the complex interconnections between people, the emergence of group identity, and the paths along which information, norms, and behavior spread from person to person to person.”
— James Fowler answering the question “If you only had a single statement to pass on to others summarizing the most vital lesson to be drawn from your work, what would it be?” in Starting Over, SEED, Aprill 22, 2011.
Seven Bridges of Königsberg
“It all starts in Königsberg, now Kalingrad, a small strip of Russian territory. In the 18th century, the philosopher Immanuel Kant, lived there and was famous for taking walks so regularly that it was said that people could set their clocks by him.
When Kant was still a young boy, the bridges had become the center of a popular riddle: Is it possible to walk across all seven bridges without crossing the same one twice? It was an enigma that defied an easy solution until it caught the eye of the Leonhard Euler, the greatest mathematician of that age.
To solve the Königsberg bridge problem, Euler developed a new type of mathematics called graph theory. He designated the four land masses that the bridges connected as nodes and the bridges themselves as links.
From there it was fairly easy to see that the only way someone could walk across all the bridges only once would be if there were an even number of bridges. It was a nice trick, but at the time, nobody realized how important Euler’s invention of graph theory would become.
One of the people who got interested in graphs was Paul Erdős.
Erdős was famous for showing up at mathematicians doors and announcing “my brain is open” (meaning that he was ready to collaborate). He did this so often, that mathematicians often rank themselves by their Erdős number, or how many links away they are from collaborating with him.
What Erdős realized is that if networks develop randomly, they are highly efficient. Even with a lot of nodes, you need relatively few links. Moreover, the larger the network, the less links you need, proportionately, to connect everything together.
The Milgram Small World Experiment: 6 Degrees of Separation
In 1967, the psychologist Stanley Milgram randomly selected people living in Wichita, Kansas and Omaha, Nebraska and asked them to get a letter to a stockbroker in Boston they had never met. This became known as the small world experiment.
The subjects were given no information except the man’s name and occupation and were only allowed to send the package to people they knew on a first name basis. Amazingly, the letters got there in about six steps on average. Just six relationships separated people across an entire continent!
(More modern e-mail experiments have confirmed most of Milgram’s findings).
Just as Erdős predicted, even in the huge network of people comprising the entire USA, it took an amazingly small amount of links to connect them all. There seemed to be mysterious forces at work that bind disparate parts into a coherent whole.
The Strength of Weak Ties
Mark Granovetter, a sociologist, was aware of Milgram’s work and decided to study the matter further. In the late 1960’s and Early 1970’s, he began studying how people found jobs in communities around Boston.
He soon found that successful job searches revolved around a strange combination of acquaintance and chance. Granovetter found that over 80% of the people in his study who found a job through a contact did not have a close relationship with that person.
Our friends have a lot more friends than we do, so we’ll often find what we’re looking for through the friends of our friends (besides, we share so much of our experiences with those close to us that they tend to have the same information we do). Granovetter called this phenomenon, The Strength of Weak Ties (pdf).”
— The Story of Networks, Digital Tonto, Sep 26, 2010
From mapping systems to controlling them
A Universe of Hubs: Mauro Martino, of Barabasi’s lab, illustrates how hubs act as an organizing principle within complex networks by plotting the 325,729 Web pages in the University of Notre Dame Web domain [green points]. He also mapped the 1,497,134 links that connect those pages [white lines]; for clarity, he showed only the strongest connections. Pages with many connections are hubs. Less-connected nodes cluster around them like planets gather around a star Mauro Martino/Barabási Lab
“In 1736 the Swiss mathematician Leonhard Euler ended a debate among the citizens of Königsberg, Prussia, by drawing a graph. The Pregel River divided the city, now Kaliningrad, Russia, into four sections. Seven bridges connected them. Could a person cross all seven without walking over the same one twice?
Euler began with a map that cleared away everything—the homes and streets and coffeehouses—irrelevant to the question at hand. Then he translated that map into something even more abstract, a depiction not of a physical place but of an interconnected system. The four sections became dots, and the seven bridges became lines. By transforming Königsberg into simple nodes and edges (as mathematicians have come to call such abstractions), Euler could subject the system to mathematical analysis. In doing so, he proved that a person could not cross all seven bridges without walking over the same one twice. More important, he mapped a network for the first time.
Over the next two centuries, scientists built on Euler’s work to develop graph theory, a branch of mathematics that would eventually serve as the basis for network science. But it wasn’t until 1959—when the Hungarian mathematicians Paul Erdös and Alfréd Rényi proposed a means by which complex networks evolve—that a defined theory of networks began to emerge. And it was only in the mid-1990s that scientists began to apply that theory to really complex problems. Before then, large data sets were difficult to obtain and even more difficult to process. But as data became more accessible and processing power cheaper, researchers began applying graph theory to everything from protein interactions to the workings of the power grid.
Albert-László Barabási a Romanian-born physicist at the University of Notre Dame, was one of those researchers. In the past decade and a half, has transformed the way his colleagues understand networks at least twice. His theories have influenced important developments in engineering, marketing, medicine and spycraft. And his research may soon allow engineers, marketers, doctors and spies to not just understand and predict network behavior, but also to control it. (…)
Barabási mapped several other large and complex systems, including the connections between transistors on computer chips and the collaborations between actors in Hollywood. In each case, highly linked nodes, which he called hubs, were the defining characteristic of the network, not just an anomaly but an organizing principle for engineered and natural systems alike. With his student Réka Albert, Barabási updated the Erdős–Rényi model to reflect the existence of hubs in real-world networks. In doing so, he created a tool for scientists to map and explore all manner of complex systems in ways they had never thought to before. (…)
Engineers use control theory to predict how systems will respond to various inputs, which in turn helps them make robots that can catch baseballs, cars that take sharp corners with ease, and planes that don’t fall from the sky. (…)
Like prediction, control required evaluating an object as a system with nodes of varying importance. A car for instance: “It is made of 5,000 components,” Barabási says, “yet you as a driver have access to only three to five nodes”—the steering wheel, the gas pedal, the brake, and maybe the clutch and shifter. “With those three to five knobs, you can make this system go anywhere a car can go.” What he wanted to know was if he could look at any network, not just engineered ones, and find those control nodes. Among the thousands of proteins operating within a cell, could he find the steering wheel, the gas pedal and the brake? (…)
Control nodes take instructions or signals from outside the network (for example, a foot on the gas pedal) and transmit them to nodes within the network (the fuel-injection system). To find them, Liu borrowed an algorithm, developed by Erdös and Rényi five decades prior, that acts as a signal moving through the network. It starts at one node and follows a random edge to another node, at which point it “erases” every other edge but the one it came in on and the one it will go out on. The algorithm runs through the entire network over and over until it finds the minimum set of starting points needed to reach every node in the system. Control these starting points, and you control the entire network. (…)
Whereas the neuronal map of C. elegansis complete, scientists have determined only about 5 percent of the connections in the yeast cell’s gene network. The more data scientists feed into the model, the better they can map connections in the network and the fewer control nodes they might need to operate the system. “We know these maps are incomplete,” Barabási says. “But they’re getting richer every day.” He also says his theory applies to total control of a network. Scientists who want partial control—say, to elicit a particular protein expression within a cell—would need to master far fewer nodes. (…)
“What we have to realize is that control is a natural progression of understanding processes,” he says. “But control is a question of will, and will can be controlled by laws. We have to come together as a society to figure out how far we can push it.”
The hidden influence of social networks: Nicholas Christakis on TED.com
“We’re all embedded in vast social networks of friends, family, co-workers and more. Nicholas Christakis tracks how a wide variety of traits — from happiness to obesity — can spread from person to person, showing how your location in the network might impact your life in ways you don’t even know.”
— Nicholas Christakis, Greek American physician and sociologist known for his research on social networks and on the socioeconomic and biosocial determinants of health, longevity, and behavior. Speech at TED2010, February 2010 in Long Beach, CA.
Manuel Lima: The Power of Networks. Mapping an increasingly complex world | TED
Manuel Lima is a Fellow of the Royal Society of Arts, nominated by Creativity magazine as “one of the 50 most creative and influential minds of 2009”, Manuel Lima is a Senior UX Design Lead at Microsoft Bing and founder of VisualComplexity.com - A visual exploration on mapping complex networks. TEDxBuenosAires, April 2011
The Power of Networks — Animated by RSA
☞ C. J. Stam, J. C. Reijneveld, Graph theoretical analysis of complex networks in the brain, Nonlinear Biomedical Physics, 2007 (research paper)
“Since the discovery of small-world and scale-free networks the study of complex systems from a network perspective has taken an enormous flight. In recent years many important properties of complex networks have been delineated. In particular, significant progress has been made in understanding the relationship between the structural properties of networks and the nature of dynamics taking place on these networks. For instance, the ‘synchronizability’ of complex networks of coupled oscillators can be determined by graph spectral analysis.
These developments in the theory of complex networks have inspired new applications in the field of neuroscience. Graph analysis has been used in the study of models of neural networks, anatomical connectivity, and functional connectivity based upon fMRI, EEG and MEG. These studies suggest that the human brain can be modelled as a complex network, and may have a small-world structure both at the level of anatomical as well as functional connectivity.
This small-world structure is hypothesized to reflect an optimal situation associated with rapid synchronization and information transfer, minimal wiring costs, as well as a balance between local processing and global integration. The topological structure of functional networks is probably restrained by genetic and anatomical factors, but can be modified during tasks. There is also increasing evidence that various types of brain disease such as Alzheimer’s disease, schizophrenia, brain tumours and epilepsy may be associated with deviations of the functional network topology from the optimal small-world pattern.”
☞ Nicholas Christakis: How social networks predict epidemics, TED video, June 2010
☞ Minority rules: Scientists discover tipping point for the spread of ideas
☞ The ‘rich club’ that rules your brain
☞ Eshel Ben-Jacob, Learning from Bacteria about Social Networks, Google Tech Talk, Sept 30, 2011 Video
☞ Genes and social networks: new research links genes to friendship networks
☞ Manuel Castells, Network Theories of Power - video lecture, USCAnnenberg
☞ Networks tag on Lapidarium