Contents
Preface
xi
List of Figures
xiii
List of Tables
xvii
Glossary
xix
1
Introduction
1
1.1
What is a social network? . . . . . . . . . . . . . . . . . . . .
1
1.2
Multiple aspects of relationships . . . . . . . . . . . . . . . .
6
1.3
Formally representing social networks . . . . . . . . . . . . .
7
2
The core model
9
2.1
Representing networks to understand their structures . . . . . .
9
2.2
Building layered models . . . . . . . . . . . . . . . . . . . . . 11
2.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3
Background
17
3.1
Graph theory background . . . . . . . . . . . . . . . . . . . . 17
3.2
Spectral graph theory . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1
The unnormalized graph Laplacian . . . . . . . . 21
3.2.2
The normalized graph Laplacians . . . . . . . . . 23
3.3
Spectral pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4
Spectral approaches to clustering . . . . . . . . . . . . . . . . 24
3.4.1
Undirected spectral clustering algorithms . . . . . 26
3.4.2
Which Laplacian clustering should be used? . . . 27
3.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4
Modelling relationships of different types
31
4.1
Typed edge model approach . . . . . . . . . . . . . . . . . . . 32
4.2
Typed edge spectral embedding . . . . . . . . . . . . . . . . . 32
4.3
Applications of typed networks . . . . . . . . . . . . . . . . . 34
4.4
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
vii