viii
Contents
5
Modelling asymmetric relationships
41
5.1
Conventional directed spectral graph embedding . . . . . . . . 41
5.2
Directed edge layered approach . . . . . . . . . . . . . . . . . 44
5.2.1
Validation of the new directed embedding . . . . . 46
5.2.2
SVD computation for the directed edge model
approach . . . . . . . . . . . . . . . . . . . . . . 47
5.3
Applications of directed networks . . . . . . . . . . . . . . . . 48
5.4
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6
Modelling asymmetric relationships with multiple types
69
6.1
Combining directed and typed embeddings . . . . . . . . . . . 69
6.2
Layered approach and compositions . . . . . . . . . . . . . . 70
6.3
Applying directed typed embeddings . . . . . . . . . . . . . . 72
6.3.1
Florentine families . . . . . . . . . . . . . . . . . 72
6.3.2
Criminal groups . . . . . . . . . . . . . . . . . . 74
6.4
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7
Modelling relationships that change over time
81
7.1
Temporal networks . . . . . . . . . . . . . . . . . . . . . . . 81
7.2
Applications of temporal networks . . . . . . . . . . . . . . . 85
7.2.1
The undirected network over time . . . . . . . . . 85
7.2.2
The directed network over time . . . . . . . . . . 89
7.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8
Modelling positive and negative relationships
97
8.1
Signed Laplacian . . . . . . . . . . . . . . . . . . . . . . . . 97
8.2
Unnormalized spectral Laplacians of signed graphs . . . . . . 98
8.2.1
Rayleigh quotients of signed unnormalized
Laplacians . . . . . . . . . . . . . . . . . . . . . 99
8.2.2
Graph cuts of signed unnormalized Laplacians . . 100
8.3
Normalized spectral Laplacians of signed graphs . . . . . . . . 102
8.3.1
Rayleigh quotients of signed random-walk
Laplacians . . . . . . . . . . . . . . . . . . . . . 102
8.3.2
Graph cuts of signed random-walk Laplacians . . 104
8.4
Applications of signed networks . . . . . . . . . . . . . . . . 105
8.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9
Signed graph-based semi-supervised learning
121
9.1
Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
9.2
Problems of imbalance in graph data . . . . . . . . . . . . . . 127
9.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
10 Combining directed and signed embeddings
139
10.1
Composition of directed and signed layer models . . . . . . . . 139
10.2
Application to signed directed networks . . . . . . . . . . . . 142
10.2.1
North and West Africa conflict . . . . . . . . . . 143