CONTENTS

Preface/Foreword

1 Origins

1.1 What Is Network Science?

1.2 A Brief History of Network Science

1.3 General Principles

2 Graphs

2.1 Set-Theoretic Definition of a Graph

2.2 Matrix Algebra Definition of a Graph

2.3 The Bridges of Königsberg Graph

2.4 Spectral Properties of Graphs

2.5 Types of Graphs

2.6 Topological Structure

2.7 Graphs in Software

2.8 Exercises

3 Regular Networks

3.1 Diameter, Centrality, and Average Path Length

3.2 Binary Tree Network

3.3 Toroidal Network

3.4 Hypercube Networks

3.5 Exercises

4 Random Networks

4.1 Generation of Random Networks

4.2 Degree Distribution of Random Networks

4.3 Entropy of Random Networks

4.4 Properties of Random Networks

4.5 Weak Ties in Random Networks

4.6 Randomization of Regular Networks

4.7 Analysis

4.8 Exercises

5 Small-World Networks

5.1 Generating a Small-World Network

5.2 Properties of Small-World Networks

5.3 Phase Transition

5.4 Navigating Small Worlds

5.5 Weak Ties in Small-World Networks

5.6 Analysis

5.7 Exercises

6 Scale-Free Networks

6.1 Generating a Scale-Free Network

6.2 Properties of Scale-Free Networks

6.4 Analysis

6.5 Exercises

7 Emergence

7.1 What is Network Emergence?

7.2 Emergence in the Sciences

7.3 Genetic Evolution

7.4 Designer Networks

7.5 Permutation Network Emergence

7.6 An Application of Emergence

7.7 Exercises

8 Epidemics

8.1 Epidemic Models

8.2 Persistent Epidemics in Networks

8.3 Network Epidemic Simulation Software

8.4 Countermeasures

8.5 Exercises

9 Synchrony

9.1 To Sync or Not to Sync

9.2 A Cricket Social Network

9.3 Kirchhoff Networks

9.4 Pointville Electric Power Grid

9.5 Exercises

10 Influence Networks

10.1 Anatomy of Buzz

10.2 Power in Social Networks

10.3 Conflict in I-Nets

10.4 Command Hierarchies

10.5 Emergent Power in I-Nets

10.6 Exercises

11 Vulnerability

11.1 Network Risk

11.2 Critical Node Analysis

11.3 Game Theory Considerations

11.4 The General Attacker-Defender Network Risk Problem

11.6 Stability Resilience in Kirchhoff Networks

11.7 Exercises

12 NetGain

12.1 Classical Diffusion Equations

12.2 Multiproduct Networks

12.3 Java Method for Netgain Emergence

12.4 Nascent Market Networks

12.5 Creative Destruction Networks

12.6 Merger and Acquisition Networks

12.7 Exercises

13 Biology

13.1 Static Models

13.2 Dynamic Analysis

13.3 Protein Expression Networks

13.4 Mass Kinetics Modeling

13.5 Exercises

Bibliography

Index

PREFACE/FOREWORD

The phrase “network science” may be premature, as I write this foreword, because it may be too early to declare the combination of graph theory, control theory, and cross-discipline applications a “science.” Indeed, many of my colleagues have presented strong arguments to the contrary—declaring network science a fad—or even worse—a fabrication. So it was with trepidation that in 2006 I began writing a series of essays on various aspects of scale-free networks, small worlds, and networks that self-synchronize. These rough ideas expressed by this series evolved into the book that you are now holding in your hand. Like most first attempts, it is not without flaws. Yet, writing this book was a labor of love and—hopefully—it will become a useful resource for the unbiased, inquiring mind. Maybe it will establish the new science of networks as a subject taught in nearly every science, engineering, medical, and social science field of study.

Only time will tell whether this first attempt to compile what we know about the new science of networks into a single volume misses the mark or succeeds—and a textbook at that! But it has always been my weakness to write on topics that are slightly ahead of their time. The risk here lies in the selection of topics that I have chosen to call network science. Clearly, one has to include the work of pioneers such as Adamic, Albert, Barabasi, Barrat, Bollobas, Erdos, Granovetter, Kephart, Lin, Liu, Mihail, Milgram, Molloy, Moore, Newman, Pastor-Satorras, Renyi, Strogatz, Tadic, Wang, Watts, Weigt, White, Zhang, and Zhu. I have done so in the first 6 of 13 chapters. These chapters develop the field from its graph theory roots, to the modern definition of a network. Entire chapters are devoted to the most famous classes: regular, random, scale-free, and small-world networks. So, the first half of this book traces the development of network science along a trail blazed by the inventors. But then what?

My second objective was to add to what is known and published by the pioneers. The risk here lies in being pretentious—presuming to know what direction this new field might take. Once again, I relied on my weakness for being presumptuous— inquisitively so. Chapter 7, “Emergence,” introduces new self-organizing principles for networks and shows how to custom-design networks of arbitrary degree sequence distribution; Chapter 8, “Epidemics,” extends the elegant work of Z. Wang, Chakrabarti, C. Wang, and Faloutsos, to the exciting new endeavor of designing antigen countermeasures for the Internet. This work can be used to explain human epidemics as well as epidemics that sweep across the Internet. Chapter 9, “Synchrony,” pushes the early work of Watts to new levels—claiming that network synchronization is merely a special case of linear system stability. Simple eigenvalue tools can be used to determine the stability and synchrony of almost any linear network. Chapter 10, “Influence Networks,” is mostly new material and suggests what conditions must be met in order for a social network to come to consensus. As it turns out, it is not easy for groups to agree! Chapter 11, “Vulnerability,” builds on the PhD dissertation of Waleed Al-Mannai, who formalized and extended my own work on network risk. Al Mannai’s theory is being used on a daily basis to evaluate critical infrastructure systems and protect them against natural and synthetic (anthropogenic, humanmade) attacks. This has made a profound impression on the practice of homeland security. Chapter 12, “Netgain,” is an exploration of business models—relating the famous Schumpeter creative destruction process to an emergent process, and mapping the Bass and Fisher–Pry equations onto networks. It is comforting to verify the Bass–Fisher–Pry equations for networks, but furthermore, I show how these classical models may be extended to multi-product markets and oligopolies. Finally, Chapter 13, “Biology,” is completely on the leading edge of network science. This final chapter introduces the reader to the exciting new field of protein expression networks and suggests some new directions for the reader to consider.

The casual reader may easily skip over the mathematics, and still glean much from the application of networks to various disciplines ranging from computer science and engineering, business, public health (epidemiology), Internet virus countermeasures, social network behavior, biology, and physics. The more dedicated reader and classroom instructor may want to experiment with the software tools provided by the publisher and author (tedglewis@friction-free-economy.com). These include 5 major Java applications: Network.jar for exploring various classes of networks and experimenting with various emergence processes; Influence.jar for the study of influence networks and social network analysis; NetworkAnalysis.jar for the study of network vulnerability and the attacker-defender network risk problem; NetGain.jar for business modeling; and BioNet.jar for biological networks—especially protein expression networks. Both executable and source code are available as open source software. If you intend to deliver this material as an instructor in a college-level course, you will want to download the instructor’s manual from the publisher’s web site.

This book is a start, but it also leaves many questions unanswered. I hope that it will inspire a new generation of investigators and investigations. If I am right, the

phrase “network science” will not be controversial in another 10 years. But then, this is left as an exercise for the reader!

I want to thank Steve Lieberman for his diligent equation typesetting and careful reading of several drafts; also, Rudy Darken, and Tom Mackin, who contributed to my thought process and helped correct several of my ill-conceived ideas. Waleed Al Mannai had a major impact on Chapter 11, and also indirectly on the whole book. It was a pleasure working with these colleagues over 3 years of writing.

TED G. LEWIS

March 22, 2008