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.3 Navigation in 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.5 Critical Link Analysis
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
About the Author
Index
Copyright © 2009 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Lewis, T. G. (Theodore Gyle), 1941-
Network science : theory and practice / Ted G. Lewis.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-470-33188-0 (cloth)
1. Network analysis (Planning) I. Title.
T57.85.L49 2008
003′ .72--dc22
2008047060
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