Foreword |
|
xi | |
|
Introduction |
|
xv | |
|
|
1 | (14) |
|
1.1 The Seven Bridges of Konigsberg |
|
|
1 | (3) |
|
1.2 Graphs as mathematical models |
|
|
4 | (2) |
|
1.3 Graph theory in the analysis of people and groups |
|
|
6 | (5) |
|
1.3.1 The study of connection |
|
|
6 | (1) |
|
1.3.2 The study of information flow |
|
|
7 | (1) |
|
1.3.3 The study of community, diversity and familiarity |
|
|
8 | (1) |
|
1.3.4 The study of importance, influence and attachment |
|
|
9 | (1) |
|
1.3.5 Graphs as data sources |
|
|
10 | (1) |
|
1.4 Purpose, structure and organization of this book |
|
|
11 | (4) |
|
|
15 | (28) |
|
2.1 Elementary graph theory |
|
|
15 | (13) |
|
2.1.1 General definition of a graph |
|
|
16 | (2) |
|
|
18 | (5) |
|
2.1.3 Vertex and edge properties |
|
|
23 | (2) |
|
2.1.4 Representations of graphs |
|
|
25 | (3) |
|
|
28 | (8) |
|
2.2.1 Creating a graph from an edgelist |
|
|
28 | (2) |
|
2.2.2 Creating a graph from an adjacency matrix |
|
|
30 | (1) |
|
2.2.3 Creating a graph from a dataframe |
|
|
31 | (2) |
|
2.2.4 Adding properties to the vertices and edges |
|
|
33 | (3) |
|
2.3 Creating graphs in Python |
|
|
36 | (5) |
|
2.3.1 Creating a graph from an edgelist |
|
|
36 | (2) |
|
2.3.2 Creating a graph from an adjacency matrix |
|
|
38 | (1) |
|
2.3.3 Adding vertex and edge properties to a graph |
|
|
39 | (2) |
|
|
41 | (2) |
|
2.4.1 Discussion questions |
|
|
41 | (1) |
|
|
42 | (1) |
|
|
43 | (40) |
|
3.1 Visualizing graphs in R |
|
|
44 | (30) |
|
3.1.1 Native plotting in igraph |
|
|
45 | (5) |
|
|
50 | (7) |
|
3.1.3 Static plotting with ggraph |
|
|
57 | (9) |
|
3.1.4 Interactive graph visualization using visNetwork |
|
|
66 | (3) |
|
3.1.5 Interactive graph visualization using networkD3 |
|
|
69 | (5) |
|
3.2 Visualizing graphs in Python |
|
|
74 | (6) |
|
3.2.1 Static plotting using networkx and matplotlib |
|
|
74 | (3) |
|
3.2.2 Interactive visualization using networkx and pyvis |
|
|
77 | (3) |
|
|
80 | (3) |
|
3.3.1 Discussion questions |
|
|
80 | (1) |
|
|
81 | (2) |
|
4 Restructuring Data for Use in Graphs |
|
|
83 | (36) |
|
4.1 Transforming data in rectangular tables for use in graphs |
|
|
84 | (18) |
|
4.1.1 Creating a simple graph of a management hierarchy |
|
|
85 | (2) |
|
4.1.2 Connecting customers through sales reps |
|
|
87 | (5) |
|
4.1.3 Connecting customers through common purchases |
|
|
92 | (5) |
|
4.1.4 Approaches using Python |
|
|
97 | (5) |
|
4.2 Transforming data from documents for use in graphs |
|
|
102 | (14) |
|
4.2.1 Scraping data from semi-structured documents |
|
|
103 | (4) |
|
4.2.2 Creating an edgelist from the scraped data |
|
|
107 | (3) |
|
4.2.3 Approaches in Python |
|
|
110 | (6) |
|
|
116 | (3) |
|
4.3.1 Discussion questions |
|
|
116 | (1) |
|
|
117 | (2) |
|
|
119 | (28) |
|
5.1 Theory of graph traversal, paths and distance |
|
|
120 | (9) |
|
5.1.1 Paths and graph traversal |
|
|
120 | (3) |
|
5.1.2 Path length and distance |
|
|
123 | (2) |
|
5.1.3 Shortest path algorithms |
|
|
125 | (2) |
|
5.1.4 Graph diameter and density |
|
|
127 | (2) |
|
5.2 Calculating paths, distance, diameter and density |
|
|
129 | (7) |
|
|
129 | (5) |
|
5.2.2 Calculating in Python |
|
|
134 | (2) |
|
|
136 | (9) |
|
5.3.1 Facilitating introductions in a workplace |
|
|
137 | (2) |
|
5.3.2 Finding distant colleagues in a workplace |
|
|
139 | (6) |
|
|
145 | (2) |
|
5.4.1 Discussion questions |
|
|
145 | (1) |
|
|
145 | (2) |
|
6 Vertex Importance and Centrality |
|
|
147 | (22) |
|
6.1 Vertex centrality measures in graphs |
|
|
148 | (4) |
|
|
149 | (1) |
|
6.1.2 Closeness centrality |
|
|
149 | (1) |
|
6.1.3 Betweenness centrality |
|
|
150 | (1) |
|
6.1.4 Eigenvector centrality |
|
|
151 | (1) |
|
6.2 Calculating and illustrating vertex centrality |
|
|
152 | (7) |
|
|
152 | (2) |
|
6.2.2 Calculating in Python |
|
|
154 | (3) |
|
6.2.3 Illustrating centrality in graph visualizations |
|
|
157 | (2) |
|
|
159 | (7) |
|
6.3.1 Finding `superconnectors' |
|
|
159 | (4) |
|
6.3.2 Identifying influential employees |
|
|
163 | (3) |
|
|
166 | (3) |
|
6.4.1 Discussion questions |
|
|
166 | (1) |
|
|
166 | (3) |
|
7 Components, Communities and Cliques |
|
|
169 | (32) |
|
7.1 Theory of components, partitions and clusters |
|
|
170 | (5) |
|
7.1.1 Connected components of graphs |
|
|
170 | (2) |
|
7.1.2 Vertex partitioning |
|
|
172 | (1) |
|
7.1.3 Vertex clustering and community detection |
|
|
173 | (1) |
|
|
174 | (1) |
|
7.2 Finding components, communities and cliques using R |
|
|
175 | (7) |
|
7.2.1 Finding connected components of disconnected graphs |
|
|
175 | (3) |
|
7.2.2 Partitioning and community detection in R |
|
|
178 | (3) |
|
7.2.3 Finding cliques in R |
|
|
181 | (1) |
|
7.3 Finding components, communities and cliques using Python |
|
|
182 | (6) |
|
7.3.1 Finding connected components using Python |
|
|
182 | (1) |
|
7.3.2 Partitioning and community detection using Python |
|
|
183 | (4) |
|
7.3.3 Finding cliques in Python |
|
|
187 | (1) |
|
|
188 | (9) |
|
7.4.1 Detecting communities and cliques among Facebook friends |
|
|
188 | (5) |
|
7.4.2 Detecting politically aligned communities on Twitter |
|
|
193 | (4) |
|
|
197 | (4) |
|
7.5.1 Discussion questions |
|
|
197 | (1) |
|
|
198 | (3) |
|
8 Assortativity and Similarity |
|
|
201 | (14) |
|
8.1 Assortativity in networks |
|
|
201 | (4) |
|
8.1.1 Categorical or nominal assortativity |
|
|
202 | (2) |
|
8.1.2 Degree assortativity |
|
|
204 | (1) |
|
|
205 | (3) |
|
|
208 | (1) |
|
8.4 Calculating assortativity and similarity in Python |
|
|
209 | (3) |
|
|
212 | (3) |
|
8.5.1 Discussion questions |
|
|
212 | (1) |
|
|
213 | (2) |
|
|
215 | (16) |
|
9.1 Graph database technology |
|
|
216 | (4) |
|
9.1.1 Labelled-property graphs |
|
|
216 | (2) |
|
9.1.2 Resource description frameworks |
|
|
218 | (2) |
|
9.2 Example: how to work with a Neo4J graph database |
|
|
220 | (8) |
|
9.2.1 Using the browser interface |
|
|
221 | (4) |
|
9.2.2 Working with Neo4J using R |
|
|
225 | (2) |
|
9.2.3 Working with Neo4J using Python |
|
|
227 | (1) |
|
9.3 Moving to persistent graph data in organizations |
|
|
228 | (1) |
|
|
229 | (2) |
|
9.4.1 Discussion questions |
|
|
229 | (1) |
|
|
229 | (2) |
|
10 Further Exercises for Practice |
|
|
231 | (8) |
|
10.1 Friendships among Scottish teenage girls |
|
|
231 | (2) |
|
10.2 Interactions between dolphins in Doubtful Sound, New Zealand |
|
|
233 | (1) |
|
10.3 Character interaction in Victor Hugo's novel Les Miserables |
|
|
233 | (1) |
|
10.4 Communication between criminals involved in a drug importation operation |
|
|
234 | (1) |
|
10.5 Academic collaboration between network scientists |
|
|
235 | (1) |
|
10.6 Other sources of data for practice |
|
|
236 | (3) |
References |
|
239 | (2) |
Glossary |
|
241 | (6) |
Index |
|
247 | |