Network Science

Theory and Applications

Ted G. Lewis, PhD, Ted G. Lewis

• Publisher: Wiley
• Year: 2011
• Print ISBN:
  9780470331880
• Edition: 1
• eBook ISBN:
  9781118211014
• Topic: Computer Science
• Subtopic: Computer Networking
• Index: Computer Science

A comprehensive look at the emerging science of networks

Network science helps you design faster, more resilient communication networks; revise infrastructure systems such as electrical power grids, telecommunications networks, and airline routes; model market dynamics; understand synchronization in biological systems; and analyze social interactions among people.

This is the first book to take a comprehensive look at this emerging science. It examines the various kinds of networks (regular, random, small-world, influence, scale-free, and social) and applies network processes and behaviors to emergence, epidemics, synchrony, and risk. The book's uniqueness lies in its integration of concepts across computer science, biology, physics, social network analysis, economics, and marketing.

The book is divided into easy-to-understand topical chapters and the presentation is augmented with clear illustrations, problems and answers, examples, applications, tutorials, and a discussion of related Java software. Chapters cover:

• Origins
• Graphs
• Regular Networks
• Random Networks
• Small-World Networks
• Scale-Free Networks
• Emergence
• Epidemics
• Synchrony
• Influence Networks
• Vulnerability
• Net Gain
• Biology

This book offers a new understanding and interpretation of the field of network science. It is an indispensable resource for researchers, professionals, and technicians in engineering, computing, and biology. It also serves as a valuable textbook for advanced undergraduate and graduate courses in related fields of study.

1

ORIGINS

The “new science of networks”—an emerging field of study that we abbreviate as network science, is really quite old, having roots as far back as 1736. Essentially the application of mathematical graph theory to problems in a variety of fields, network science reemerged in the late 1990s as a “new science.” But graph theory has been applied to practical problems since its inception in 1736, when Swiss mathematician Leonhard Euler solved the very real-world problem of how best to circumnavigate the Bridges of Königsberg, using graph theory.

Graph theorists spent the next 200 years in the backwaters of arcane mathematics. But it is difficult to keep a good idea down for long. The mathematics of graphs appeared again in the 1950s when the Hungarian and nomadic mathematician Paul Erdos (1913–1996) reestablished graph theory (and created the branch known as discrete mathematics) with papers on random graphs. Erdos’ colorful description of mathematics as a machine for turning coffee into theorems preferred extended visits with other mathematicians to owning his own home. Today, we use the Erdos–Renyi (ER) random graph as a kind of benchmark—to compare with nonrandom graphs. The ER generative procedure for constructing a random graph marked a second historical milestone in 1959–60 (see Table 1.1).

In the late 1960s and 1970s graph theory was used by social scientists to model social networks and study the behavior of humans in groups. Stanley Milgram is credited with introducing the notion of a small-world network to the social science community—igniting interest in studies of how network topology might influence human behavior—and the reverse. The “small-world dilemma” was the subject of vigorous study throughout this period. Why is it, social scientists asked, that humans are able to connect to one another through an extremely small number of intermediaries, even as the size of a population grows?

TABLE 1.1 Historical Timeline of Significant Events

Date	Who	Contribution
1736	Euler	Bridges of Königsberg
1925	G. Yule	Preferential attachment, Yule–Simon distribution
1927	Kermack, McKendrick	First epidemic model
1951	Solomonoff, Rappaport	Spread of infection in random networks
1955	Simon	Power law observed in word analysis
1959	Gilbert	First generative procedure for random graph
1960	Erdos, Renyi	Random graphs
1967	Milgram	Small-world experiment
1969	Bass	Diffusion of innovation in populations—nonnetwork model
1971	Fisher, Pry	Diffusion by product substitution—nonnetwork model
1972	Bollobas	Complex graphs
1972	Bonacich	Idea of influence in social networks leading to influence diagrams
1973	Granovetter	Job-seeking networks formed clusters with “weak links” between them
1978	Pool, Kochen	First theoretical examination of small worlds
1984	Kuramoto	Synchronization of linear systems
1985	Bollobas	Publishes book on “random graphs”
1988	Waxman	First graph model of the Internet
1989	Bristor, Ryan	“Buying networks” = application of network science to model economic system
1990	Guare	Coined phrase, “six degrees of separation” = name of his Broadway play
1995	Molloy, Reed	Generation of networks with arbitrary degree sequence distribution
1996	Kretschmar, Morris	Early application of network science to spread of infectious disease = contagion driven by largest connected component
1998	Holland	Introduction of emergence in complex adaptive systems
1998	Watts, Strogatz, Faloutsos, Faloutsos	Renewed interest in Milgram’s original work on small worlds, examples of clustering; first generative procedure for small world
1999	Faloutsos	Power law observed in Internet
1999	Albert, Jeong, Barabasi	Power law observed in WWW
1999	Dorogovtsev, Mendes	Small-world properties
1999	Barabasi, Albert,	Scale-free network model
1999	Dorogovtsev, Mendes, Samukhim, Krapivsky Redner	Exact solution to scale-free network degree sequence
1999	Watts	Explanation of “small-world dilemma”: high clustering, low path length
1999	Adamic	Distance between .edu sites shown to be small-world
1999	Kleinberg, Kumar, Raghavan, Rajagopalan Tomkins	Formalized model of WWW as “Webgraph”
1999	Walsh	Difficulty of search in small worlds using local properties
2000	Marchiori, Latora,	Harmonic distance replaces path length: works for disconnected networks
2000	Broder, Kumar, Maghoul, Raghavan, Rajagopalan Stata, Tomkins, Wiener	Full Webgraph map of the WWW
2000	Kleinberg	Shows O(n) search in small world using “Manhattan distance”
2000	Albert, Jeong, Barabasi	Scale-free networks are resilient if hubs are protected (Internet’s “Achilles heel”)
2001	Yung	Taxonomy of applications of small-world theory to: SNA, collaboration, Internet, business, life sciences
2001	Pastor-Satorras, Vespignani	Claim no epidemic threshold in scale-free networks; Internet susceptible to SIS viruses
2001	Tadic, Adamic	Use of local information can speed search on scale- free networks
2002	Levene, Fenner, Loizou, Wheeldon	Enhanced Webgraph model concluded structure of the WWW couldn’t be explained by preferential attachment alone
2002	Kleinfeld,	Claims Milgram experiments not well founded: small- world social network is an “urban myth”
2002	Wang, Chen, Barahona, Pecora, Liu, Hong, Choi Kim, Jost, Joy	Sync in small worlds equivalent to stability in coupled system
2003	Wang, Chakrabarti, Wang, Faloutsos	Showed spread of epidemics determined by network’s spectral radius, largest eigenvalue of connection matrix
2003	Virtanen	Complete survey of network science results up to 2003
2003	Strogatz	Synchronization of crickets, heartbeats
2005	NRC	Definition of network science
2006	Atay	Synchronization in networks with degree sequence distribution—application to networks
2007	Gabbay	Consensus in influence networks—linear and nonlinear models

Milgram’s famous “six degrees of separation” experiment suggested that the distance between two people selected at random from the entire population of the United States is approximately six intermediaries. In Milgram’s experiment, volunteers in Kansas and Nebraska were asked to forward a letter to an unfamiliar target living in Cambridge and Boston, Massachusetts. Not knowing the target person, recipients forwarded the letter to an acquaintance closer to the target than themselves. Many of the letters were lost, but of the ones that eventually reached their target addresses, the number of hops along the chain of intermediaries ranged from 2 to 10, with an average of 5.2. Hence the notion of a small world and six degrees of separation was born.

Network science took its third, and current step toward becoming a scientific discipline of its own in the late 1990s when a number of scientists in other fields began to use networks as models of physical and biological phenomena. In particular, the pioneering work of Duncan Watts, Steven Strogatz, and Albert-Laszlo Barabasi stimulated renewed interest in mathematical analysis of networks as applied to the physical world. Watts equated the structure of very sparse networks with small diameter (small worlds) with a diverse number of phenomena such as phase transitions in materials, functionality of biological organisms, and behavior of electrical power grids. How could a simple graph model explain such diversity of real-world behaviors?

Strogatz studied the impact of network structure on complex adaptive systems in physics as well as explaining why hearts beat in a regular synchronized pattern in mammals, and why a certain species of firefly rhythmically chirps in unison without centralized control. It appeared that living organisms tend to synchronize their behavior without global knowledge. In this book, we show that a deep understanding of how and why network synchronization occurs in physical and biological systems also explains the conditions for arriving at a consensus by a group of people, how best to conduct product marketing campaigns, and how corporations rise to become a monopoly. Synchronization is a byproduct of the structure of “living networks.”

Barabasi and students created another line of investigation with the invention of scale-free networks—nonrandom networks with hubs. In a number of studies of the structure of the Internet and WWW, Barabasi et al. discovered an emergent property of the decentralized Internet—that it had emerged without central planning into a structure consisting of a small number of extremely popular sites called hubs, and a large number of “unpopular” sites with few links. Instead of being random, like an ER (Erdos–Renyi) network, the Internet topology was very nonrandom. In fact, the probability that a site has k links obeys a power law, which drops off quickly for large k. Furthermore, they speculated that this was the result of a microrule called preferential attachment—that the probability a site will obtain a new link is directly proportional to the number of links it already has. Thus, the more links a site has, the more it gets—the so-called “rich get richer” phenomenon.

Scale-free networks are extremely nonrandom. This discovery set the stage for a plethora of publications in a diverse number of disciplines ranging from political science to sociology, biology, and physics. Why do so many natural phenomena obey the power law instead of the normal distribution or perhaps the exponential distribution? Once again, the stage was set for deep inquiry into the structure of organizations, organisms, and physical matter to explain the questions raised by the power law.

The current state of network science can best be described as “still evolving.” In its modern form, it is approximately a decade old. Discoveries continue to be made on a monthly basis, which means that this book will soon be out of date! Therefore, the author has attempted to focus on the fundamentals—results that hopefully will endure for decades—rather than delve into interesting but distracting diversions.

The purpose of this chapter is to define the emerging discipline called network science and develop a historical timeline of key events leading up to the current state of the field. We survey that past 270 years leading up to the current state of the art, and end with a loose collection of “rules” for networks. We study the following in detail:

1. Network science can be defined in many ways. We loosely define it as the study of the theoretical foundations of network structure/dynamic behavior and its application to many subfields. Network science is both theory and application.

2. The history of network science is divided into three periods: (1) early pre- network period (1736–1966), when network science was really the mathematics of graphs; (2) a meso–network period (1967–1998), when network science was not yet called “the new science of networks,” but in fact applications of networks were emerging from the research literature; and (3) the modern period (1998–present), when the pioneers of the current definition of network science set forth the fundamentals and showed that the fundamentals had meaning in the real world.

3. The key concepts or principles of network science are (at least) structure, dynamism, bottom–up evolution, autonomy, topology, power, stability, and emergence. Each of these are explained in detail in this chapter.

4. We give a new perspective on network science that links emergence of network s...

Table of contents

• Cover
• Title page
• Copyright page
• Preface/Foreword
• 1 Origins
• 2 Graphs
• 3 Regular Networks
• 4 Random Networks
• 5 Small-World Networks
• 6 Scale-Free Networks
• 7 Emergence
• 8 Epidemics
• 9 Synchrony
• 10 Influence Networks
• 11 Vulnerability
• 12 NetGain
• 13 Biology
• Bibliography
• About the Author
• Index