Network Science: Theory And Applications

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.

T. G. Lewis is Professor of Computer Science at the Naval Postgraduate School, Monterey, CA. He has written over thirty books during the course of his extensive career. Dr. Lewis is the former vice president of development for Eastman Kodak.

"This book provides a comprehensive study of network science, specifically of different network classes and their respective properties. The chapters are easy to understand, each containing an extensive introduction that prepares the reader for what is to follow." (Computing Reviews, 1 November 2010)
“This fascinating book is a tour de force review of the application of network theory to a number of real-life and wildly different areas.” (Computing Reviews, July 2009)

1. ORIGINS.
1.1 What is Network Science?.
1.2 A Brief History of Network Science.
1.2.1 The Pre-Network Period (1736-1966).
1.2.2 The Meso-Network Period (1967-1998).
1.2.3. The Modern Period (1998-present).
1.3 General Principles.
2. GRAPHS.
2.1 Set Theoretical Definition of a Graph.
2.1.1 Nodes, Links, and Mapping Function.
2.1.2 Node Degree and Hubs.
2.1.3 Paths and Circuits.
2.1.4 Connectedness and Components.
2.1.5 Diameter, Radius, and Centrality.
2.1.6 Betweeness and Closeness.
2.2 Matrix Algebra Definition of a Graph.
2.2.1 Connection Matrix.
2.2.2 Adjacency Matrix.
2.2.3 Laplacian Matrix.
2.2.4 Path Matrix.
2.3.1 Euler Path, Euler Circuit.
2.3.2 Formal Definition of the Bridges of K?nigsberg.
2.3.3 Euler’s Solution.
2.4 Spectral Properties of Graphs.
2.4.1 Spectral Radius.
2.4.2 Spectral Gap.
2.5 Types of Graphs.
2.5.1 Barbell, Line, and Ring Graphs.
2.5.2 Structured vs. Random Graphs.
2.5.3. k-Regular Graphs.
2.5.4 Graph Density.
2.6 Topological Structure.
2.6.1 Degree Sequence.
2.6.2 Graph Entropy.
2.6.3 Scale-Free Topology.
2.6.4 Small World Topology.
2.7 Graphs in Software.
2.7.1 Java Nodes and Links.
2.7.2 Java Networks.
2.8. Exercises.
3. REGULAR NETWORKS.
3.1 Diameter, Centrality, and Average Path Length.
3.1.1 Calculating Path Length and Centrality.
3.2 Binary Tree Network.
3.2.1 Entropy of Binary Tree Network.
3.2.2 Path Length of Binary Tree Network.
3.2.3 Link Efficiency of Binary Tree Network.
3.3 Toroidal Network.
3.3.1 Average Path Length of Toroidal Networks.
3.3.2 Link Efficiency of Toroidal Networks.
3.4 Hypercube Networks.
3.4.1 Average Path Length of Hypercube Networks.
3.4.2 Link Efficiency of Hypercube Networks.
3.5 Exercises.
4. RANDOM NETWORKS.
4.1 Generation of Random Networks.
4.1.1 Gilbert Random Network.
4.1.2 Erdos-Renyi (ER) Random Network.
4.1.3 Anchored Random Network.
4.2 Degree Distribution of Random Networks.
4.3 Entropy of Random Networks.
4.3.1 Model of Random Network Entropy.
4.3.2 Average Path Length of Random Networks.
4.3.3 Cluster Coefficient of Random Networks.
4.3.4 Link Efficiency of Random Networks.
4.4 Diameter, Centrality, and Closeness in Random Networks.
4.4.1 Diameter of Random Networks.
4.4.2 Radius of Random Networks.
4.4.3. Closeness Calculation in Java.
4.4.4 Closeness in 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.1.1 The Watts-Strogatz Procedure.
5.1.2 Generalized WS Procedure.
5.1.3 Degree Sequence of Small World Networks.
5.2 Properties of Small World Networks.
5.2.1. Entropy vs. Rewiring Probability.
5.2.2 Entropy vs. Density.
5.2.3 Path Length of Small World Networks.
5.2.4 Cluster Coefficient of Small World Networks.
5.2.5 Closeness in Small Worlds.
5.3 Phase Transition.
5.3.1 Path Length and Phase Transition.
5.3.2 Phase Transition in Materials.
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.1.1 The Barabasi-Albert (BA) Network.
6.1.2 Generating BA Networks.
6.1.3 Scale-Free Network Power Law.
6.2 Properties of Scale-Free Networks.
6.2.1 BA Network Entropy.
6.2.2 Hub Degree versus Density.
6.2.3 BA Network Average Path Length.
6.2.4 BA Network Closeness.
6.2.5 Scale-free Network Cluster Coefficient.
6.3 Navigation in Scale-Free Networks.
6.3.1 Max-degree Navigation versus Density.
6.3.2 Max-degree Navigation versus Hub Degree.
6.3.3 Weak Ties in Scale-Free Pointville.
6.4 Analysis.
6.4.1 Entropy.
6.4.2 Path Length and Communication.
6.4.3 Cluster Coefficient.
6.4.4 Hub Degree.
6.5 Exercises.
7. EMERGENCE.
7.1 What is Network Emergence?.
7.1.1 Open Loop Emergence.
7.1.2 Feedback Loop Emergence.
7.2 Emergence in the Sciences.
7.2.1 Emergence in Social Science.
7.2.2 Emergence in Physical Science.
7.2.2 Emergence in Biology.
7.3 Genetic Evolution.
7.3.1 Hub Emergence.
7.3.2 Cluster Emergence.
7.4 Designer Networks.
7.4.1 Degree Sequence Emergence.
7.4.2 Generating Networks with Given Degree Sequence.
7.5 Permutation Network Emergence.
7.5.1 Permutation Micro-Rule.
7.5.2 Permutation and Cluster Coefficient.
7.6 An Application of Emergence.
7.6.1 Link Optimization by Random Permutation.
7.6.2 Optimization by Deterministic Permutation.
7.6.3 Model of Minimum Length Emergence.
7.6.4 Two-Dimensional Layouts.
7.7 Exercises.
8. EPIDEMICS.
8.1. Epidemic Models.
8.1.2 The Kermack-McKendrick Model.
8.1.3 Epidemic Thresholds.
8.1.4 SIR.
8.1.5 Peak Infection Density in Structured Networks.
8.1.6 SIS Epidemics.
8.2 Persistent Epidemics in Networks.
8.2.1 Random Network Epidemic Threshold.
8.2.2 Epidemic Threshold in General Networks.
8.2.3 Fixed-point Infection Density in General Networks.
8.3 Network Epidemic Simulation Software.
8.4 Countermeasures.
8.4.1 Countermeasure Algorithms.
8.4.2 Countermeasure Seeding Strategies.
8.4.3 Antigen Simulation in Java.
8.5 Exercises.
9. SYNCHRONY.
9.1 To Sync or Not To Sync.
9.1.1 Chaotic Maps.
9.1.2 Network Stability.
9.1.2.1 Lyapunov Method.
9.1.2.2 Spectral Decomposition.
9.2 A Cricket Social Network.
9.2.1 Sync Property of the Cricket Social Network.
9.2.2 A More General Model: Atay Networks.
9.2.3 Stability of Atay Networks.
9.3 Kirchhoff Networks.
9.3.1 Kirchhoff Network Model.
9.3.2 Kirchhoff Network Stability.
9.4 Anatomy of Buzz.
9.4.1 A Buzz Network.
9.4.2 Buzz Network Simulator.
9.4.3 Buzz Network Stability.
9.5 Exercises.
10. INFLUENCE NETWORKS.
10.1 Anatomy of Buzz.
10.1.1 A Buzz Network.
10.1.2 Buzz Network Simulator.
10.1.3 Buzz Network Stability.
10.2 Power in Social Networks.
10.2.1 Two-Party Negotiation.
10.2.2 I-net State Equation.
10.2.3 I-net Stability.
10.2.4 I-net Consensus.
10.2.5 Java Methods for Computing Influence.
10.3 Conflict in I-nets.
10.3.1 Degree of Conflict.
10.3.2 Java Method to Compute Degree of Conflict.
10.4 Command Hierarchies.
10.5 Emergent Power in I-nets.
10.5.1 Weight Emergence.
10.5.2 Java Method for Weight Emergence.
10.5.3 Stability of Weight Emergence.
10.5.4 Link Emergence.
10.6 Exercises.
11. VULNERABILITY.
11.1 Network Risk.
11.1.1 Nodes as Targets.
11.1.2 Links as Targets.
11.2 Critical Node Analysis.
11.2.1 The Barbell Model.
11.2.2 Minimizing Network Risk.
11.2.2.1 The Linear Cost Model.
11.2.3 The Exponential Cost Model.
11.2.4 The Attacker-Defender Model.
11.2.4 Java Arms Race Methods.
11.3 Game Theory Considerations.
11.4 The General Attacker-Defender Network Risk Problem.
11.5 Critical Link Analysis.
11.5.1 Link Resilience.
11.5.2 Model of Link Resilience.
11.5.3 Flow Resilience.
11.5.4 Java Methods for Flow Heuristic.
Table 11.4 Allocation of Resources via Flow Analysis.
11.5.5 Network Flow Resource Allocation.
11.5.6 Maximum Flow in Structured Networks.
11.6 Stability Resilience in Kirchhoff Networks.
11.6 Exercises.
12. NETGAIN.
12.1 Classical Diffusion Equations.
12.1.1 Market Diffusion Equations.
12.1.2 Simple Netgain Networks.
12.2 Multi-Product Networks.
12.3 Java Method for Netgain Emergence.
12.4 Nascent Market Networks.
12.4.1 Nascent Market Emergence.
12.4.2 The Nascent Market Fixed Point.
12.5 Creative Destruction Networks.
12.5.1 Creative Destruction Emergence.
12.5.2 The Square-Root Law Fixed Point.
12.6 Merger & Acquisition Networks.
12.6.1 Java Method for Merging Nodes.
12.6.2 Merging Speeds Up Creative Destruction.
12.7 Exercises.
13. BIOLOGY.
13.1 Static Models.
13.1.1 Scale-free Property.
13.1.2 Small World Effects.
13.2 Dynamic Analysis.
13.2.1 Linear Continuous Networks.
13.2.2 Boolean Networks.
13.3 Protein Expression Networks.
13.3.1 Emergence of Biological Networks.
13.4 Mass Kinetics Modeling.
13.4.1 Mass Kinetic State Equations.
13.4.2 Bounded Mass Kinetic Networks.
13.5 Exercises.