Module 6CCMCS02/7CCMCS02
Theory of Complex Networks
Compact Lecture Notes
798
672
977
606 1 539
202
823
588
930 329
120
68 312
510
144 430 926 946 394
906 57
258
659 699 187
425
605
451 612 988 688
860
629
383
386 842
594 679
306 301 719
180
117 192
735 891 251
496 761 56 361
972 872 300 746
432 309
43 712
462 670
838 899
437 472
897 111 281 87
46 691 883
890 412 470 232
30
622 868 997
827 948 175 968
596 488 759 366
706 566 749 960 886
453
664 962 919 878
935 152
851 324 789 516
685 19
316 223 873443 34 315
138 520 435646 266
252 235 649 711 517
83 903 933 139 846 969 724
762 797 263
297 785 467
49 427
254 748 351
914
865 773 271 597
414
105 219 951
779 194 805 970
159 807 647
179 610 352
888 143 415
754 150 959 741 804
487 922 729 777 945 814
546
177 330 864 651
713 359 21
308 155
953 48 221 166
887 840 514 683 106 422
31 955 799
319 989 967
570 979
94 191
269 645 981 637 334 186
491 421 454 917 591
796 905 782
806 658 340
613
404 525 973
896 717 726 74
908 336 124 923
188 17 705 829
54 207 122 907 755
671 465
682 787 833
298 565 701 58 976
267
966 413 676
376 937 357 198
551 375 916 129
484 22 326
971
292
702 615 898 677 920
964 924 408 495
581 769
656 881 821 574
475 556 695
661
60 730 680
480 557 478 912 483 205
325 763 956 249
189 770 673
742
53
178 562 904 751
540
463
505 247 687 206
812
608 947 185 311 665
439 396 893
541
140 616 110
163885 515 776
199 599
857 884 784
373 716 374
602
371
745 245 213
547 875
125 550 932 509 825
497 795 372
617 320
928 93 625 228
843 534 134 674 335
304 131
542 828 295
468 165
950 728
808 368
406
279 27
9 400
201
996 618 184 631
874 583
367 723
70
580 337 339
739 362 663 399
264 248
98 604 630
95 990 328
901 402
241 75
469 346 837
211 858 499 792
15 513 869 548 59 236
302 810
240 576 826
975 867 473
809
628
343 983
944 482 703
433 174 895 498
786 552 693 648 781 32 911
13 667 429
740
980 555 486
62 527 714 460
277 569 519
445 927 154 642
530 365 181 401
653 419 508 291 272 985
715 913 317
803 112
182 758 852 882 643
265 322 952 771 169 609
464 528 10
476 338 100
38 848 364
44 627 378 811
6
614 635
348 925
363 780 471
294 353 590
135
536 733
727 994
78 126 377 403 931
16 287 76 747
839 793 696
289 176 800 456
299 831 554 987 506
310 764
501 20 288 866
392 426 47
190 449 636 333 650
718 720
704 280 563
900 261 442 652 492 545
293 707 611 193 936 543
732 35 578 167 153
601 85 915 170 879 489 160
388 522
791 305 395 587
963
11
420 356 861 560 466
350 941 358 760 708 255
666
634 532 417 568
197 986 621 149
709 398 148 641
841 91 765
405 162 579
815 586 561
256 567
832 813 222
341 459
778 250 849
239 103 998 101
44061 409 118 285
217 452 698 984
360 553 381
801
303 918
234 296 675 870
92 86
481524 63 854 518
196 744
638 438 662
71 342 114
689
80 640
743 323 526 598 173
90 824
512 626
238 686 278 89
259 974 273 783 644
500 284
957 136
995 276 257 575 37 229
42 102 55 531 921 737 544
571 909 130
835 200 385
736 529
485 455 12 158 390 347 954
592 282 816 564 790 332
318 133 584 286 369
195
632 535 79 183 25
208 260 39 750
397 243 107
507 725
834 142
321 847 132 623 387 766
768 410 880
147 242
283 244 942 992 2
474 845
853 600 127 830 210 391 146 493
461 104 444 418
220
504 447 99 436
327 477
820 7 313 84 458
836 67 314
354
690 227 119 66 151 934
734 64 108 752 654
441 949 965 157
82 5 40 41 214
775 929
850
274 26 731 77
502 619 137 982 511 14
123 660 978 1000
231 558 156 33
355 331 537 721 772
844 237
767 822
490 262 45 991 577 428 141 993 503
999 756
36 855757
203 894669
958 69 700 607
29 692 121
856 172
96 407
216 344 910 523 268
389 697 876
225
585 657
889 161 97
233 307
204 28 678
171
88 212 446 450
681 589 559
4 684
961 224
788 51 349
128 694 494
226 862 633
424
859 794 818
892 738 379
145 549
722 50
246
940 411
3 573 47918
871 270 116 603
655
109
52 168
215 115
582
290 538
380
817 275 593
81 521
943 802 423
164
620 73
345
533 939
863
595 668
572 382
639
253384 113
624 431
370
ACC Coolen
I Neri
Department of Mathematics
King’s College London
, 2
1 Introduction 4
2 Definitions and notation 15
2.1 Networks or graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The adjacency matrix of a network . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Paths in networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Graphs within graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Connected components in nondirected and directed graphs . . . . . . . . . . 21
2.5.1 Nondirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.2 Directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Microscopic structural characteristics of graphs 25
3.1 Node degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Neighbourhood sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Clustering coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Graph distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Node centrality: a path based approach . . . . . . . . . . . . . . . . . . . . . 29
3.6 Eigenvector centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.7 Node similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Macroscopic structural characteristics of graphs 35
4.1 Mean values of single-node features . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Distributions of single node quantities . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Distributions of multi-node quantities . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Degree correlations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5 Generalisation to node features other than degrees . . . . . . . . . . . . . . . 45
4.6 Modularity and community detection . . . . . . . . . . . . . . . . . . . . . . 47
5 Processes on networks and their relation to spectral features 50
5.1 Voter models on networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Stability of fixed points in the nonlinear voter model [Not examinable] . . 54
5.3 Diffusion processes: - the Laplacian matrix of a graph . . . . . . . . . . . . . 55
5.4 Random walks on networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6 Spectra of adjacency matrices of undirected graphs . . . . . . . . . . . . . . 58
5.7 Spectra of Laplacian matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 63
, 3
6 Random graphs 67
6.1 Random graphs as ‘null models’ . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 The Erdős-Rènyi model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.4 The Erdős-Renyi model in the finite connectivity regime . . . . . . . . . . . 75
6.5 Random graphs with a given prescribed degree distribution p(k) . . . . . . . 76
6.6 Percolation theory for random, locally tree-like graphs . . . . . . . . . . . . . 79
7 Appendices 89
7.1 Network software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.2 The Pearson correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.3 Properties of symmetric matrices . . . . . . . . . . . . . . . . . . . . . . . . 90
7.4 Integral representation of the Kronecker δ-symbol . . . . . . . . . . . . . . . 93
7.5 The Landau order symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.6 Perron-Frobenius theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8 Exercises 95
, 4
1. Introduction
The challenge of large data sets. In recent decades our ability to collect and store vast
amounts of quantitative data has increased dramatically. This includes socio-economic data,
such as social links between individuals or professional collaboration networks, consumer
preferences and commercial interactions, trade dependencies among corporations, credit
or insurance obligations between financial institutions. We have access to traffic data on
computer and telecommunication systems, satellite networks, the internet, electricity grids,
rail, road or air travel connections and distribution networks. We collect and process large
amounts of geological and meteorological data, data on sea levels, air and water pollution,
volcanic and seismic records, and sizes of polar and glacier ice sheets. Finally, we have seen
an explosion in recent years of biomedical data, such as experimental data on biochemical
processes and structures at cellular, subcellular and even molecular levels, the topologies
of complex composite signalling and information processing systems such as the brain or
the immune system, genomic and epigenetic data (gene expression levels, DNA sequences),
epidemiological data, and vast numbers of patient records with clinical information.
However, one tends to collect data for a reason. This reason is usually the desire to
understand the dynamical behaviour of the complex system that generated the data, to
predict with reasonable accuracy its future evolution and its response to perturbations or
interventions, or to understand how it was formed. We may want this for commercial gain,
to improve and optimise a system’s efficiency, to design effective regulatory controls, or
(in the case of medicine) to understand and cure diseases. For small and simple systems
the translation of observation into qualitative and quantitative understanding of design
and function is usually not difficult. In contrast, if we collect data on complex systems
with millions of nonlinearly interacting variables, just having a list of the parts and their
connections and observations of their collective patterns of behaviour is no longer enough to
understand how these systems work.
Networks as data reduction and visualisation tools. A first and useful step in modelling
structural data on complex many-variable systems is to visualise these systems as networks
or graphs. The idea is to represent each observed system component as a node in the
network, and each observed interaction between two components as a link between the
two corresponding nodes. Dependent upon one’s research domain, the nodes of such
networks may represent anything ranging from genes, molecules, or proteins (in biology), via
processors or servers (in computer science), to people, airports, power plants or corporations
(in social science or economics). The links could refer to biochemical reactions, wired
or wireless communication channels, friendships, financial contracts, etc. The price paid
for the complexity reduction is the loss of information. Limiting ourselves to a network
representation means that we only record which parts interact, and disregard how and when
they interact. However, the rationale is that the topology of the interactions between a
Theory of Complex Networks
Compact Lecture Notes
798
672
977
606 1 539
202
823
588
930 329
120
68 312
510
144 430 926 946 394
906 57
258
659 699 187
425
605
451 612 988 688
860
629
383
386 842
594 679
306 301 719
180
117 192
735 891 251
496 761 56 361
972 872 300 746
432 309
43 712
462 670
838 899
437 472
897 111 281 87
46 691 883
890 412 470 232
30
622 868 997
827 948 175 968
596 488 759 366
706 566 749 960 886
453
664 962 919 878
935 152
851 324 789 516
685 19
316 223 873443 34 315
138 520 435646 266
252 235 649 711 517
83 903 933 139 846 969 724
762 797 263
297 785 467
49 427
254 748 351
914
865 773 271 597
414
105 219 951
779 194 805 970
159 807 647
179 610 352
888 143 415
754 150 959 741 804
487 922 729 777 945 814
546
177 330 864 651
713 359 21
308 155
953 48 221 166
887 840 514 683 106 422
31 955 799
319 989 967
570 979
94 191
269 645 981 637 334 186
491 421 454 917 591
796 905 782
806 658 340
613
404 525 973
896 717 726 74
908 336 124 923
188 17 705 829
54 207 122 907 755
671 465
682 787 833
298 565 701 58 976
267
966 413 676
376 937 357 198
551 375 916 129
484 22 326
971
292
702 615 898 677 920
964 924 408 495
581 769
656 881 821 574
475 556 695
661
60 730 680
480 557 478 912 483 205
325 763 956 249
189 770 673
742
53
178 562 904 751
540
463
505 247 687 206
812
608 947 185 311 665
439 396 893
541
140 616 110
163885 515 776
199 599
857 884 784
373 716 374
602
371
745 245 213
547 875
125 550 932 509 825
497 795 372
617 320
928 93 625 228
843 534 134 674 335
304 131
542 828 295
468 165
950 728
808 368
406
279 27
9 400
201
996 618 184 631
874 583
367 723
70
580 337 339
739 362 663 399
264 248
98 604 630
95 990 328
901 402
241 75
469 346 837
211 858 499 792
15 513 869 548 59 236
302 810
240 576 826
975 867 473
809
628
343 983
944 482 703
433 174 895 498
786 552 693 648 781 32 911
13 667 429
740
980 555 486
62 527 714 460
277 569 519
445 927 154 642
530 365 181 401
653 419 508 291 272 985
715 913 317
803 112
182 758 852 882 643
265 322 952 771 169 609
464 528 10
476 338 100
38 848 364
44 627 378 811
6
614 635
348 925
363 780 471
294 353 590
135
536 733
727 994
78 126 377 403 931
16 287 76 747
839 793 696
289 176 800 456
299 831 554 987 506
310 764
501 20 288 866
392 426 47
190 449 636 333 650
718 720
704 280 563
900 261 442 652 492 545
293 707 611 193 936 543
732 35 578 167 153
601 85 915 170 879 489 160
388 522
791 305 395 587
963
11
420 356 861 560 466
350 941 358 760 708 255
666
634 532 417 568
197 986 621 149
709 398 148 641
841 91 765
405 162 579
815 586 561
256 567
832 813 222
341 459
778 250 849
239 103 998 101
44061 409 118 285
217 452 698 984
360 553 381
801
303 918
234 296 675 870
92 86
481524 63 854 518
196 744
638 438 662
71 342 114
689
80 640
743 323 526 598 173
90 824
512 626
238 686 278 89
259 974 273 783 644
500 284
957 136
995 276 257 575 37 229
42 102 55 531 921 737 544
571 909 130
835 200 385
736 529
485 455 12 158 390 347 954
592 282 816 564 790 332
318 133 584 286 369
195
632 535 79 183 25
208 260 39 750
397 243 107
507 725
834 142
321 847 132 623 387 766
768 410 880
147 242
283 244 942 992 2
474 845
853 600 127 830 210 391 146 493
461 104 444 418
220
504 447 99 436
327 477
820 7 313 84 458
836 67 314
354
690 227 119 66 151 934
734 64 108 752 654
441 949 965 157
82 5 40 41 214
775 929
850
274 26 731 77
502 619 137 982 511 14
123 660 978 1000
231 558 156 33
355 331 537 721 772
844 237
767 822
490 262 45 991 577 428 141 993 503
999 756
36 855757
203 894669
958 69 700 607
29 692 121
856 172
96 407
216 344 910 523 268
389 697 876
225
585 657
889 161 97
233 307
204 28 678
171
88 212 446 450
681 589 559
4 684
961 224
788 51 349
128 694 494
226 862 633
424
859 794 818
892 738 379
145 549
722 50
246
940 411
3 573 47918
871 270 116 603
655
109
52 168
215 115
582
290 538
380
817 275 593
81 521
943 802 423
164
620 73
345
533 939
863
595 668
572 382
639
253384 113
624 431
370
ACC Coolen
I Neri
Department of Mathematics
King’s College London
, 2
1 Introduction 4
2 Definitions and notation 15
2.1 Networks or graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The adjacency matrix of a network . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Paths in networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Graphs within graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Connected components in nondirected and directed graphs . . . . . . . . . . 21
2.5.1 Nondirected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.2 Directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Microscopic structural characteristics of graphs 25
3.1 Node degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Neighbourhood sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Clustering coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Graph distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Node centrality: a path based approach . . . . . . . . . . . . . . . . . . . . . 29
3.6 Eigenvector centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.7 Node similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Macroscopic structural characteristics of graphs 35
4.1 Mean values of single-node features . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Distributions of single node quantities . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Distributions of multi-node quantities . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Degree correlations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5 Generalisation to node features other than degrees . . . . . . . . . . . . . . . 45
4.6 Modularity and community detection . . . . . . . . . . . . . . . . . . . . . . 47
5 Processes on networks and their relation to spectral features 50
5.1 Voter models on networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Stability of fixed points in the nonlinear voter model [Not examinable] . . 54
5.3 Diffusion processes: - the Laplacian matrix of a graph . . . . . . . . . . . . . 55
5.4 Random walks on networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6 Spectra of adjacency matrices of undirected graphs . . . . . . . . . . . . . . 58
5.7 Spectra of Laplacian matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 63
, 3
6 Random graphs 67
6.1 Random graphs as ‘null models’ . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 The Erdős-Rènyi model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.4 The Erdős-Renyi model in the finite connectivity regime . . . . . . . . . . . 75
6.5 Random graphs with a given prescribed degree distribution p(k) . . . . . . . 76
6.6 Percolation theory for random, locally tree-like graphs . . . . . . . . . . . . . 79
7 Appendices 89
7.1 Network software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.2 The Pearson correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.3 Properties of symmetric matrices . . . . . . . . . . . . . . . . . . . . . . . . 90
7.4 Integral representation of the Kronecker δ-symbol . . . . . . . . . . . . . . . 93
7.5 The Landau order symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.6 Perron-Frobenius theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8 Exercises 95
, 4
1. Introduction
The challenge of large data sets. In recent decades our ability to collect and store vast
amounts of quantitative data has increased dramatically. This includes socio-economic data,
such as social links between individuals or professional collaboration networks, consumer
preferences and commercial interactions, trade dependencies among corporations, credit
or insurance obligations between financial institutions. We have access to traffic data on
computer and telecommunication systems, satellite networks, the internet, electricity grids,
rail, road or air travel connections and distribution networks. We collect and process large
amounts of geological and meteorological data, data on sea levels, air and water pollution,
volcanic and seismic records, and sizes of polar and glacier ice sheets. Finally, we have seen
an explosion in recent years of biomedical data, such as experimental data on biochemical
processes and structures at cellular, subcellular and even molecular levels, the topologies
of complex composite signalling and information processing systems such as the brain or
the immune system, genomic and epigenetic data (gene expression levels, DNA sequences),
epidemiological data, and vast numbers of patient records with clinical information.
However, one tends to collect data for a reason. This reason is usually the desire to
understand the dynamical behaviour of the complex system that generated the data, to
predict with reasonable accuracy its future evolution and its response to perturbations or
interventions, or to understand how it was formed. We may want this for commercial gain,
to improve and optimise a system’s efficiency, to design effective regulatory controls, or
(in the case of medicine) to understand and cure diseases. For small and simple systems
the translation of observation into qualitative and quantitative understanding of design
and function is usually not difficult. In contrast, if we collect data on complex systems
with millions of nonlinearly interacting variables, just having a list of the parts and their
connections and observations of their collective patterns of behaviour is no longer enough to
understand how these systems work.
Networks as data reduction and visualisation tools. A first and useful step in modelling
structural data on complex many-variable systems is to visualise these systems as networks
or graphs. The idea is to represent each observed system component as a node in the
network, and each observed interaction between two components as a link between the
two corresponding nodes. Dependent upon one’s research domain, the nodes of such
networks may represent anything ranging from genes, molecules, or proteins (in biology), via
processors or servers (in computer science), to people, airports, power plants or corporations
(in social science or economics). The links could refer to biochemical reactions, wired
or wireless communication channels, friendships, financial contracts, etc. The price paid
for the complexity reduction is the loss of information. Limiting ourselves to a network
representation means that we only record which parts interact, and disregard how and when
they interact. However, the rationale is that the topology of the interactions between a
