Contents
1 Introduction and Overview ...................................... 1
1.1 Why Networks? ............................................ 1
1.2 Examples of Networks . . .................................... 3
1.2.1 Technological Networks . ............................. 3
1.2.2 Social Networks . .................................... 5
1.2.3 Biological Networks . . . . ............................. 7
1.2.4 Information Networks . . . ............................. 9
1.3 About this Book . . . ........................................ 11
2 Preliminaries .................................................. 15
2.1 Background on Graphs . . .................................... 15
2.1.1 Basic Definitions and Concepts . . ...................... 16
2.1.2 Families of Graphs . . . . . . ............................. 18
2.1.3 Graphs and Matrix Algebra . . . . . . ...................... 20
2.1.4 Graph Data Structures and Algorithms .................. 21
2.2 Background in Probability and Statistics . ...................... 24
2.2.1 Probability . . ........................................ 25
2.2.2 Principles of Statistical Inference . ...................... 31
2.2.3 Methods of Statistical Inference: Tutorials . . . . ........... 32
2.3 Statistical Analysis of Network Data: Prelude ................... 42
2.4 Additional Related Topics and Reading . . ...................... 45
Exercises . . . ................................................... 45
3 Mapping Networks ............................................. 49
3.1 Introduction ............................................... 49
3.2 Collecting Relational Network Data . . . . . ...................... 50
3.2.1 Measurement of System Elements and Interactions . ....... 51
3.2.2 Enumerated, Partial, and Sampled Data . . . . . . . ........... 54
3.3 Constructing Network Graph Representations . .................. 56
3.4 Visualizing Network Graphs . . . . ............................. 58
3.4.1 Elements of Graph Visualization . ...................... 58
ix