Complex Networks Theory Notes
Uploaded by
Ved Modi Kaura TGComplex Networks Theory Notes
Uploaded by
Ved Modi Kaura TGModule 6CCMCS02/7CCMCS02
Theory of Complex Networks
Compact Lecture Notes
Version of 31 March 2015
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
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Microscopic structural characteristics of graphs 22
3.1 Node-specific quantities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Generalised degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Quantities related to pairs of nodes . . . . . . . . . . . . . . . . . . . . . . . 24
4 Macroscopic structural characteristics of graphs 27
4.1 Average values of single-node features . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Distributions of single node quantities . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Distributions of multi-node quantities . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Generalisation to node features other than degrees . . . . . . . . . . . . . . . 34
4.5 Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Processes on networks and their relation to spectral features 37
5.1 Spin and voter models on networks . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Diffusion processes and random walks - the Laplacian matrix of a graph . . . 40
5.3 Spectra of adjacency matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.4 Spectra of Laplacian matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6 Random and pseudo-random graphs 48
6.1 Random graphs as ‘null models’ . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.2 The Erdös-Rènyi model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3 The Erdös-Renyi model in the finite connectivity regime . . . . . . . . . . . 51
6.4 Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.5 The giant component in random tree-like graphs . . . . . . . . . . . . . . . . 56
6.6 Tailoring topologies via maximum entropy random graph ensembles . . . . . 60
7 Further topics 65
7.1 Watts-Strogatz and shifted-Poissonnian small-world networks . . . . . . . . . 65
7.2 Preferential attachment networks . . . . . . . . . . . . . . . . . . . . . . . . 67
7.3 Complexity – counting graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3
8 Appendices 72
8.1 Network software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.2 The Pearson correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.3 Properties of symmetric matrices . . . . . . . . . . . . . . . . . . . . . . . . 73
8.4 Diagonalisation of symmetric matrices . . . . . . . . . . . . . . . . . . . . . 75
8.5 Integral representation of the Kronecker δ-symbol . . . . . . . . . . . . . . . 76
8.6 The δ-distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8.7 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.8 The Lagrange method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
9 Exercises 78
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
5
Figure 1. Neural networks, areas of the brain mapped using Golgi’s staining technique
by Ramon y Cajal around 1900. The nodes are brain cells (neurons), and the links are
coated fibres via which the neurone communicate electrical signals. The staining shows only
a tiny fraction of the links, in reality a neuron is connected on average to around 104 other
neurone. The topologies of these networks vary according to the brain area that is being
imaged, ranging from rather regular (in areas related to preprocessing of sensory signals) to
nearly amorphous (in higher cognitive areas).
system’s components should somehow be a fingerprint of its function, and that much can be
learned from the topologies of such networks alone.
For example, DNA contains the assembly instructions for large and complicated macro-
molecules called proteins. These proteins serve as building material for all the parts of the
cell, as molecular processing factories, information readers, translators, sensors, transporters
and messengers. They interact with each other by forming (temporary) complexes, which
are (meta)stable super-molecules formed of multiple proteins that attach to each other
selectively. Many experimental groups produce tables of molecular binding partners such
as that shown in Fig. 2. Network representations of these data have been very useful to
generate intuition on the possible relevance of individual nodes (i.e. proteins), and to suggest
functional modules. There are thousands of other examples of complex systems that tend to
be modelled as networks, of which a selection is shown in the various figures in this section.
6
Figure 2. Left: the data on human protein interactions (from HPRD data base), being
lists of pairs of protein species that have been observed to interact, together with codes of
each species and information on the experiments where interaction was observed. Each line
reports on one pair-interaction. This database contains some 70,000 reported interactions
(about half of the interactions believed to exist among human proteins). Right: the network
representation of the data on the left. Each protein is represented by a node, and each pair-
interaction (each line on the left) is represented by a link connecting the two nodes concerned.
Since interaction of two proteins is a symmetric property, this graph has nondirected links.
Figure 3. Gene regulation networks: here the nodes represent different genes in humans,
and the links (which now are directional) indicate the ability of individual genes (when
‘switched on’) to affect the extent to which other genes are activated. Here the links are
moreover ‘weighted’ (i.e. they carry a numerical value), indicated by solid arrows (positive
value, excitatory effect) or dashed arrows (negative value, inhibitory effect). The figure here
shows only a small subset of the genes – the true number of nodes is in the order of 20,000.
7
Figure 4. Graphical representation of the internet. Nodes represent the webpages and
links represent html jump instructions. In July 2014 it contained some 3.32 billion pages.
8
Figure 5. Social network of collaboration partners within an organisation
(here: a subset of IBM).
Figure 6. Network representations of interactions observed between share prices. Nodes
represent individual companies (with a colour code representing a classification of sectors),
and links imply significant observed correlation in the share prices of these companies.
9
Figure 7. Main arteries of the oil and gas distribution network, and of the national
electricity power grid of the USA. Here one would be interested in questions related to
the network’s vulnerability against targeted attacks, and how to design networks to reduce
the damage done by such attacks.
10
Figure 8. Phylogenetic trees, constructed from genome similarity. Here the nodes
represent species of organisms, and links represent the most plausible evolutionary ancestor
relationships. Top: general phylogenetic tree showing the main organism families and their
genome lengths. Bottom: focus on different strains of human influenza.
11
Figure 9. Ecological networks, mapping species and their mutual dependencies in a
given area (predator/prey or parasitic relationships, supply of food or other resources,
reproduction, etc). The nodes represent the different species of organisms, and links indicate
a mutual dependency.
12
Figure 10. Networks representing economic and financial relationships between the main
players in financial markets. It is now increasingly (and painfully) being realised by
regulators that the complex interconnected nature of the international financial system
means that new mathematical approaches are needed to understand, predict, and prevent
future financial crises. Top: the type of players required in models. Bottom: example of big
players and their dependencies and relations in the international banking network.
13
Figure 11. Immune networks. Nodes represent different ‘T-clones’ (families of immune cells
that coordinate the adaptive immune response to specific invaders). Links indicate that the
T-clones interact with a common B-clone (the B-clones actually trigger the destruction of
the invaders). In humans there are typically around 108 T-clones (i.e. nodes).
Figure 12. Simplified models of magnetic systems in statistical physics. Here the nodes
(of which there are of the order of 1024 ) represent sites on regular (2-dim or 3-dim) lattices,
occupied by atoms with intrinsic magnetic fields. The links indicate which pairs of magnetic
atoms are believed to be able to interact and exchange energy.
14
Figure 13. Mobility networks. These are very important in the modelling and prevention of
the spread of epidemics. Nodes are the main global population centres, and links represent
pairs of population centres with the most intensive traffic of people between them.
Note that network images in themselves are subjective. Different software tools will
use different protocols for deciding on the most appealing placements of nodes, and hence
generally will produce different visual representations of the same network (see e.g. Fig. 14).
It is perfectly fine to use graphical representations as intuitive aids, but we will need precise
mathematical descriptions when it comes to extracting information and testing hypotheses.
Figure 14. The two graphs shown here may look different, but are in fact topologically
identical. They differ only in the choices made for the placements of the nodes in the image
plane, i.e. in cosmetics.
This course will describe some of the mathematical and computational tools that have
been developed over the years to characterise and quantify network and graph topologies,
quantify the complexity of large networks, identify modules in networks, and to understand
the resilience of processes on networks against node or link removal. We also study how to
define and generate synthetic networks with controlled topological features.
15
2. Definitions and notation
2.1. Networks or graphs
Some authors use ‘networks’ to denote the physical objects in the real world, and ‘graphs’
for their mathematical description. Here we will not make this distinction.
• Definition: an N -node graph G(V, E) is defined by a set of vertices (or nodes)
V = {1, . . . , N }, and a set of edges (or links) E ⊆ {(i, j)| i, j ∈ V }
• Definition: a simple graph is a graph without self-links, i.e. ∀(i, j) ∈ E : i 6= j
• Definition: a nondirected graph is a graph with symmetric links only, i.e. if (i, j) ∈ E
then also (j, i) ∈ E
• Definition: a directed graph is one that contains non-symmetric links, i.e. ∃(i, j) ∈ E
such that (j, i) ∈
/E
6• 6•
'$ A
K A
A
5 A
5
•?@
3 A
• •@3 A•
&%
I 6
@ @
@ 4 @ 4
@ • - •A •7
- •
@ •A •7
2 A 2 A
1•
U
A
•8 1•
A
•8
V = {1, 2, 3, 4, 5, 6, 7, 8} V = {1, 2, 3, 4, 5, 6, 7, 8}
E = {(2, 1), (3, 2), (4, 2), (5, 2), (3, 3), E = {(2, 1), (1, 2), (3, 2), (2, 3), (4, 2), (2, 4),
(5, 4), (7, 4), (8, 4), (6, 5)} (5, 2), (2, 5), (5, 4), (4, 5), (7, 4),
(4, 7), (8, 4), (4, 8), (6, 5), (5, 6)}
Figure 15. Left: example of a directed graph. It is not simple, since it has a self-link (3, 3)
(note that in principle we could leave out arrows when drawing self-links, since there are
reciprocal by definition). Right: example of a simple non-directed graph.
• Conventions: in drawing graphs we use the following conventions, see e.g. Fig 15
(i) a node i is represented by a small filled circle
(ii) in directed graphs a link (i, j) is drawn as an arrow from node j to node i
(iii) in simple non-directed graphs a link (i, j), which in such graphs is always
accompanied by a link (j, i), is drawn as a line segment between nodes i and j
(iv) a self-interaction (i, i) is drawn by a small circle that starts at i and ends at i
16
In situations where in the context of the problem at hand it is clear that we have only non-
directed graphs, we leave out the explicit mentioning of both (i, j) and (j, i) and simple give
In these lectures we will limit ourselves to non-weighted graphs, i.e. we will not consider
graphs in which links carry a numerical value to represent their sign or strength. We consider
links to be binary objects: they are either present or absent.
2.2. The adjacency matrix of a network
Next we switch to a less cumbersome representation of graphs than sets of links, which will
also make subsequent calculations more easy. In an N -node graph there are N × N potential
links, the presence of each of which can be coded by a binary number, which we arrange as
the entries of a matrix:
• Definition: the adjacency matrix A ∈ {0, 1}N ×N of an N -node graph G(V, E) is defined
by the following entries:
Aij = 1 if (i, j) ∈ E, i.e. if there is a link j → i
∀(i, j) ∈ {1, . . . , N }2 : (1)
Aij = 0 if (i, j) ∈
/ E, i.e. if there is no link j → i
@ Aij = 1 @
i
@
@ • @
•@ j
@ @
@ @
@ @
• Consequence: a simple N -node graph has an N ×N adjacency matrix with zero diagonal
elements, i.e. Aii = 0 ∀i ∈ {1, . . . , N }.
• Consequence: a nondirected N -node graph has a symmetric N × N adjacency matrix,
i.e. Aij = Aji ∀(i, j) ∈ {1, . . . , N }2 .
• Consequence: a directed N -node graph has a nonsymmetric N × N adjacency matrix,
i.e. ∃(i, j) ∈ {1, . . . , N }2 such that Aij 6= Aji .
17
There is a one-to-one correspondence between the N 2 binary entries of A and the
specification of which links are present in an N -node graph, so each N -node graph
corresponds to a unique adjacency matrix and vice versa. We could therefore equivalently
also have defined our graphs and their types (e.g. directed, non directed, simple) on the
basis of the adjacency matrices and their properties, instead of starting from the edge and
vertex sets.
We can verify that the two network examples of Fig 15 correspond to the following two
adjacency matrices:
6•
0 0 0 0 0 0 0 0
'$ A
K
A
5 1 0 0 0 0 0 0 0
?3
• A
•
0 1 1 0 0 0 0 0
&%
I
@ 6
@ 0 1 0 0 0 0 0 0
A=
@ 4
• •A •7
@ - -
0 1 0 1 0 0 0 0
2 0 0 0 0 1 0 0 0
A
U
A
•8
0 0 0 1 0 0 0 0
1•
corresponds to 0 0 0 1 0 0 0 0
6•
0 1 0 0 0 0 0 0
A
A
5 1 0 1 1 1 0 0 0
•@3 •A
0 1 0 0 0 0 0 0
@ 0 1 0 0 1 0 1 1
A=
@ 4
• •A •7
@
0 1 0 1 0 1 0 0
2 0 0 0 0 1 0 0 0
A
•8
A 0 0 0 1 0 0 0 0
1•
corresponds to 0 0 0 1 0 0 0 0
We observe indeed that the second adjacency matrix is symmetric (as it corresponds to a
non-directed graph), in contrast to the first.
2.3. Paths in networks
Consider products of a graph’s adjacency matrix entries of the following form, with i, j ∈
{1, . . . , N }, and with i` ∈ {1, . . . , N } for all `:
k−1 f actors
k−1
Y z }| {
Ai` i`+1 = Ai1 i2 Ai2 i3 Ai3 i4 . . . Aik−2 ik−1 Aik−1 ik (2)
`=1
18
Since each individual factor is either 0 or 1 we must conclude that
k−1
Y
Ai` i`+1 = 1 if Ai` i`+1 = 1 ∀` ∈ {1, . . . , k − 1} (3)
`=1
k−1
Y
Ai` i`+1 = 0 otherwise (4)
`=1
But this implies
k−1
Y
Ai` i`+1 = 1 if the graph contains the path of connected links (5)
`=1
ik → ik−1 → . . . → i2 → i1
k−1
Y
Ai` i`+1 = 0 if it does not (6)
`=1
For instance, in the first (directed) graph of Fig 15 we have
A54 A42 = 1 : the graph contains the path 2 → 4 → 5
A45 A52 = 1 : the graph does not contain the path 2 → 5 → 4
A65 A54 A42 A21 = 1 : the graph contains the path 1 → 2 → 4 → 5 → 6
A76 A65 A54 A42 = 0 : the graph does not contain the path 2 → 4 → 5 → 6 → 7
and so on.
• Definition: a closed path (or cycle) is a path that starts and ends at the same node, so
k−1
Y
Ai` i`+1 = 1 with i1 = ik if the graph contains (7)
`=1
the cycle i1 → ik−1 → . . . → i2 → i1
k−1
Y
Ai` i`+1 = 0 with i1 = ik if it does not (8)
`=1
• Definition: a simple cycle in a graph is one that contains no repeated vertices or edges,
i.e. k−1
`=1 Ai` i`+1 = 1 with i1 = ik and all node labels in {i1 , . . . , ik−1 } are nonidentical.
Q
We can also ask whether there is any path of a specified length from a given initial node
j to a specified target node i. Now we do not care what exactly are the intermediate nodes
visited in between i and j. We are obviously interested in the presence or absence of paths
of length 2 or more, since having a path of length 1 means simply that Aij = 1 (which can
be read off directly from the adjacency matrix):
N
X N
X k−1
Y
... Aii1 Ai` i`+1 Aik j > 0 ⇔ there exists at least one path of (9)
i1 =1 ik =1 `=1 length k + 1 f rom node j to node i
N
X N
X k−1
Y
... Aii1 Ai` i`+1 Aik j = 0 ⇔ there exists no path of (10)
i1 =1 ik =1 `=1 lenght k + 1 f rom node j to node i
19
But since the summations over the indices {i1 , . . . , ik } in the latter formulae are equivalent to
doing matrix multiplications, we can simplify these formulae. We remember the definitions
of matrix multiplication and powers of matrices, e.g.
N N
(A0 )ij = δij , (Ak+1 )ij = (Ak )ir Arj
X X
(AB)ij = Air Brj ,
r=1 r=1
(with the Kronecker δ-symbol, defined as δii = 1 for all i and δij = 0 for all index pairs
i 6= j), and we conclude from these that the following is true
(Ak+1 )ij > 0 ⇔ there exists at least one path (11)
of lenght k + 1 f rom node j to node i
(Ak+1 )ij = 0 ⇔ there exists no path (12)
of lenght k + 1 f rom node j to node i
This shows already the benefit of working with adjacency matrices as opposed to the sets
(V, E) of nodes and links; for large N it would become painful to trace lines in images or
match entries in sets of index pairs, but instead we can simply do matrix multiplication.
Finally, the last step will not come as a surprise. If we don’t care about path lengths
but only ask about connectivity, we may write
(Ak+1 )ij > 0 ⇔ there exists at least one path f rom j to i
X
(13)
k≥0
(Ak+1 )ij = 0 ⇔ there exists no path f rom j to i
X
k≥0
Two final definitions in relation to paths in graphs with special properties:
• Definition: an Eulerian path in a graph is one in which each link (or edge) is traversed
exactly once.
• Definition: a Hamiltonian path in a graph is one in which each node (or vertex) is
visited exactly once.
2.4. Graphs within graphs
• Definition: a subgraph G0 (V 0 , E 0 ) of a graph G(V, E) is a graph such that V 0 ⊆ V and
E 0 ⊆ E.
For instance, the red graph below has V 0 = {1, 2, 4, 5, 6} and E 0 = {(1, 2), (2, 1), (1, 5), (5, 1),
(4, 5), (5, 4), (4, 6), (6, 4)}, and is clearly a subgraph of the one at the top of page 15.
20
• Definition: the connected components of a graph G are the largest sub-graphs of G such
that for each subgraph there exists a path between all vertices within the subgraph.
For instance, the graph in black on the left has the connected components shown in blue
and red on the right:
• Definition: a clique in a graph G is a maximal subset V 0 ⊆ V of vertices in the graph
such that every member of the subset has an edge connecting to every other. Here
‘maximal’ means that it is impossible to add any further edge to V 0 such that the new
edge connects to all previous edges in V 0 .
In this graph we all cliques of size 2, 3 and 4 shown respectively in purple, green and pink.
Note: the immune networks in Figure 11 consist strictly of connected cliques.
21
• Definition: a bipartite graph G is one in which the vertices can be divided into two
nonempty disjoint subsets, i.e. V = V1 ∪ V2 with |V1 |, |V2 | > 0 and V1 ∩ V2 = ∅, such
that all edges (i, j) ∈ E have either i ∈ V1 and j ∈ V2 or j ∈ V1 and i ∈ V2 .
The nodes in bipartite graphs can be divided into two qualitatively different groups, and
there are no links between indices in the same group. Examples are networks that represent
sexual relations in heterosexual groups, or graphs that represent relations between diseases
(node group 1) and clinical features (node group 2), networks mapping researchers and the
journals in which they publish, networks of resource generators and resource consumers, etc:
Generalisations to tripartite graphs (three disjunct vertex subsets, with links only between
nodes from different subsets) and to higher order partitions are obvious.
22
AA
K A A
A A
•@
I
•
A
6
•@ •
A •@ •
A
@ @ @
@ @ @
@• - •A - @ • •A @• •A
i AA i A i A
• • •
U A A
kiin (A) = 1 ki (A) = 4 ki (A) = 4
kiout (A) = 3 Ci (A) = 1/6 Ci (A) = 2/6 = 1/3
Ti (A) = 1 Ti (A) = 2
Figure 16. Left: in- and out degrees kiin (A) and kiout (A), i.e. the number of arrows flowing
into and out of the given node, in directed graphs. Middle and right: degrees ki (A), triangle
counters Ti (A), and clustering coefficients Ci (A) in non-directed graphs. Ci (A) gives the
fraction of distinct neighbour pairs of i that are themselves connected. In the absence of link
directionality, there is no distinction in nondirected graphs between left- and right-degrees.
3. Microscopic structural characteristics of graphs
3.1. Node-specific quantities
Node degrees. To characterize graph topologies more intuitively, we first inspect simple
quantities that inform us about their structure in the vicinity of individual nodes. The first
of these are the so-called in- and out-degrees kiout (A) ∈ IN and kiout (A) ∈ IN of each node i
in graph A. They count, respectively, the number of arrows flowing into and out of node i:
• Definition: the in-degree of node i in an N -node graph with adjacency matrix A is
defined as kiin (A) = N
P
j=1 Aij
• Definition: the out-degree of node i in an N -node graph with adjacency matrix A is
defined as kiout (A) = N
P
j=1 Aji
We denote the pair of in- and out-degrees for a node i as ~ki (A) = (kiin (A), kiout (A)) ∈ IN2 .
In nondirected graphs we find that always kiin (A) = kiout (A) (see exercises). Here we can
drop the superscripts and simply refer to ‘the degree’ of a node:
• Definition: the degree of node i in a non-directed N -node graph with adjacency matrix
P
A is defined as ki (A) = j Aij .
• Definition: the degree sequence of a non-directed N -node graph with adjacency matrix
A is defined as the vector (k1 (A), k2 (A), . . . , kN (A)) ∈ INN .
Clustering coefficients and closed path counters. There are many ways to characterise a
graph’s local structure beyond counting the neighbours of a node. For simple nondirected
23
graphs, the clustering coefficient gives the fraction of node pairs linked to i that are
themselves connected:
• Definition: the clustering coefficient Ci (A) of node i with degree ≥ 2 in a non-directed
N -node graph with adjacency matrix A is defined as
number of connected node pairs among neighbours of i
Ci (A) =
number of node pairs among neighbours of i
PN
j,k=1 (1−δjk )Aij Ajk Aik
= P N ∈ [0, 1] (14)
j,k=1 (1−δjk )Aij Aik
(for nodes i with degree 0 or 1 we simply define Ci (A) = 0).
We have already seen that products of entries of the adjacency matrix of a graph can be used
to identify paths. We can use this to count the numbers of closed paths of a given length:
• Claim: the number L` (A) of closed paths of length ` > 0 in an N -node graph with
adjacency matrix A (directed or non-directed) is given by
N N `−1 N
(A` )ii
X X Y X
L` (A) = ... Aik ,ik+1 Ai` ,i1 = (15)
i1 =1 i` =1 k=1 i=1
This follows directly from our earlier identities on paths. Note that the sum of the diagonal
entries of a matrix is called its trace, Tr(B) = i Bii , so we have L` (A) = Tr(A` ).
P
• Definition: the number of triangles Ti (A) involving node i in a non-directed simple
N -node graph with adjacency matrix A is defined as Ti (A) = 12 Nj,k=1 Aij Ajk Aki ∈ IN.
P
Ti (A), which can also be written as Ti (A) = 12 (A3 )ii , counts the number of distinct
nondirected loops of length three, in which node i participates. The factor 12 in Ti (A)
corrects for overcounting: any triangle starting and ending in node i can be drawn with
two possible orientations. Note that in simple non-directed graphs one has Ci (A) =
2Ti (A)/ki (A)[ki (A) − 1] (see exercises). In Fig. 16 we illustrate the various node
characteristics with some simple examples.
3.2. Generalised degrees
The concept of degrees can be generalised in obvious ways. For instance, the generalised
degrees of order ` ≥ 1 count the number of distinct paths of a given length ` that either flow
out of, or into a node i:
N N
(`)in X X
ki (A) = ... Aij1 Aj1 j2 . . . Aj`−1 j` (16)
j1 =1 j` =1
N N
(`)out X X
ki (A) = ... Aj` j`−1 . . . Aj2 j1 Aj1 i (17)
j1 =1 j` =1
24
(1)
ki (A) = 4
(2)
i • ki (A) = 20
Figure 17. Degrees and generalised degrees in non-directed graphs. At the minimal level
(1) P
one specifies for each node i (black vertex) only the degree ki (A) = ki (A) = j Aij (the
(1) (2)
number of its neighbours). Next one provides for each node the pair (ki (A), ki (A)), in
(2) P
which ki (A) = j` Aij Aj` is the number of length-two paths ending in i. Since the graph
at hand here is non-directed, we can drop the superscripts ‘in’ and ‘out’.
For ` = 1 these formulae reduce to the previous expressions for ordinary in- and out-degrees.
We can similarly introduce quantities that generalise the triangle counters Ti (A) by counting
closed paths in the graph A of arbitrary lengths ` ≥ 3, that pass through node i.
3.3. Quantities related to pairs of nodes
The distance between two nodes. We define the distance dij (A) between nodes i and j in a
non-directed graph with adjacency matrix A as the length of the shortest path from node i
to node j. It can be expressed in many ways, e.g. upon using our earlier formulae involving
paths:
• Definition: the distance dij (A) between nodes i and j is defined as follows
if there is no path f rom j to i : dij (A) = ∞ (18)
`
if there is a path f rom j to i : dij (A) = smallest ` ≥ 0 such that (A )ij > 0 (19)
Note 1: this distance is not the same as the distance between nodes in an image of the graph,
it is only based on how many links need to be crossed when walking from i to j.
Note 2: a path along which the shortest distance between two nodes is realised (there could
be more than one) is also called a geodesic.
An alternative way to obtain the distances between nodes in the graphs, without
checking one by one all possible routes from i to j, is provided by the following identity.
Here the inverse C −1 of an N × N matrix C (if it exists) is the unique matrix with the
property CC −1 = C −1 C = 1I, in which 1I denotes the N ×N identity matrix.
25
• Claim: log[(1I − γA)−1 ]ij
dij = lim (20)
γ↓0 log γ
Proof:
We first note that (1I − γA)−1 = `≥0 γ ` A` (see exercises). This series is always
P
convergent for sufficiently small γ. It then follows that
(1I − γA)−1 ]ij = γ ` (A` )ij = γ ` (A` )ij = γ dij (Adij )ij + O(γ dij +1 )
X X
`≥0 `≥dij
h i
= γ dij (Adij )ij + O(γ)
Hence
h i
−1
log[(1I − γA) ]ij log γ dij + log (Adij )ij + O(γ)
lim = lim
γ↓0 log γ γ→0 log γ
h i
dij
log (A )ij + O(γ)
= dij + lim
γ→0 log γ
1 h i
log (Adij )ij + O(e−x ) = dij
= dij − lim []
x→∞ x
The matrix inversion is usually impossible analytically, so is done numerically (see exercises).
Node centrality. To quantify how important an individual node i may be to sustain traffic
or flow of information over a graph, two measures of ‘centrality’ have been defined: the
closeness centrality and the betweenness centrality.
PN
• Definition: the average distance di (A) to node i is di (A) = N −1 j=1 dij (A).
• Definition: the closeness centrality xi (A) of node i is defined as xi (A) = 1/di (A).‡
• Definition: the betweenness centrality yi (A) of a node is defined as the number of node
pairs (k, `), with k 6= ` 6= i, such that i lies on a shortest path between k and `.§
Nodes with a high closeness centrality have small typical distances to the other nodes, and
are hence relatively close to any area of the graph. Nodes with a high betweenness centrality
are apparently important relay stations that reduce the shortest path lengths between node
pairs in the graph. They need not be on average close to the other nodes, but tend to be
the pivotal nodes that connect otherwise separate parts of the graph.
Similarity between node pairs. The functional role of any node i in an N -node graph with
adjacency matrix A is defined strictly by the specification of the links that flow into or out
‡ This definition is helpful and makes sense (and is therefore used) only for connected graphs, since otherwise
di (A) = ∞ (due to the appearance of node pairs that give dij (A) = ∞).
§ Sometimes this quantity is normalised by the total number 21 (N −1)(N −2) (in non directed graphs) of
node pairs not including i.
26
of it, i.e. by giving the two sets
∂iin = {k ≤ N | Aik = 1}, ∂iout = {k ≤ N | Aki = 1} (21)
In non directed graphs these two sets are identical for all i, so there we would simply speak
of the neighbourhood ∂i (without superscripts). Hence, any measure of similarity of nodes i
and j will somehow quantify the differences between (∂iin , ∂iout ) and (∂jin , ∂jout ). Here we will
show two common definitions for non directed graphs (possible generalisations to directed
graphs are obvious), with |S| denoting the number of elements in the set S:
• Definition: the cosine similarity between nodes i and j with nonzero degrees in a
nondirected N -node graph with adjacency matrix A is defined as
PN
|∂i ∩ ∂j | Aik Ajk
σij (A) = q = q k=1 (22)
|∂i ||∂j | ki (A)kj (A)
• Definition: the Pearson correlation similarity between nodes i and j with nonzero
degrees in a nondirected N -node graph with adjacency matrix A is defined as
PN PN PN
1 1 1
N k=1 Aik Ajk − N k=1 Aik N k=1 Ajk
τij (A) = r 2 r 2
1 PN 2 1 PN 1 PN 2 1 PN
N k=1 Aik − N k=1 Aik N k=1 Ajk − N k=1 Ajk
PN 1
k=1 Aik Ajk − ki (A)kj (A)
=q qN (23)
1 1
ki (A)[1 − k (A)]
N i
kj (A)[1 − k (A)]
N j
These measures obey −1 ≤ σij (A), τij (A) ≤ 1 for all (i, j) (see exercises).
The origin of the Pearson correlation (or Pearson coefficient) definition of distance
between node pairs is the following. In statistics the Pearson correlation of two variables
(u, v) with joint distribution P (u, v) measures the degree of linear relationship between u
and v, and is defined as follows (see also 8.2):
huvi − huihvi
PC = q (24)
(hu2 i − hui2 )(hv 2 i − hvi2 )
1 P
One obtains formula (23) above by choosing P (u, v) = N k δu,Aik δv,Ajk , see exercises for the
proof.
27
4. Macroscopic structural characteristics of graphs
The previous characteristics describe the topology of the graph in the neighbourhood of a
specified node. A global characterisation could be giving the full sequence of these local
numbers, as in the degree sequence k(A) = (k1 (A), . . . , kN (A)). However, as networks
get larger, it is increasingly inconvenient to draw conclusions and derive insight from large
sequences. To arrive at quantitative characteristics that are less sensitive to the number of
nodes, one has two simple options that continue to build on single-node features.
4.1. Average values of single-node features
The first is to consider the averages of the single-node quantities.
• Definition: the average in-degree of an N -node graph with adjacency matrix A is given
by k̄ in (A) = N −1 N in
P
i=1 ki (A)
• Definition: the average out-degree of an N -node graph with adjacency matrix A is given
by k̄ out (A) = N −1 N out
P
i=1 ki (A)
The average in-degree and the average out-degree in any graph are always identical (see
exercises), which reflects the simple fact that all arrows flowing out of a node will inevitably
flow into another node. So we can use in both cases the simpler notation k̄(A).
• Definition: the density ρ(A) ∈ [0, 1] of an N -node graph with adjacency matrix A is
the number of edges of a graph divided by the maximum possible number of edges.
P
We note that in a directed graph the number of links is L = ij Aij , in a non directed graph
P P P
it is L = i<j Aij + i Aii , and in a simple nondirected graph L = i<j Aij . Hence
P
Aij
directed graphs : ρ(A) = ij 2 (25)
N
P P P P
i<j Aij + i Aii i<j Aij + i Aii
nondirected graphs : ρ(A) = 1 = 1 (26)
2
N (N − 1) + N 2
N (N + 1)
P
Aij
simple nondirected graphs : ρ(A) = 1 i<j (27)
2
N (N − 1)
Note: in these definitions we do not count the links (i, j) and (j, i) in non-directed graphs
twice, and the number of non-diagonal entries in a symmetric matrix is 21 N (N − 1). These
densities can be written in terms of the average degree of a graph as follows (see exercises):
directed graphs : ρ(A) = k(A)/N (28)
X
nondirected graphs : ρ(A) = k(A)/(N +1) + Aii /N (N +1) (29)
i
simple nondirected graphs : ρ(A) = k(A)/(N −1) (30)
28
• Definition: the average shortest path length in a graph with adjacency matrix A
2 X
non−directed graphs : d(A) = dij (A) (31)
N (N −1) i<j
1 X
directed graphs : d(A) = dij (A) (32)
N (N −1) i6=j
• Definition: the diameter of a graph with adjacency matrix A is defined as d(A) =
maxi6=j dij (A) (i.e. the distance between the pair of nodes that are furthest from one
another in the graph).
• Definition: the average local clustering coefficient of an N -node graph with adjacency
matrix A is defined as C̄(A) = N −1 N
P
i=1 Ci (A).
Note: a graph is considered ‘small-world’, if C̄(A) is significantly higher than for a random
graph constructed on the same vertex set, and if the graph has approximately the same
mean-shortest path length as its corresponding random graph.
• Definition: the number of links L in a directed graph is L = i,j≤N Aij . In a non-
P
directed graph we do not count Aij = 1 and Aji = 1 separately, so here the number of
links would be L = 12 i6=j≤N Aij + i≤N Aii .
P P
4.2. Distributions of single node quantities
Degree statistics. For large graphs, or when comparing graphs of different sizes, we need
quantities that are intrinsically macroscopic in nature but more informative than just average
values of single-node features. The simplest of these are histograms of the observed values of
the N previously defined local features. If we divide, for each possible value, how often this
value is observed by the total number of observations (i.e. the number of nodes, we obtain
the empirical distribution of the given feature in the graph:
• Definition: the degree distribution of a non-directed N -node graph with adjacency
matrix A is defined as
1 X
∀k ∈ IN : p(k|A) = δ (33)
N i k,ki (A)
It gives for each k the fraction of nodes i in the graph that have degree ki (A) = k.
• Definition: the joint in- and out-degree distribution of a directed N -node graph with
adjacency matrix A is defined as
1 X
∀(k in , k out ) ∈ IN2 : p(k in , k out |A) = δ in in δ out out (34)
N i k ,ki (A) k ,ki (A)
It gives for each value of the pair (k in , k out ) the fraction of nodes i in the graph that have
kiin (A) = k in and kiout (A) = k out . Often we abbreviate δkin ,kin (A) δkout ,kout (A) as δ~k,~ki (A) ,
i i
with ~k = (k in , k out ).
29
p(k)
p(k)
k k k
Figure 18. Degree distributions as observed in several non-directed real-world graphs,
suggesting a tendency for these networks to have power-law distributions of the form
p(k) ∼ k −γ , with powers in the range 2 < γ < 3. The evidence for this is somewhat
weak in the first two examples, but the last four do indeed resemble lines in a log-log plot.
In many large real-world networks one observes degree distributions of a power-law form,
see e.g. Figure 18. These are also called ‘scale-free’ networks, since there is apparently no
‘typical’ scale for the degrees in such systems. See exercises. Most nodes typically have small
degrees, but there is a small number of nodes (the so-called ‘hubs’) with very large degrees.
This reflects organisation principles to which we will come back later.
Other statistics. Similarly we can define the joint distribution p(k, T |A) of degrees and
triangle numbers in non-directed graphs:
1 X
∀k, T ∈ IN : p(k, T |A) = δ δ (35)
N i k,ki (A) T,Ti (A)
Now p(k, T |A) is the fraction of nodes that have degree k and that participate in T triangles.
It will be clear how to generalise these ideas and define similar distributions for in- and out-
degrees and triangles in directed graphs, or distributions of generalised degrees.
76
pp
61
95
pp
pp
pp 21
pp
45
8
30
pp
pp pp
pp
55
84 51
pp
87 pp
pp 19
78
10 pp 34 32
pp pp pp pp
pp
pp
pp
58 12 pp 53
9 pp pp 94 pp
pp pp
pp pp
pp
21 65
pp 22
pp 56 75
63 pp pp pp
40 pp
pp pp 5 8 56
pp pp pp
pp 71 41
96 pp 3 pp pp pp pp pp
pp pp
pp 40 pp
pp pp 81
pp pp pp pp 17
89 pp
pp 91 pp 36
pp pp pp pp
pp pp 52 pp pp
pp pp 88
54
pp
pp
27
76 pp pp
pp pp pp
pp
66
pp
pp 70 pp pp pp pp pp 29
48 pp pp 52
92 pp
pp
pp
pp pp
98 24
27 84 pp pp pp
pp 51
pp 73 pp pp pp
pp 90 pp pp
pp pp
pp
pp pp
11 pp
86 70 pp
pp pp 45 37 pp
9
pp pp
64 78 pp pp pp
pp pp
82 pp pp
57 3 pp 77 pp
pp pp pp 42 pp
24 pp pp pp 41
81 pp pp pp 46
pp pp pp pp 74 pp
pp 42 pp pp 82 pp pp
77 pp pp pp 51
pp pp 12 pp pp pp pp pp 97
pp 71 pp pp pp pp 42
pp pp pp 30
pp pp 33 pp pp
pp pp pp pp 75
pp
pp
pp pp
53
pp pp 53 28 pp
pp
pp
pp
28 pp pp 44 81
13 pp 32 47 pp
35 pp
pp pp 83
pp pp 39 pp pp pp pp
pp 46 pp pp 52 pp 23 pp
pp pp 43 pp pp pp pp 26
pp 58 pp pp pp pp
26 pp pp pp 48
pp pp 49 pp pp
pp pp
31 pp pp
11 pp pp 73 91
97 49 pp pp pp pp pp
pp pp pp pp
pp pp pp
50 pp pp
pp pp pp
pp 93 45
pp 86 pp 61 pp pp pp
pp pp pp 69 pp 46 pp
27
pp pp pp pp pp pp 24 pp
pp 30 pp pp
4
pp pp pp 79 100 pp
pp pp
pp 47 74 43
pp 92 pp pp pp 40 pp
pp pp 7 48
83 69 pp pp pp pp pp 54 pp pp
pp pp pp 82
pp
pp 38 pp pp
pp 55 pp pp
pp pp pp pp 28
pp pp
90 pp pp pp 84
pp pp
6 pp pp
pp
13 pp 59 85 pp pp pp
pp pp 39 pp
pp
65 pp pp 88 pp pp pp 16 26 pp pp 47
pp pp pp 98 pp pp pp 38 pp
pp
15 pp pp pp 80 pp
pp
99 18 pp 89 pp 31
43 pp 25 pp pp
2 72 pp 25 pp pp pp pp pp pp
pp 60 pp pp pp
pp pp 63 pp
pp pp pp pp pppp 67 57 4 73
pp 23 96 pp pp 2
pp pp pp 44 pp pp
pp pp 66 37 pp 86 65 pp
pp pp pp
pp pp
pp pp pp pp 22 pp 93 83 pp pp
6 pp pp
pp 20 68 31 pp pp pp pp
pp
92 78 pp pp
pp pp pp pp 49 pp pp pp 30
pp pp 44 22 57 58 pp pp pp pp pp
pp pp pp pp
94 4 pp pp pp pp pp
pp 33 pp pp pp 3
pp 77 pp
pp pp pp pp pp pp pp pp
pp pp pp pppp pp pp
15 pp 35 60 pp pp
95
pp pp pp pp pp pp pp
pp pp 79 pp 87 pp pp
pp 23 14 pp 67
pp 21 pp 69 pp 74
pp pp
56 29 pp
80 pp pp
pp pp pp 32 pp
pp pp
pp
pp 19 5
pp pp pp pp pp
pp 15 pp pp pp pp
pp 67 pp pp pp pp pp pp
pp pp pp pp pp
pp pp pp pp pp
87 pp pp
17
pp pp 64 pp
pp pp
pp pp pp pp pp
pp pp pp 70
72 pp 96 66 pp pp
14 pp 7 85 18 pp 9 72 68 pp
pp 97 pp 20
10 39 pp pp
pp pp 17
pp 41 pp 2 88 6
29 pp 50 99 pp pp pp pp
pp pp 94 pp
pp pp 59 pp pp pp
pp pp pp pp pp
pp pp pp 89 pppp pp pp pp pp
59 100 pp pp pp
pp pp pp 35 pp pp
16 pp pp
pp
pp
76 pp
25 pp 16 pp
64 38 91 pp pp pp pp 7 pp pp 75
pp pp 95pp pp pp pp 71
pp pp 14 pp
pp 54 pp pp pp
5 pp
pp pp 18
62 63 36 10 pp
pp 80 pp pp pppp 100 pp
pp pp 11
pp pp
pppp pp pp
pp 98 pp
pp 8
33
90 pp pp
20 pp 99 pp
pp
19 pp pp
93 pp pp pp
79 60 pp
pp
pp 12
pp
pp 34
37
pp
pp
1 62 pp
1 13
62
pp
pp
34
61
85
55
pp
Erdös-Rényi Modular Small world
1.0 1.0 1.0
0.8 0.8 0.8
p(k) 0.6 0.6 0.6
0.4 0.4 0.4
0.2 0.2 0.2
0.0 0.0 0.0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
k k k
29 95
pp
23 pp 96 pp
pp
90 5
28
pp pp pp pp
pp
pp pp pp
pp
pp
pp 6
pp 13 pp
63 53 86 pp
pp 85
pp
4 pp 94
pp
39 pp
pp
pp pp
97 pp
42 pp 79
pp pp pp
33 88 pp
pp 66 pp
pp pp pp
pp
pp 15 pp
pp pp pp
pp pp pp
62 87
pp 56 60 pp pp pp
pp pp 95 pp
pp 85 19 pp pp 61 84
pp pp 7 16
pp
pp pp
pp 7614
16 27 pp
pp 3 75
pp
pp 40 pp
pp 87 pp pp
pp pp 93
7 pp pp pp pp pp
pp pp
pp
pp pp
pp
68 pp pp
12 pp 98
72 pp
pp
pp
21 pp 77 pp
pp
77 pp pp pp pp
pp 25
75 pp
pp pp 88
pp
17 pp pp
pp pp
pp 69 pp 17 pp 74
pp pp pp pp
pp 43 26
pp 13
95 83
pp 2
pp pp pp 8
pp pp 9 pp 66
43 pp pp pp
24 pp
pp
66 24 pp pp 65
pp 55 25 38 pp
pp pp pp pp
pp 75
pp 41 pp pp
1
pp
64 80 pp pp pp pp pp pp pp pp pp
pp pp 81 74 pp
94 78
pp pp pp 92 pp
pp pp 46 82 pp
pp pp pp pp pp pp pp
pp pp pp pp pp pp
70 pp
70 pp 71 73 pp
pp pp 81 60 78 pp pp
pp pp pp pp pp
pp 97 6 pp 99 35 pp
pp 67 pp pp 76 67
pp pp pp pp pp
pp pp pp 57 pp pp
pp pp pp 12
76 pp 31 27 pp
65 54 38 pp pp pp 89
36
pp
pp pp pp pp
pp pp pp 37 pp
37 pp 4 pp pp pp 64
pp pp pp 28 pp pp pp pp 99 pp
pp 18
pp 4 pp pp pp 56 pp 55 73
pp 84 pp 12
pp pp pp
22 85 pp pp pp pp
pp pp pp pp pp pppp 80 23 pp
pp 100 pp pp pp pp
pp pp 5
100 pp pp 93 pp
89 5 pp pp pp pp
pp 82
47 2 9 34
21 pp pp pp 34 pp
pp pp
pp 45
pp pp pp pp pp pp
48 pp pp pp pp
pp pp pp pp 46
pp 15 pp pp pp pp pp
pp 79 pp
pppp pp pp
53 pp
pp
96 pp 100 91
2 pp pp pp pp pp
pp pp
pp pp pp pp 56 pp 90 pp
pp pp pp pp pp
pp pp pp pp pp
pp 40 pp pp pp
89 26 pp pp
pp 34pp pp pp 48 58 pp 51 pp 1 pp pp
pp pp pp 6pp pppp pp pp pp pp
pp pp 35 pp 79 pp pp
pp
pp pp pp 23 22 pp 37 pp
pp 57 pp 54
pp pp pp pp pp pp
58 pp pp pp pp pp
pp 68 pp
pppp pp 91 32 50 pp
73 pp pp pp pp 31
pp
pp pp 29 pp pp 44
pp pp pp pp 54
pp pp
pp pp
pp pp
pp pp 96 pp 52 pp
pp pp pp 10
98 14 28
pp
11
14 pp pp 25 10 pp 81 63
pp 52 pp
pp pp pp pp pp 47
pp
30 pp pp 10 pp pp pp pp pp pp
pp pp
pp pp
19
pp
pp pp pp 72
83 pp
pp pp pp pp pp pp pp pp pp 80 22 pp
pp pp pp 11 pp pp pp
33
86 98 pp pp pp
pp pp pp pp pp
8 pp pp pp
65 pp
pp pp 59 pp pp
pp pp pp 18 pp pp
pp 15 8 pp
68 pp pp
78 97 pp
pp pp pp
61 pp pp
83 pp
pp
69 26 pp pp pp pp
pp pp pp pp pp pp
36 pp pp
pp pp pp
pp pp 67 pp pp pp
pp 58 69 53
55 pp 64 pp
pp pp
pp 93 30 38
pp 13 99 pp pp 43
pp pp 20
pp 35 pp
pp
21
pp pp 90 7 pp
pp 71
pp 20 pp
pp
27 pp
pp 86 pp pp
72 pp 29 62
36 pp 48
57 pp pp 88 pp
45 pp pp pp 70
62 pp pp 32
pp
74 pp pp
39 44 pp pp pp pp
pp pp 47 pp
33 pp
pp pp
pp 50 pp pp
pp
pp pp pp
32 pp pp
pp pp 59
pp 24
pp pp 52
63 30 pp pp
pp 31 42
39
pp pp 61
19
pp
3 pp pp pp
pp pp
60
pp pp49 pp pp pp
pp
pp
pp 92
91 pp
pp pp
pp
pp pp 49
77 40 pp 41 pp 51
pp pp pp
94 50
pp
51
84
11 pp 92
Scale-free Regular random Periodic lattice
1.0 1.0 1.0
0.8 0.8 0.8
p(k) 0.6 0.6 0.6
0.4 0.4 0.4
0.2 0.2 0.2
0.0 0.0 0.0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
k k k
Figure 19. Examples of small numerically generated non-directed graphs, all with N = 100
and k(A) = 4 (their precise definitions will be given in subsequent sections of these notes).
Clearly, size and average degree do not specify topologies sufficiently – there are still too
many ways to generate graphs with the same size and the same number of links. The degree
distribution provides additional information, but one would still like to go further.
31
4.3. Distributions of multi-node quantities
A logical next step, after having focused on the statistics of features that characterise nodes,
is to turn to features of links. For instance, for simple nondirected graphs A we can define
• Definition: the joint distribution of degrees of connected node pairs in a non-directed
N -node graph with adjacency matrix A is
P
0 0 i6=j δk,ki (A) Aij δk0 ,kj (A)
∀k, k ≥ 0 : W (k, k |A) = P (36)
i6=j Aij
@ @
Aij = 1
•@@ •@
@ @
@
@ @
@ @
ki (A) = k? kj (A) = k 0 ?
W (k, k 0 |A) gives the fraction of non-self links in the network that connect a node of degree k
to a node of degree k 0 . Clearly W (k, k 0 |A) = W (k 0 , k|A) for all (k, k 0 ), and W (k, k 0 |A) = 0
if k = 0 or k 0 = 0 (or both). From (36) follows also
• Definition: the degree assortativity a(A) in a non-directed graph is the Pearson
correlation between the degrees of connected nonidentical node pairs,
W (k, k 0 |A)kk 0 − ( k>0 W (k|A)k)2
P P
k,k0 >0
a(A) = 2 2 ∈ [−1, 1] (37)
k>0 W (k|A)k − (
P P
k>0 W (k|A)k)
W (k, k 0 |A).
P
with the marginal distribution W (k|A) = k0 >0
If a(A) > 0 there is a preference in the graph for linking high-degree nodes to high-degree
nodes and low-degree nodes to low-degree nodes; if a(A) < 0 the preference is for linking
high-degree nodes to low-degree ones. Upon summing the definition (36) over k 0 we see that
the marginal W (k|A) follows directly from the degree distribution, for simple graphs the
relation is
N
1 k
W (k, k 0 |A) =
X X
W (k|A) = δk,ki (A) ki (A) = p(k|A) (38)
k0 >0 N k̄(A) i=1 k̄(A)
(for graphs with self-links we would replace k̄(A) → k̄(A) − N −1 i Aii ). The reason why
P
W (k|A) 6= p(k|A) is that in W (k|A) the degree likelihood of nodes is conditioned on these
nodes coming up when picking links at random; this favours nodes with more links over those
with less. In those graphs where there are no correlations between the degrees of connected
32
nodes one would find that the joint distribution (36) is simply the product of the respective
marginals (38), W (k, k 0 |A) = W (k|A)W (k 0 |A) for all k, k 0 > 0. Hence, a useful quantity to
characterise correlations is
• Definition: the degree correlation ratio in a simple non-directed graph with adjacency
matrix A is
0 W (k, k 0 |A) k̄ 2 (A) W (k, k 0 |A)
Π(k, k |A) = = (39)
W (k|A)W (k 0 |A) kk 0 p(k|A)p(k 0 |A)
This quantity is by definition equal to 1 for graphs without degree correlations. Any
deviation from Π(k, k 0 |A) = 1 will signal the presence of degree correlations.
The degree correlations captured by Π(k, k 0 |A) can provide valuable new information that
is not contained in the degree distribution p(k|A). For instance, in Fig. 20 we show
two networks with nearly identical degree distributions, that are nevertheless seen to be
profoundly different at the level of degree correlations. The result of calculating the
macroscopic characteristics p(k|A) and Π(k, k 0 |A) for the example protein interaction data
of Fig. 2 is shown in Fig. 21.
For directed networks the degree correlations are described by a function W (~k, ~k 0 |A),
where ~k = (k in , k out ) and ~k 0 = (k 0in , k 0out ), since in directed graphs we must distinguish
between in-in degree correlations, out-out degree correlations, and in-out degree correlations:
• Definition: the joint distribution of in- and out-degrees of connected node pairs in a
simple directed N -node graph with adjacency matrix A is
P
ij δ~k,~ki (A) Aij δ~k0 ,~kj (A) 1
∀k, k ≥ 0 : W (~k, ~k |A) =
0 0
X
= δ~ ~ Aij δ~k0 ,~kj (A)
N k̄(A) ij k,ki (A)
P
ij Aij
(40)
@ @
Aij = 1
•@@ •@
@ @
@
@ @
@ @
~ki (A) = ~k? ~kj (A) = ~k 0 ?
with ~ki (A) = (kiin (A), kiout (A)).
W (~k, ~k 0 |A) gives the fraction of links in the network that connect a node with in- and out
degrees ~k to a node with in- and out-degrees ~k 0 . Clearly W (~k, ~k 0 |A) = 0 if ~k = (0, ?) or
~k 0 = (?, 0) (or both), but now we may find that W (~k, ~k 0 |A) 6= W (~k 0 , ~k|A).
33
p(k) Π(k, k 0 )
0.4 40
1.4
0.3 30
1.2
0
k
0.2 20 1
0.8
0.1 10
0.6
0.0
0 10 20 30
10 20 30 40
k k
0.4 40
1.4
0.3 30
1.2
k0
0.2 20 1
0.8
0.1 10
0.6
0.0
0 10 20 30
10 20 30 40
k k
Figure 20. Illustration of the limitations of using only degree statistics to characterise
graphs. The two non-directed N = 5000 graphs shown here look similar and have nearly
indistinguishable degree distributions p(k) (shown as histograms). However, they differ
profoundly at the level of degree correlations, which is visible only after calculating the
functions Π(k, k 0 ) for the two graphs, shown as heat maps on the right. In the top graph,
high degree nodes tend to be connected more to other high degree nodes. In the bottom
graph there is a strong tendency for high degree nodes to connect to low degree nodes.
The left and right marginals of W (~k, ~k 0 |A) need not be identical (in contract to non-
directed graphs). For simple directed graphs we find (see exercises):
W1 (~k|A) = p(~k|A)k in /k̄(A), W2 (~k 0 |A) = p(~k 0 |A)k out0/k̄(A)
• Definition: the degree correlation ratio in a simple directed graph with adjacency matrix
A is
W (~k, ~k 0 |A) k̄ 2 (A) W (~k, ~k 0 |A)
Π(~k, ~k 0 |A) = = in out0 (41)
W1 (~k|A)W2 (~k 0 |A) k k p(~k|A)p(~k 0 |A)
This quantity is by definition equal to 1 for directed graphs without degree correlations.
Any deviation from Π(~k, ~k 0 |A) = 1 will signal the presence of degree correlations.
34
Π(k, k 0 )
0.4 50
1.4
40
0.3
1.2
p(k) k0 30
0.2 1
20
0.8
0.1
10
0.6
0.0
0 10 20 30
10 20 30 40 50
k k
Figure 21. The degree distribution p(k) (33) (left), and the normalised degree correlation
kernel Π(k, k 0 ) (39) (right, shown as a heatmap) for the protein interaction network of Fig.
2. Here N ≈ 9000 and k̄(A) ≈ 7.5. Significant deviations from Π(k, k 0 ) ≈ 1, i.e. deviations
from green in the heat map, imply nontrivial structural properties beyond those captured
by the degree distribution.
4.4. Generalisation to node features other than degrees
In addition to inspecting the joint statistics of degrees of connected nodes, we can generalise
the idea to arbitrary discrete features xi ∈ X of a node i (which could be the degree of i,
but could also indicate its colour, gender, physical location, etc).
• Definition: the joint distribution of discrete features x of connected node pairs in a
non-directed N -node graph with adjacency matrix A is
P
0 0 i6=j δx,xi (A) Aij δx0 ,xj (A)
∀x, x ∈ X : W (x, x |A) = P (42)
i6=j Aij
@ @
Aij = 1
•@@ •@
@ @
@
@ @
@ @
xi (A) = x? xj (A) = x0 ?
W (x, x0 |A) gives the fraction of non-self links in the network that connect a node with
features x to a node with features x0 . Clearly W (x, x0 |A) = W (x0 , x|A) for all (x, x0 ). From
(42) follows also
35
• Definition: the assortativity a(A) relative to the discrete feature x in a non-directed
graph is the Pearson correlation between features of connected nonidentical node pairs,
W (x, x0 |A)xx0 − ( x∈X W (x|A)x)2
P P
x,x0 ∈X
a(A) = 2 2 ∈ [−1, 1] (43)
x∈X W (x|A)x − (
P P
x∈X W (x|A)x)
W (x, x0 |A).
P
with the marginal distribution W (x|A) = x0 ∈X
If a(A) > 0 the linked nodes tend to have positively correlated features; if a(A) < 0 they
tend to have negatively correlated features. Note that this definition (43) therefore is sensible
only for features x whose values are ordered in a meaningful way – like height or age, but in
contrast to e.g. colour.
Upon summing (42) over x0 we see that the marginal W (x|A) is
N
1
W (x, x0 |A) =
X X
W (x|A) = δ ki (A) (44)
x0 ∈X N k̄(A) i=1 x,xi (A)
Using the joint distribution p(x, k|A) = N −1
P
i δx,xi (A) δk,ki (A) of features and degrees of
nodes we can simplify the marginal of W to
X k
W (x|A) = p(x, k|A) (45)
k>0 k̄(A)
4.5. Modularity
Sometimes the prominent structure of a network is modularity, see e.g. Fig 22. In such
graphs nodes connect preferentially to other nodes that have the same module label – in fact
finding the optimal modules, i.e. the optimal assignment of a string (x1 , . . . , xN ) of module
labels to the nodes in the network, is a common problem in network applications. We can
now use the module membership label of each node as its feature in the sense above.
To quantify the extent to which a simple non-directed graph is modular, we compare
the number of ‘like-connects-to-like’ connections (or intra-modular links) in the graph A to
what we would have found if the wiring had been completely random:
1X
nr of intra−modular links in A : Lintra (A) = Aij δxi ,xj (46)
2 ij
(where the factor 12 reflects the non-directed nature of the graph, we don’t want to count the
same link twice). In contrast, in a random graph A0 (which we will study more rigorously
later) with the same degree sequence k = (k1 , . . . , kN ) as the graph A we would calculate the
expectation value of the above quantity as hLintra (A0 )i = 21 ij hA0ij δxi ,xj i = 12 ij hA0ij iδxi ,xj ,
P P
since there is assumed to be no relation between the labels x and the adjacency matrix. Now
hA0ij i = P (A0ij = 1|k).1 + P (A0ij = 0|k).0 = P (A0ij = 1|k) (47)
36
Figure 22. Examples of modular graphs. Here each node has a feature xi that represents
membership of a specific subset of nodes (its ‘module’, here the modules are shown colour-
coded). Nodes are more frequently connected to partners within the same module, as
opposed to partners from another module.
Here P (A0ij = 1|k) is the probability that in a random graph with degree sequence
k = (k1 , . . . , kN ) one will find nodes i and j connected. This must be proportional to
ki and kj , so we can estimate that hA0ij i ≈ ki kj /C. The value of C then follows upon
summing both sides over i and j, giving (since A and A0 have the same degrees):
hA0ij i = ( hence N k̄ = (N k̄)2 /C
X X X
ki )( kj )/C so C = N k̄ (48)
ij i j
This leads to our estimate hA0ij i = ki kj /N k̄, and hence
1 X ki kj
nr of intra−modular links in A0 : Lintra (A0 ) ≈ δx ,x (49)
2 ij N k̄ i j
We can then define (apart from an overall scaling factor) our measure of modularity in terms
of the difference between the number of intra-modular links seen in A and the number we
would expect to find by accident in a random non-modular graph A0 with the same degrees:
• Definition: the modularity of a non-directed graph with adjacency matrix A is
1 X ki (A)kj (A)
Q(A) = Aij − δxi ,xj (50)
2N k̄(A) ij N k̄(A)
The modularity obeys − 12 ≤ Q(A) ≤ 1
2
(see exercises).
37
5. Processes on networks and their relation to spectral features
We often study networks because they are the infrastructure of some process. Here we
inspect simple dynamical processes for variables placed on the nodes of graphs, to find out
which network aspects impact on the processes that they support. This leads us to the
eigenvalue spectrum of the matrix A, and of the so-called Laplacian matrix of the graph.
5.1. Spin and voter models on networks
First definition – simple linear model. Imaging having a simple non-directed N -node graph
with adjacency matrix A. Each node i represents an individual, and carries a continuous
variable si , which represents e.g. a voting opinion (si > 0: vote for party A; si < 0: vote
for party B; si = 0: undecided). Alternatively, we could think of the si representing the
orientations of magnetic atoms (si > 0: north pole up; si < 0: north pole down).
• Dynamical equations:
Each individual i gathers opinions (or magnetic forces) from his/her social circle ∂i ,
which is its neighbourhood on the graph: ∂i = {j ≤ N | Aij = 1}, and has his/her
opinion si driven by social pressure (the cumulative opinions) from the environment ∂i :
d X X
si (t) = sj (t) − λsi (t) = (A − λ1I)ij sj (t) (51)
dt j∈∂i j
λ > 0 represents a decay parameter – in the absence of peer pressure, i.e. for nodes
without neighbours, so ∂i = ∅, one would find si (t) = si (0)e−λt .
• Solution of dynamical equations:
Equation (51) is linear, and hence easily solved:
XB `
s(t) = e(A−λ1I)t s(0), eB = (52)
`≥0 `!
with s = (s1 , . . . , sN ). The matrix A is symmetric, so it has a complete set of N
orthogonal eigenvectors êk , with k = 1 . . . N , which can be normalised such that
0
∀k : Aêk = µk êk , ∀k, k 0 : êk · êk = δkk0 (53)
Here {µ1 , . . . , µN } are the N (not necessarily distinct) real-valued eigenvalues of A;
since they depend on A we should write µk (A), but if there is no risk of ambiguity we
will sometimes drop the argument A to reduce clutter in formulae. We can use the N
eigenvectors as our new basis in IRN , and write for any s ∈ IRN :
N
σk êk , σk = êk · s
X
s= (54)
k=1
Taking the inner product on both sides of (52), using (53), gives
38
X t` X t` N
0
êk · (A − λ1I)` s(0) = êk · (A − λ1I)` σk0 (0)êk
X
σk (t) =
`≥0 `! `≥0 `! k0 =1
N X t` N X t` (µk0
0 − λ)` k k0
êk · (A − λ1I)` êk =
X X
= σk0 (0) σk0 (0) ê · ê
k0 =1 `≥0 `! k0 =1 `≥0 `!
N X t` (µk0 − λ)`
δkk0 = σk (0)et(µk −λ)
X
= σk0 (0) (55)
k0 =1 `≥0 `!
Eigenvalues of A with µk < λ will have σk (t) → 0 and those with µk > λ will have
σk (t) → ±∞. Hence either |s(t)| → 0 or |s(t)| → ∞ as t → ∞; the dynamical
variables evolve either to zero or to infinity. Hence, although this model (51) is well-defined
mathematically, it is not a good description of social or magnetic interactions.
Revised definition – spherical model. To cure the maladies of the previous model without
sacrificing its linearity, we can replace the constant λ in (51) by a time dependent decay rate
λ(t). If we define this λ(t) by the requirement that s2 (t) = N for all t ≥ 0, so that the
divergencies of the previous laws can no longer occur, we obtain a so-called spherical model:
• Dynamical equations:
d 1
∀t ≥ 0 : s(t) = As(t) − λ(t)s(t), λ(t) = s(t) · As(t) (56)
dt N
d 2
The second equations follows upon setting s2 (0) = N and demanding that dt s (t) = 0
k
for all t ≥ 0. Again we switch to the new basis of eigenvectors {ê }, by substituting
k
s(t) = N
P
k=1 σk (t)ê into (56), which now leads to the following equations, from which
we need to solve both the {σk (t)} and λ(t):
N
d 1 X
σk (t) = [µk − λ(t)]σk (t), λ(t) = µk σk2 (t) (57)
dt N k=1
• Solution of dynamical equations:
The first equation in (57) is solved easily:
Rt
dt0 λ(t0 )
σk (t) = σk (0)eµk t− 0 (58)
Substitution into the second equation of (57) then gives an equation for λ(t):
N
Rt
dt0 λ(t0 ) 1 X
λ(t)e2 0 = µk e2µk t σk2 (0) (59)
N k=1
N
d 2 R t dt0 λ(t0 ) d 1 X
e 0 = e2µk t σk2 (0) (60)
dt dt N k=1
N
Rt
dt0 λ(t0 ) 1 X
e2 0 = e2µk t σk2 (0) + C (61)
N k=1
39
v
Z t u N
0 0
u 1 X
dt λ(t ) = log t e2µk t σk2 (0) + C (62)
0 N k=1
σk2 (0) = N :
P
We find the constant C by evaluating the above for t = 0, using k
N
1 X
1= σk2 (0) + C hence C=0 (63)
N k=1
We thus obtain the following solution:
N N 2µk t 2
P
1d h1 X i
k=1 µk e σk (0)
λ(t) = log e2µk t σk2 (0) = PN (64)
2 dt N k=1 2µ k σ 2 (0)
t
k=1 e k
• Asymptotic behaviour:
Let us assume, for simplicity, that we do not have the pathological case where the
initial vector s(0) was strictly orthogonal to one or more of the A-eigenvectors. So
σk (0) = êk · s(0) 6= 0 for all k. Let us also define the largest eigenvalue µmax :
µmax = max µk , S = {k ≤ N | µk = µmax } (65)
k≤N
Multiply numerator and denominator of (64) by exp(−2µmax t) and take t → ∞:
2(µk −µmax )t 2
µmax σk2 (0) + k∈S
P P
k∈S / µk e σk (0)
lim λ(t) = lim P 2 P N 2(µ −µ )t 2
k∈S σk (0) + / e σk (0)
t→∞ t→∞ k max
k∈S
P 2
µmax σk (0)
= k∈S P 2
= µmax (66)
k∈S σk (0)
We also know from (56) that, using standard linear algebra,
s(t) · As(t) x · Ax
λ(t) = 2
≤ maxx∈IRN = µmax (67)
s (t) x2
with equality if and only if s(t) is in the eigenspace of A with eigenvalue µmax . We see
in (66) that our process (56) evolves towards an eigenvector of A with eigenvalue µmax .
The second largest eigenvalue of A controls the timescale over which the evolution towards
stationarity takes place. If we make the simple choice σk (0) = 1 ∀k for the initial conditions,
we can write the solution λ(t) at any time in terms of the so-called eigenvalue spectrum
N
1 X
%(µ|A) = δ[µ − µk ] (68)
N k=1
(see appendix 8.6 for definition and properties of the δ-distribution). To see this we note
that when σk (0) = 1 ∀k our equation (64) simplifies to
1 PN 2µk t
dµ %(µ|A)µ e2µt
R
N k=1 µk e
λ(t) = 1 N = R (69)
2µk t dµ %(µ|A)e2µt
P
N k=1 e
We conclude that the dynamics of such processes on graphs depends critically on the
eigenvalue spectra of their adjacency matrices.
40
5.2. Diffusion processes and random walks - the Laplacian matrix of a graph
Diffusion processes on networks. Imaging again having a simple non-directed N -node graph
with adjacency matrix A. Each node i of the graph now contains a conserved resource zi ∈ IR
(e.g. energy, water, food, money, etc), which can diffuse (or ‘leak’) away to its neighbours,
always from high to low levels. With ‘conserved’ we mean that, in contrast to the variables
in our previous dynamical models, if the amount of the variable increases at one node it
has to decrease somewhere else in compensation. The rate of diffusion between two nodes
is larger when their differences in resource levels are larger, as would be the case with e.g.
heat or water pressure.
d X X
zi (t) = [zj (t) − zi (t)] = Aij zj (t) − ki (A)zi (t) (70)
dt j∈∂i j
This process can be written in terms of the N × N so-called Laplacian matrix L with entries
d
zi (t) = − j Lij zj (t), where
P
Lij , as dt
Lij = ki (A) δij − Aij (71)
and the solution of the diffusion process becomes, with z = (z1 , . . . , zN ),
z(t) = e−Lt z(0) (72)
We could again worry about diverging solutions, but we will see below that all eigenvalues
of L are nonnegative, so here this cannot happen. In fact we can show easily from (70) that
P
the total amount Z = i zi is conserved over time:
d XX X X
Z(t) = Aij zj (t) − ki (A)zi (t) = kj (A)zj (t) − ki (A)zi (t) = 0 (73)
dt i j j i
Random walks on networks. Random walks on non-directed graphs are discrete versions of
diffusion processes. We define pj (t) ∈ [0, 1] as the probability that the walker is at site j
at time t ∈ IN. At each time step he moves to a new site i, selected randomly and with
equal probabilities from the neighbours of j. Since there are kj (A) sites to choose from, the
probability to go to each one of these is kj−1 (A). Hence the dynamical equations are
X 1 X Aij
pi (t + 1) = pj (t) = pj (t) (74)
j∈∂i kj (A) j kj (A)
With the definition Dij (A) = ki (A)δij this can be rewritten as pi (t + 1) = j (AD −1 )ij pj (t),
P
and hence, upon defining p(t) = (p1 (t), . . . , pN (t)), we can write the solution at any time as
p(t) = (AD −1 )t p(0) (75)
We see that the stationary state solution p = (p1 , . . . , pN ) of this equation can be written as
p = Dx, with (D − A)x = 0. Since D − A is the Laplacian matrix, we see that again the
41
Laplacian is the relevant matrix to describe the process.
The dynamical and asymptotic features of diffusion-type processes on graphs are
apparently controlled by the eigenvalue spectrum of the Laplacian matrix, rather than that
of the adjacency matrix. Note: the entries of the Laplacian matrix of a simple non-directed
graph are no longer binary, Lij ∈ {0, −1} if i 6= j, and Lii ∈ IN.
5.3. Spectra of adjacency matrices
Properties of eigenvalue spectra of adjacency matrices. The previous pages showed why the
spectra of adjacency matrices and Laplacians are important, from the point of view of the
impact of topological features of graphs on the processes for which they are the infrastructure.
We now investigate the properties of these spectra, and get some feeling for which spectra
we might expect to find for real networks.
• Definition: the eigenvalue spectrum % : IR → IR of the adjacency matrix A of a non-
directed N -node graph with eigenvalues {µ1 (A), . . . , µN (A)} is
N
1 X
∀µ ∈ IR : %(µ|A) = δ[µ − µk (A)] (76)
N k=1
• Consequence: for any well-behaved function f (µ) (for precise conditions on f see the
field of Distribution Theory) one has
N Z ∞
1 X
f (µk (A)) = dµ f (µ)%(µ|A) (77)
N k=1 −∞
This follows directly from the properties of the δ-distribution, see Appendix 8.6.
We know from linear algebra that all eigenvalues of symmetric matrices are real-valued,
hence the above restriction to non-directed graphs. Adjacency matrices of directed graphs
will indeed normally have complex eigenvalues.
In the remainder of this subsection, let A be the adjacency matrix of a non-directed
N -node graph, and let µmin (A) and µmax (A) denote the smallest and the largest eigenvalue
in the set {µ1 (A), . . . , µN (A)}. Let u be the N -dimensional vector u = (1, 1, . . . , 1):
• Claim: µmin (A) ≤ k̄(A)
Proof: x · Ax u · Au 1 X
µmin (A) = minx∈IRN 2
≤ 2
= Aij = k̄(A)
x u N ij
• Claim: µmax (A) ≥ k̄(A)
Proof: x · Ax u · Au 1 X
µmax (A) = maxx∈IRN 2
≥ 2
= Aij = k̄(A)
x u N ij
42
• Claim: µmax (A) ≤ maxj=1...N kj (A).
Proof:
Let µ be an eigenvalue of A and x ∈ IRN the corresponding eigenvector. Define
x? = maxi xi . If x? ≤ 0 (so all components of x are non-positive) we replace x → −x,
so that we will have x? > 0 (note: since x 6= 0 this is always possible to achieve). Now
choose i to be a site with xi = x? , and use xj ≤ x? for all j:
µx? =
X
Aij xj
j
X xj X x?
µ = Aij ≤ A ij ? = ki (A) ≤ maxj=1...N kj (A)
j x? j x
Since this result holds for any eigenvalue µ, we can indeed also state the above claim.
We can combine the above three inequalities into the following corollary:
µmin (A) ≤ k̄(A) ≤ µmax (A) ≤ maxj=1...N kj (A) (78)
• Definition: a non-directed N -node graph with adjacency matrix A in which all degrees
ki (A) are identical to q, i.e. ki (A) = q for all i, is called a q-regular graph.
• Claim: the largest eigenvalue of the adjacency matrix A of a q-regular non-directed
N -node graph with adjacency matrix A is µmax (A) = q.
Proof: this follows directly from (78).
• Claim: the eigenvalue spectrum %(µ|A) of a simple non-directed graph obeys
Z
dµ µ%(µ|A) = 0 (79)
Proof:
We use the fact that for each symmetric matrix A there exists a unitary N × N matrix
U , i.e. one such that U U † = U † U = 1I, such that A = U D(µ)U † , where D(µ) is the
diagonal matrix with entries D(µ)ij = µi (A)δij . Now
Z Xh i Xh i
dµ µ` %(µ|A) = µ`k (A) = D ` (µ) (U † AU )`
X
N =
kk kk
k k k
Xh `−1 i Xh i
= U † AU U † AU = U † A`−1 AU
kk kk
k k
Xh i
U † A` U (U † )ki (A` )ij Ujk = (A` )ij Ujk (U † )ki
XX XX
= =
kk
k k ij k ij
` † ` `
X X X
= (A )ij (U U )ji = (A )ij δij = (A )ii
ij ij i
1
For ` = 1 this gives dµ µ` %(µ|A) =
R P
N i Aii = 0.
43
human PIN N = 5000 simple N = 5000 complex
1 1 1
%(µ)
0 0 0
-5 -3 -1 1 3 5 -5 -3 -1 1 3 5 -5 -3 -1 1 3 5
µ µ µ
Figure 23. Adjacency matrix eigenvalue distributions %(µ) of three graphs shown and
quantified in previous figures. Left: eigenvalue distribution for the human protein interaction
graph (see Figures 2 and 21). Middle and right: eigenvalue distributions for the two graphs
in Fig. 20. The middle histogram refers to the graph with only weak degree correlations (top
line in Fig. 20) and the right histogram refers to the graph with strong degree correlations
(bottom line in Fig. 20). The eigenvalue spectra of the last two graphs are seen to be
significantly different, in spite of their nearly identical degree distributions.
• Claim: the eigenvalue spectrum %(µ|A) of a non-directed graph obeys
Z
dµ µ2 %(µ|A) = k̄(A) (80)
Proof:
From the previous proof we know that for any integer ` > 0: dµ µ` %(µ|A) =
R
1 P ` 2
N i (A )ii . Upon choosing ` = 2 we find, using Aij = Aij for Aij ∈ {0, 1}:
Z
1 X 2 1 X
dµ µ2 %(µ|A) = (A )ii = Aij Aji
N i N ij
1 X 1 X
= Aij = ki (A) = k̄(A) (81)
N ij N i
Link between adjacency matrix spectra and closed path statistics. From the eigenvalue
spectrum %(µ|A) of the adjacency matrix A of a non-directed graph one can obtain the
numbers L` (A) of closed paths of all possible lengths ` in this graph, since
• Claim: for any integer ` > 2 the eigenvalue spectrum %(µ|A) of a non directed graph
with adjacency matrix A obeys
Z
1
dµ µ` %(µ|A) = L` (A) (82)
N
where L` (A), defined in (15), gives the number of closed paths of length ` in the graph.
Proof:
340175
481 430
44
447 776
594
811 843 255 155 123 124
688 254 256 154 156
186 187 92
80 468 529 253 250 249 248
727 999 122 91 125 93
1000 209 185 60
474 247 208 61
887 997 998 251 210 257 218153
772 95 200 217 29 94 62
996 207 90 59
28 30
990 211 473 201 121
720 995 252 199 184 188 157
686 991 246 206 216 126
994
258 202 3163
647 992 212 152 219 189 27
475 249 220 58 95
475 907 989 158 127
391 789 205 203 89
993 472 505 248 251 96 64 32
161 160 213 245
346 131 198 504
333 711 215 250 65
570 698 637 204 183 120 97
999 405 476 638 506 259
636 128
503 190 159 66 34
982 162 635 33 1
284 124 130 214 674 247 26 35
389 159 988675 639 282 221
759 132
160 330 244 634 502 151 4 3
947 113 315 725 673 57
626 280 252 98 67 36 5
230 722 899 2
471 676 633
723 761 129 163 507 129
477 197 625 281 88 160
519 753 151 869 672 215 640 260 214
413 832 133 243 627 279
578 205 158 374 283
985 763 987 501 246 191 6
512 900 898 632
444 452 182
111 357 119 68 37
661 677 538
473 128 628 222 569
671 216 242 313 99
85 164 478 25
641 373 952 624 278 570
685 975 508 500 631 506
328 134 375 953 253 601
165 629 130 537
157 470 479 314 507 600
173 697 15 901 986 196 951 539
828 261 150 284 56 7
991 897 241 161
952 898 670 245
87 127 217 480 678 213 311 312 568
327 954 630 475
808 167 307 21 499 474 505
762 329 642 38 571 632
49 768 481 623 950 87 192 602
815 791 277
465 165 372 240 310 315 69 631
269 822 930 135 902 985
171 976 509 443 536 508 599
100 669 156 181
619
878 987 442 476 540
638 684 326 376 223
998 664 182 755 891 218 485 100
535 420 484 473 633
195 949 498 118 411
126 896 482 469 239 663
8 713 233 234 309 344 345 285 410 567
553 9 974 643 262 347 379 444 603 662
436 144 330 955 679 24 346 254 572
882 486 244 131 504
216 668 50 622 235
400 241 289 903 276 378 630
752 267 683 60 325 425 984 49 232 441 8
262 136 487 51 412 634
617 971 166 316
852 325 483 238 212 348 380 509
609 666 564 256 155 219 488 371 497 236 149
343 162 664
61 948 598
944 248 535 477 541 693
902 48 55 409
510 290 308 342 472
39 314 888 739 667 644 377 39 661 694
876 143 602 613 995 125 52 496
707 839 620 482 341 445
678 274 904 895 489 377 231
293 331 237 193 665
187 317
933 136 612 194 495 289 341
580 24 581 172 468 413 566
706 137 86 604
524 324 220 180 376 440 70 724
215 490 494 621 275 349 503 629
693 480 893 71 47 680 291 573 692
792 101 154 983 947 243 286 381 635 695
936 840 780 167 221 956
392 457 702 666 493 263 224
222 53 375 408 510
821 491 340
164 230 307
531 774 645 492 795 288 117 478
316 38 223 101 725
128 309 238 905 696723
115 275 124 597 660
489 224 370 796 23 534 542
367 201
567 783 649 662 794 255 471 666
311 294 332 661 292 211 446
291 809 959 379 323 138 663 894 225 511
355 946 374 132 755
323 896 156 46 229 318
536 574 665 28 339 9
385 696 412 220 226 148
635 467 407 414 691 726
191 493 174 575 153 193 228 793 54 29 274 373 439
166 145 745 227 378 287 350 382
494 664 306 54 754
92 125 459 646 573 982 620 403 565 628
956 797 163
892 600 917 168 660 572 681 502
55 555 371 736 574 372 511 605 722 756
958 369 561 217 94 906 293 242 40 479 636 697 727
169 54 485 27 287
769 960 123
322 139 333 571 957 574
909 404 338 179
424 264 406 194
5 401 500 786 792 945 85
464 921 351 297 575 45 30
280 626 429 659 785 786
583 588 893 91 371
562 369 402 470 447 667 753
681 292 734 180 152 55 757
506 329 647 570 90 512 71 533 596
243 57 903 659 286 438
778 294 305 225 543
916 140 466 798 319 690
116 256 415
499 398 96 405 273 210 405
277 363 874 798 981 26 728
695 58 349 907321 334 576 379 22 351 721
169 192 337 383 787
997 680 569 791 370
849 910 89 619 102 758
421 886 92 784
630 525 934 140 122 682 31 944 480 816
845 322
152 870 698
427 533 648 658 44 401 404 501 512
339 442 151 295 147 627 752
154 675 68 715 577 56 10
483 116 406 437 564 817
913 744751 276 141 568 958 241 53 133
859
402 455 939
540 353 285 892 265 285 288 788
82 236 590 951 880 335 513 369 403 469
978 922 682 781 88 304 448
105 71426 528 183 730 320 93 799 637
25 606 783 815
107 279 908 657 465 790 980 336 658 759
649 368 407 178 575
665 393 526 296 164
288 396 133 360 382 656 578 32 729
800 74 185 616 260 150 43 940 943 41 818847
534 46 170 84 320 532 668 689
831 356 199 272 402 436 416
308 547 584 672 16 758 567 400 720
299 142 121 57 938 481 789
76 942 226 582 530 380 544 595
692 232 240 336 191 368 195 257 352 751
509 605 233 123 866 861 618 941 384
558 650 992 814
650 828 829 94 408 683 846
784 914 655 87 209
915 319 827 297 284 115 848
51 487 282 401 468 500
426 577 690 42 226 72 513 699
618 149 514 335 819
895 962 579 33 24 435 449 782
941 2 802 969 909 566 891 800 21
912 954 206 22 3 654 959 979 942 303
411 544 652 474 296 464 830
35 463 414 143 826 789 266 937 760 790
377 626 878
129 42 651 399 367
361 409 58 240 146 289
237 1 628 994 337 41 563 845
660 263 171 298
7 53 795 95 400 103 849
445 572 931 653 565 52 813 877
378 460 306 754 458 214 50 148 120 318 367 434 482 730
86 820
228 928 824 148 615 40 11 417
157 731 652 34 467 657
138 825 831
249 144 283 271 321 531
639 710 539 404 568 190 334 450 607 638 719 879
319 286 738 456 910 381 617 684 936 177
726 39 580 410 23 750
923 564 67 134 576 688
257 967 354 663 537 299 366 499 669
89 515 978 801 399 433 353 385 876
338 38 398 83 258 844 850
662 318 640 501 589 298 321 147 317 35 545 781 791 909
817 78 69 463 59
362 79 130 223 668 939 37 302 594 908
973 904 834 890 96 36 66 42 514 821
765 145 761
372 671 960 300 788 267 165
352
721 104 466 700
712 93 375 637 119 146 172 563 303 302 208 880
195 899 34 591 435 227 85 301 432 451 812
231 700 543 310 832 411 68 483
28 18 384 824 304 227
938 466 255 311 309 282 398 114
316 305 935 418
312 278 565 770 911 306
308 22 65 365 333 20 196 875 907851 910
641 350 312 307
579 397 73 290 939
741 20 807 797 339 516 685 562 625
453 225 450 581 731 940
471 17 977 69 60 239
548 418 818 399 366 431
748 97 498 843
161 234 742 879 184 313 562 412 802 465 822
557 862 315 189 616 452 792
855 732 545 868 382 145 530 881
972 948 317 830
677 624 703 462 397 51 386
229 120 551 659 118 64 270 749
449 70 322 419 656 718 780
563 84 852
906 938
648 702 771 517 268 364 104 911
940 980 173 823 889 833 787 934 281 12
881 981 413 354 941
338 961 21 301 687
364 314 762 874
272 479 873 912 772 396 61 430 484 515 639 670
669 819 724 546 608 811
423 561 332 176 464 577
507 340 71 259 420
407 190 196 453
395 386 179 704 63 882
607 305 98 396 82 593
596 801 629 439 701 773 976 686 497 701
344 10 36 250 270 414 937
469 434 718 302 872 582 518 803 135 823
443 56 498 770 363 421 842 912
901 935 492 117 853
872 932 73 874 43
331 926 328 429 905 942
334 141 467 31 889 72
258 336 636 83 280
505 202 810 347 955 779 440 560 383 933 20 62 463 207 422 387 732 793
326 462 446 261 787 461 188 365 615 395
11 576 395 228 561
542 244 774 423 883
177 142 689 822 834 394 113 454 529
656 653 643 438 174 700 269 166 291 873
733 968 871 415 786 19 393 624
705 913
957 888 519 600 362
99 485 779
611 197 740 441 341 962 331 424 936
606 121 599 428 392 748 913
303 433 875 810
538 885 694 769 73 462 496 74 197 943
310 514 431 559 238 355 763
703 975 687 516 323 717 854
242 842 599 804
627 116 82 279 19 388 824 904
884 163 735 734 655
335 29 441 775 425 391 841 884
19 676 919 235 153 437 583 50 300 686
848 176 194 883 419 408 376 442 699 736 601 269 455
632 287 932 427 144 547
833 365 870 416 733 394 390 389
604 897 118 313 361
394265 717 979 348 41 750 558 598 426 671
390 443 461 578 794 914
30 706 100 74 384 609 640 872
920 625 515 112 876 460 520 13 592 935 944
644 964 821 737 702
679 865 988 790 667 614 914 187 614 105
146 491 517 175 81 785 270 732 260
829 873 835 18 495 528
566 756 953 549 768 278
511 929 486
45 63 825 436 698 342 364 733 903
83 846 603 552 887 602 81 855 885
409 688 805 175 456
110 239 25 444 115 460 330
518 986 301 869 776 963 75 560
204 417 557 597 360 356 778 809 915
541 593 735 825
210 472 731 974
106 642 812 80 393 764 840 945
33 556 101 44 934
673 796 738 76 18
6 490 450 931 136 292 747
704 17 517 623 871
281 86 877 77 457 494
804 631 380 65 707 697 79 78 584
200 496 98 532 445 459 229 324
503 108 277 521 112 206 795
428 373 793 221 603 359 716 902
495 368 435 271 385 458 299 886
858 621 162 459 767 915 689 916
324 777 820 596 487 357 856 946
337 875 451 449 176 868
767 943 203 854 320 418 784 730 806 527 654
246 794 775 546 102 167 358 548 685
188 747 13 114 777 186 836 556 16 49 933
657 168 343 613 392 493 75
4 47 771 990 451 826
497 993 106 886 696 198
27 40 651 446 739 329
708 237 579
178 268 672 703 839
300 520 764 67 945 219 105 973 591 808
841 996 132 103 964 363 870
448 276 690 143 14 610 641 734
587 878 930 604 492 777 917 947
728 88
417
104
595 15 488
559 887 901
114 634 708 695 272 765
989 760 827 81 134 434 522 261 857
743 107 80 518
109 419 386 729 17 932
645 867 778 555 391 325
342 422 247 452 766 691 106 746
447 585 526 796
837 835 826 461 72 916 819 807 491
75 59 91 113 458 783 14 328
266 155 513 177 740 694 45 298 293
847 877 117 489
174 948
788 900 344 692 827
119 885 185 275 490 622 869
729 837 693 715 900 918 931
454 813 198 137 126 271 612 605 838 888
477 440 108 972 48 549
397 283 43 925 879 779 273 594 326
48 111 327 807
252 420 554 929 390 137
709 149 90 484 139 99 433 858
806 453 965 387 523 13 15 525 230 684
709 728 205 653
508 66 866 16 519 558
102 186 765 782 362 776 930
597 304 267 76
522 383 894 746 109 112 818 780 590
601 406 699 741 274 808 580 735 766 949
799 457 917 704 899919
222 486 209 586 906 178 781 168 673 868
655 884 586 389 797
388 79 524 297 199
343 23 595 890 510 345 971 606 12 611 828 889
502 454 184 142 46 236 642 745
64 633 880 421 553 837 961
983 853 554 773 814 838 611 47 262 294 929
97 415
691 110 593 859
84 719 432 928 520
62 911 212 524 523
150 871 658 527 77 111 865 966 107 950
749 470 817 727 550 806
478 44 416 710
610 571 456 764 11 898
359 949 883 742 809 522 521 557 296 621 714 960
439 970 920
864 358 785 455 179 295
208 437 918 110 173
820 550 687 422 183 361 552 607 77 775 890 867
264 585 701 881 346 587 266 928
844 823 78 683
950 674 525 592 589
189 610 138 652
592 211 388 192 816 10 581 231 798 829 836
245 882 431 736 767 860
966 521 181 967 969 726 204 951
295 864 839 927 705 959
158 646 180 182 810
670 253 423 551 556551
856 711 546 674 897
598 410 32 181 545 743 550 608 141 235 169 263 612 744
867 70 763 547 921 927
838 805 254 488 549 968 108 200 643 805
381 654 919 347 548 526 9 109 891
14 588 591 265 866
539 544 815
430 360 609
131 213 811 552 555 958
918 725 553 620
569 37 543 863 264 713
424 926 588 774 896
540 814 527 554 172 861 835
857 538 348 812 590 8 582 952
926
623 560 542 139 830
716 541 712 744 813 682
504 762 840 920 589 140 651 799 922
448 862 349 234 232 768
259 429 724 203 737 957
127 892 865
218 706
537 925 7
224 937 425 350 528 613 743 804 925
193 359 170 675 895
766 370 159 587
921 723 171 583 233201 644
438 170 428
984 970 536 426 853 6 619
559 332 965 713 861 529 924 584 862 834 953
761 351 745 202 923 956
122 922 712 773
923 722 831 864 924
977 535 530 5 586 894
841 854 585 650 893
531
860 358 852 614 681 800
207 427 352 534 533 532 855
769
4 738 803
836 714 856 3 721 851 645 707 742
860 760 859 618 676 863 954 955
387 290 746858 615 833
135 622 857
476 946 353 354 357 850
608 720 711 772
908 757 617 649 832
927 355 715 356 747 849 616 680
756 759 848 646 802
842 801
1000 12 719 2 677 708 739 770 741
327 755 716 847748 648
924 758 754 751 718
717 710 771
753 752 647 679
750 846
374 103 749
863 843 678 740
844 845 709
757
737
403
905
963 523
N = 1000, k̄ = 4 N = 1000, k̄ = 2 N = 961, k̄ = 4
Erdös-Rényi periodic ring periodic 2D lattice
1 1 1
%(µ)
0 0 0
-5 -3 -1 1 3 5 -5 -3 -1 1 3 5 -5 -3 -1 1 3 5
µ µ µ
Figure 24. Adjacency matrix eigenvalue distributions %(µ) of the three further graphs,
to emphasise
R that the shape of these distributions can vary considerably, which, via the
moments dµ µ` %(µ), reflects the different statistics of closed paths in these graphs. The
Erdös-Rényi random graphs will be the subject of a subsequent section of these notes.
1 `
From the proof of (79) we know that for any integer ` > 0: dµ µ` %(µ|A) =
R P
N i (A )ii .
If ` > 2 this immediately gives us dµ µ` %(µ|A) = N1 L` (A).
R
• Claim: if the eigenvalue spectrum of the adjacency matrix A of a non-directed N -node
graph is symmetric, i.e. if %(−µ|A) = %(µ|A) for all µ ∈ IR, then this graph has no
closed paths of odd length (no triangles, no pentagons, etc).
Proof:
We use the previous result, and choose ` = 2m + 1 with m ∈ IN:
Z ∞
1 Z∞
L2m+1 (A) = N dµ µ2m+1 %(µ|A) = N dµ µ2m+1 %(µ|A) + (−µ)2m+1 %(−µ|A)
−∞ 2 −∞
1 Z∞
= N dµ µ2m+1 − µ2m+1 %(µ|A) = 0
2 −∞
340175
481 430
45
447 776
594
811 843 255 155 123 124
688 254 256 154 156
186 187 92
80 468 529 253 250 249 248
727 999 122 91 125 93
1000 209 185 60
474 247 208 61
887 997 998 251 210 257 218153
772 95 200 217 29 94 62
996 207 90 59
28 30
990 211 473 201 121
720 995 252 199 184 188 157
686 991 246 206 216 126
994
258 202 3163
647 992 212 152 219 189 27
475 249 220 58 95
475 907 989 158 127
391 789 205 203 89
993 472 505 248 251 96 64 32
161 160 213 245
346 131 198 504
333 711 215 250 65
570 698 637 204 183 120 97
999 405 476 638 506 259
636 128
503 190 159 66 34
982 162 635 33 1
284 124 130 214 674 247 26 35
389 159 988675 639 282 221
759 132
160 330 244 634 502 151 4 3
947 113 315 725 673 57
626 280 252 98 67 36 5
230 722 899 2
471 676 633
723 761 129 163 507 129
477 197 625 281 88 160
519 753 151 869 672 215 640 260 214
413 832 133 243 627 279
578 205 158 374 283
985 763 987 501 246 191 6
512 900 898 632
444 452 182
111 357 119 68 37
661 677 538
473 128 628 222 569
671 216 242 313 99
85 164 478 25
641 373 952 624 278 570
685 975 508 500 631 506
328 134 375 953 253 601
165 629 130 537
157 470 479 314 507 600
173 697 15 901 986 196 951 539
828 261 150 284 56 7
991 897 241 161
952 898 670 245
87 127 217 480 678 213 311 312 568
327 954 630 475
808 167 307 21 499 474 505
762 329 642 38 571 632
49 768 481 623 950 87 192 602
815 791 277
465 165 372 240 310 315 69 631
269 822 930 135 902 985
171 976 509 443 536 508 599
100 669 156 181
619
878 987 442 476 540
638 684 326 376 223
998 664 182 755 891 218 485 100
535 420 484 473 633
195 949 498 118 411
126 896 482 469 239 663
8 713 233 234 309 344 345 285 410 567
553 9 974 643 262 347 379 444 603 662
436 144 330 955 679 24 346 254 572
882 486 244 131 504
216 668 50 622 235
400 241 289 903 276 378 630
752 267 683 60 325 425 984 49 232 441 8
262 136 487 51 412 634
617 971 166 316
852 325 483 238 212 348 380 509
609 666 564 256 155 219 488 371 497 236 149
343 162 664
61 948 598
944 248 535 477 541 693
902 48 55 409
510 290 308 342 472
39 314 888 739 667 644 377 39 661 694
876 143 602 613 995 125 52 496
707 839 620 482 341 445
678 274 904 895 489 377 231
293 331 237 193 665
187 317
933 136 612 194 495 289 341
580 24 581 172 468 413 566
706 137 86 604
524 324 220 180 376 440 70 724
215 490 494 621 275 349 503 629
693 480 893 71 47 680 291 573 692
792 101 154 983 947 243 286 381 635 695
936 840 780 167 221 956
392 457 702 666 493 263 224
222 53 375 408 510
821 491 340
164 230 307
531 774 645 492 795 288 117 478
316 38 223 101 725
128 309 238 905 696723
115 275 124 597 660
489 224 370 796 23 534 542
367 201
567 783 649 662 794 255 471 666
311 294 332 661 292 211 446
291 809 959 379 323 138 663 894 225 511
355 946 374 132 755
323 896 156 46 229 318
536 574 665 28 339 9
385 696 412 220 226 148
635 467 407 414 691 726
191 493 174 575 153 193 228 793 54 29 274 373 439
166 145 745 227 378 287 350 382
494 664 306 54 754
92 125 459 646 573 982 620 403 565 628
956 797 163
892 600 917 168 660 572 681 502
55 555 371 736 574 372 511 605 722 756
958 369 561 217 94 906 293 242 40 479 636 697 727
169 54 485 27 287
769 960 123
322 139 333 571 957 574
909 404 338 179
424 264 406 194
5 401 500 786 792 945 85
464 921 351 297 575 45 30
280 626 429 659 785 786
583 588 893 91 371
562 369 402 470 447 667 753
681 292 734 180 152 55 757
506 329 647 570 90 512 71 533 596
243 57 903 659 286 438
778 294 305 225 543
916 140 466 798 319 690
116 256 415
499 398 96 405 273 210 405
277 363 874 798 981 26 728
695 58 349 907321 334 576 379 22 351 721
169 192 337 383 787
997 680 569 791 370
849 910 89 619 102 758
421 886 92 784
630 525 934 140 122 682 31 944 480 816
845 322
152 870 698
427 533 648 658 44 401 404 501 512
339 442 151 295 147 627 752
154 675 68 715 577 56 10
483 116 406 437 564 817
913 744751 276 141 568 958 241 53 133
859
402 455 939
540 353 285 892 265 285 288 788
82 236 590 951 880 335 513 369 403 469
978 922 682 781 88 304 448
105 71426 528 183 730 320 93 799 637
25 606 783 815
107 279 908 657 465 790 980 336 658 759
649 368 407 178 575
665 393 526 296 164
288 396 133 360 382 656 578 32 729
800 74 185 616 260 150 43 940 943 41 818847
534 46 170 84 320 532 668 689
831 356 199 272 402 436 416
308 547 584 672 16 758 567 400 720
299 142 121 57 938 481 789
76 942 226 582 530 380 544 595
692 232 240 336 191 368 195 257 352 751
509 605 233 123 866 861 618 941 384
558 650 992 814
650 828 829 94 408 683 846
784 914 655 87 209
915 319 827 297 284 115 848
51 487 282 401 468 500
426 577 690 42 226 72 513 699
618 149 514 335 819
895 962 579 33 24 435 449 782
941 2 802 969 909 566 891 800 21
912 954 206 22 3 654 959 979 942 303
411 544 652 474 296 464 830
35 463 414 143 826 789 266 937 760 790
377 626 878
129 42 651 399 367
361 409 58 240 146 289
237 1 628 994 337 41 563 845
660 263 171 298
7 53 795 95 400 103 849
445 572 931 653 565 52 813 877
378 460 306 754 458 214 50 148 120 318 367 434 482 730
86 820
228 928 824 148 615 40 11 417
157 731 652 34 467 657
138 825 831
249 144 283 271 321 531
639 710 539 404 568 190 334 450 607 638 719 879
319 286 738 456 910 381 617 684 936 177
726 39 580 410 23 750
923 564 67 134 576 688
257 967 354 663 537 299 366 499 669
89 515 978 801 399 433 353 385 876
338 38 398 83 258 844 850
662 318 640 501 589 298 321 147 317 35 545 781 791 909
817 78 69 463 59
362 79 130 223 668 939 37 302 594 908
973 904 834 890 96 36 66 42 514 821
765 145 761
372 671 960 300 788 267 165
352
721 104 466 700
712 93 375 637 119 146 172 563 303 302 208 880
195 899 34 591 435 227 85 301 432 451 812
231 700 543 310 832 411 68 483
28 18 384 824 304 227
938 466 255 311 309 282 398 114
316 305 935 418
312 278 565 770 911 306
308 22 65 365 333 20 196 875 907851 910
641 350 312 307
579 397 73 290 939
741 20 807 797 339 516 685 562 625
453 225 450 581 731 940
471 17 977 69 60 239
548 418 818 399 366 431
748 97 498 843
161 234 742 879 184 313 562 412 802 465 822
557 862 315 189 616 452 792
855 732 545 868 382 145 530 881
972 948 317 830
677 624 703 462 397 51 386
229 120 551 659 118 64 270 749
449 70 322 419 656 718 780
563 84 852
906 938
648 702 771 517 268 364 104 911
940 980 173 823 889 833 787 934 281 12
881 981 413 354 941
338 961 21 301 687
364 314 762 874
272 479 873 912 772 396 61 430 484 515 639 670
669 819 724 546 608 811
423 561 332 176 464 577
507 340 71 259 420
407 190 196 453
395 386 179 704 63 882
607 305 98 396 82 593
596 801 629 439 701 773 976 686 497 701
344 10 36 250 270 414 937
469 434 718 302 872 582 518 803 135 823
443 56 498 770 363 421 842 912
901 935 492 117 853
872 932 73 874 43
331 926 328 429 905 942
334 141 467 31 889 72
258 336 636 83 280
505 202 810 347 955 779 440 560 383 933 20 62 463 207 422 387 732 793
326 462 446 261 787 461 188 365 615 395
11 576 395 228 561
542 244 774 423 883
177 142 689 822 834 394 113 454 529
656 653 643 438 174 700 269 166 291 873
733 968 871 415 786 19 393 624
705 913
957 888 519 600 362
99 485 779
611 197 740 441 341 962 331 424 936
606 121 599 428 392 748 913
303 433 875 810
538 885 694 769 73 462 496 74 197 943
310 514 431 559 238 355 763
703 975 687 516 323 717 854
242 842 599 804
627 116 82 279 19 388 824 904
884 163 735 734 655
335 29 441 775 425 391 841 884
19 676 919 235 153 437 583 50 300 686
848 176 194 883 419 408 376 442 699 736 601 269 455
632 287 932 427 144 547
833 365 870 416 733 394 390 389
604 897 118 313 361
394265 717 979 348 41 750 558 598 426 671
390 443 461 578 794 914
30 706 100 74 384 609 640 872
920 625 515 112 876 460 520 13 592 935 944
644 964 821 737 702
679 865 988 790 667 614 914 187 614 105
146 491 517 175 81 785 270 732 260
829 873 835 18 495 528
566 756 953 549 768 278
511 929 486
45 63 825 436 698 342 364 733 903
83 846 603 552 887 602 81 855 885
409 688 805 175 456
110 239 25 444 115 460 330
518 986 301 869 776 963 75 560
204 417 557 597 360 356 778 809 915
541 593 735 825
210 472 731 974
106 642 812 80 393 764 840 945
33 556 101 44 934
673 796 738 76 18
6 490 450 931 136 292 747
704 17 517 623 871
281 86 877 77 457 494
804 631 380 65 707 697 79 78 584
200 496 98 532 445 459 229 324
503 108 277 521 112 206 795
428 373 793 221 603 359 716 902
495 368 435 271 385 458 299 886
858 621 162 459 767 915 689 916
324 777 820 596 487 357 856 946
337 875 451 449 176 868
767 943 203 854 320 418 784 730 806 527 654
246 794 775 546 102 167 358 548 685
188 747 13 114 777 186 836 556 16 49 933
657 168 343 613 392 493 75
4 47 771 990 451 826
497 993 106 886 696 198
27 40 651 446 739 329
708 237 579
178 268 672 703 839
300 520 764 67 945 219 105 973 591 808
841 996 132 103 964 363 870
448 276 690 143 14 610 641 734
587 878 930 604 492 777 917 947
728 88
417
104
595 15 488
559 887 901
114 634 708 695 272 765
989 760 827 81 134 434 522 261 857
743 107 80 518
109 419 386 729 17 932
645 867 778 555 391 325
342 422 247 452 766 691 106 746
447 585 526 796
837 835 826 461 72 916 819 807 491
75 59 91 113 458 783 14 328
266 155 513 177 740 694 45 298 293
847 877 117 489
174 948
788 900 344 692 827
119 885 185 275 490 622 869
729 837 693 715 900 918 931
454 813 198 137 126 271 612 605 838 888
477 440 108 972 48 549
397 283 43 925 879 779 273 594 326
48 111 327 807
252 420 554 929 390 137
709 149 90 484 139 99 433 858
806 453 965 387 523 13 15 525 230 684
709 728 205 653
508 66 866 16 519 558
102 186 765 782 362 776 930
597 304 267 76
522 383 894 746 109 112 818 780 590
601 406 699 741 274 808 580 735 766 949
799 457 917 704 899919
222 486 209 586 906 178 781 168 673 868
655 884 586 389 797
388 79 524 297 199
343 23 595 890 510 345 971 606 12 611 828 889
502 454 184 142 46 236 642 745
64 633 880 421 553 837 961
983 853 554 773 814 838 611 47 262 294 929
97 415
691 110 593 859
84 719 432 928 520
62 911 212 524 523
150 871 658 527 77 111 865 966 107 950
749 470 817 727 550 806
478 44 416 710
610 571 456 764 11 898
359 949 883 742 809 522 521 557 296 621 714 960
439 970 920
864 358 785 455 179 295
208 437 918 110 173
820 550 687 422 183 361 552 607 77 775 890 867
264 585 701 881 346 587 266 928
844 823 78 683
950 674 525 592 589
189 610 138 652
592 211 388 192 816 10 581 231 798 829 836
245 882 431 736 767 860
966 521 181 967 969 726 204 951
295 864 839 927 705 959
158 646 180 182 810
670 253 423 551 556551
856 711 546 674 897
598 410 32 181 545 743 550 608 141 235 169 263 612 744
867 70 763 547 921 927
838 805 254 488 549 968 108 200 643 805
381 654 919 347 548 526 9 109 891
14 588 591 265 866
539 544 815
430 360 609
131 213 811 552 555 958
918 725 553 620
569 37 543 863 264 713
424 926 588 774 896
540 814 527 554 172 861 835
857 538 348 812 590 8 582 952
926
623 560 542 139 830
716 541 712 744 813 682
504 762 840 920 589 140 651 799 922
448 862 349 234 232 768
259 429 724 203 737 957
127 892 865
218 706
537 925 7
224 937 425 350 528 613 743 804 925
193 359 170 675 895
766 370 159 587
921 723 171 583 233201 644
438 170 428
984 970 536 426 853 6 619
559 332 965 713 861 529 924 584 862 834 953
761 351 745 202 923 956
122 922 712 773
923 722 831 864 924
977 535 530 5 586 894
841 854 585 650 893
531
860 358 852 614 681 800
207 427 352 534 533 532 855
769
4 738 803
836 714 856 3 721 851 645 707 742
860 760 859 618 676 863 954 955
387 290 746858 615 833
135 622 857
476 946 353 354 357 850
608 720 711 772
908 757 617 649 832
927 355 715 356 747 849 616 680
756 759 848 646 802
842 801
1000 12 719 2 677 708 739 770 741
327 755 716 847748 648
924 758 754 751 718
717 710 771
753 752 647 679
750 846
374 103 749
863 843 678 740
844 845 709
757
737
403
905
963 523
N = 1000, k̄ = 4 N = 1000, k̄ = 2 N = 961, k̄ = 4
Erdös-Rényi periodic ring periodic 2D lattice
0.6 0.6 0.6
0.4 0.4 0.4
%Lap (µ)
0.2 0.2 0.2
0 0 0
-15 -10 -5 0 5 10 15 -15 -10 -5 0 5 10 15 -15 -10 -5 0 5 10 15
µ µ µ
Figure 25. Laplacian matrix eigenvalue distributions %Lap (µ) of the three graphs of Figure
24, which indeed show nonnegative eigenvalues only. It is clear the the eigenvalue spectra
of the adjacency matrix and of the Laplacian matrix sometimes will and sometimes will not
be similar. In the exercises we will find out why the Laplacian spectra in the middle and
right graph are of the same shape as their adjacency matrix spectra in Fig. 24.
Some examples of adjacency matrix eigenvalue spectra for non-directed graphs that we
have already inspected earlier are shown in Fig. 23. Further examples are shown in Fig. 24,
to emphasise the large variability in spectra one should expect.
5.4. Spectra of Laplacian matrices
We saw that an alternative spectral characterisation of nondirected graphs, especially
relevant for graphs describing diffusive processes, is based on the eigenvalues of the so-called
Laplacian N × N matrix L = {Lij }, rather than those of the adjacency matrix A.
• Definition: the Laplacian matrix L of an N -node graph with adjacency matrix A is
46
defined by the entries
Lij = ki (A)δij − Aij (83)
Since the Laplacian is a symmetric matrix, it must have real-valued eigenvalues.
• Claim: all eigenvalues of a Laplacian matrix L of a graph are nonnegative.
Proof:
We show that for any x ∈ IRN one will find x · Lx ≥ 0:
X X X
x · Lx = xi ki (A)δij − Aij xj = xi ki (A) − Aij xj
ij i j
X X X X
= xi Aij − Aij xj = xi Aij (xi − xj )
i j j ij
1X 1X
= xi Aij (xi − xj ) + xj Aji (xj − xi )
2 ij 2 ij
1X 1X 1X
= xi Aij (xi − xj ) − xj Aji (xi − xj ) = (xi − xj )Aij (xi − xj )
2 ij 2 ij 2 ij
1X
= Aij (xi − xj )2 ≥ 0
2 ij
Any eigenvector x of L with eigenvalue µ < 0 would have given x · Lx = µx2 < 0, in
contradiction with the above. Hence L cannot have negative eigenvalues.
• Claim: the Laplacian matrix L of a graph always has at least one eigenvalue µ = 0.
Proof:
Define u = (1, 1, . . . , 1), and show that it is an eigenvector with eigenvalue zero:
X X
(Lu)i = Lij uj = ki (A)δij − Aij ).1 = ki (A) − ki (A) = 0 (84)
j j
• Claim: the multiplicity of the kernel of a Laplacian matrix L of a graph (i.e. the
dimension of the eigenspace corresponding to eigenvalue zero) equals the number of
disconnected components in the graph.
Proof:
1
Consider a vector x with eigenvalue zero. Using the identity x · Lx = Aij (xi − xj )2
P
2 ij
derived in the previous proof, it follows that for such an eigenvector
Aij (xi − xj )2
X
0=
ij
Hence ∀(i, j) : Aij = 0 or xi = xj . For each connected component V 0 ⊆ {1, . . . , N } of
47
0
our graph we have thereby found an eigenvector ~xV ∈ IRN with eigenvalue 0:
0
xVi = 1 if i ∈ V 0
(
0
connected component V : 0
/ V0
xVi = 0 if i ∈
Imagine there was a further zero eigenvalue, with an eigenvector x that is not one of
the above. Again we would find 0 = ij Aij (xi − xj )2 . We can now decompose
P
Aij (xi − xj )2
X X
0=
V 0 i,j∈V 0
Hence we would again get, for any connected component V 0 : xi = xj for all i, j ∈ V 0 .
But that implies that x is a linear combination of the eigenvectors above, which is
not possible. Hence the dimension of the kernel of L, i.e. the number of independent
eigenvectors with eigenvalue zero, is exactly the number of connected components.
The above features of the Laplacian matrix allow us to predict immediately the stationary
state of diffusion processes. For instance, from expression (72) we may now conclude that
in the stationary state z(∞) = limt→∞ z(t):
1 X
f or each connected component V 0 : ∀i ∈ V 0 : zi (∞) = 0 zj (0) (85)
|V | j∈V 0
(see exercises for proof). In Fig 25 we show the eigenvalue spectra %Lap (µ|A) of the matrices
shown earlier (with their adjacency matrix eigenvalue spectra) in Fig. 24.
48
6. Random and pseudo-random graphs
6.1. Random graphs as ‘null models’
The need for ‘null models’. We have seen many ways to quantify network topologies. The
values we find for these quantifiers in a network, however, need to be interpreted. We need
to know what values we would have expected to find by default or typically. If we observe
that a graph has a Poissonian degree distribution, should we be excited? If we find that
the number of triangles in an N -node graph equals N/5, is this a large or a small number?
Which features of adjacency matrix spectra are common to most networks, and which are
informative and special? We lack a yardstick against which to measure what we see.
We can define ‘typical’ values as those that we would find in a ‘null model’, which we
define as a random graph that is otherwise similar to the network at hand. But how do
we define ‘similar’ ? Observations in a null model will depend on which features of the real
network we imposed upon its random counterpart – the devil is in the detail. For instance,
in constructing a measure for modularity, we compared observations in a network to what
we would expect from a randomly generated graph with the same degrees as the observed
one. We could have chosen other quantities than degrees to be copied to our null model ...
• Definition: a random graph ensemble {G, p} is defined as a set G of adjacency matrices
A, together with a measure p that specifies a probability p(A) for each A in G.
• Definition: ensemble averages of observable quantitative features f (A) of random graphs
are defined as X
hf i = p(A)f (A) (86)
A∈G
In this section we first define and study the simplest nontrivial random graph ensemble, the
Erdös-Rènyi model. Later we turn to more systematic ways of defining and constructing
random graph ensembles to serve as null models.
6.2. The Erdös-Rènyi model
Definition and basic properties. The Erdös-Rényi (ER) model is the random graph ensemble
in which G is the set of all simple nondirected N -node graphs, and all links are drawn
independently, according to p(Aij = 1) = p? and p(Aij = 0) = 1 − p? , with p? ∈ [0, 1]:
G = {A ∈ {0, 1}N ×N | Aij = Aji and Aii = 0 ∀i, j ≤ N } (87)
N h i
p? δAij ,1 + (1 − p? )δAij ,0 ,
Y
p(A) = (88)
i<j=1
We have to be careful to distinguish between averages that are defined for a single graph,
such as k̄(A), and averages over the ensemble, to be written as h. . .i, which are average
values of graph features calculated over randomly generated graph instances A.
49
• Claim: for graphs generated in the ER ensemble , the average value of the average
degree k̄(A) = N −1 ij Aij equals p? (N − 1).
P
Proof:
X 1 X X 2 X 2 X X
hk̄(A)i = p(A) Ars = p(A) Ars = p(A)Ars
N rs N r<s N r<s
A∈G A∈G A∈G
N h
2 X X i
p? δAij ,1 + (1 − p? )δAij ,0
Y
= Ars
N r<s i<j=1
A∈G
1 1 h
2 X X ? ?
i
p? δAij ,1 +(1−p? )δAij ,0
Y X
= Ars [p δArs ,1 +(1−p )δArs ,0 ]
N r<s Ars =0 i<j, (i,j)6=(r,s) Aij =0
2 X ? 2p? X 2p? 1
= p .1 = = . N (N − 1) = p? (N − 1)
N r<s N r<s N 2
Note: hki is the average over the ensemble of the average degree k̄(A) of its graphs, i.e.
hki = A∈G p(A)k̄(A). Individual random graphs A generated according to (88) will
P
generally have k̄(A) 6= hki.
• Claim: the Erdös-Rényi ensemble assigns equal probabilities to all graphs with the same
number of links.
Proof:
Since Aij ∈ {0, 1}, the probabilities (88) can be written in the alternative form:
1
Yh i P P
p(A) = (p? )Aij (1 − p? )1−Aij = (p? ) i<j
Aij
(1 − p? ) 2 N (N −1)− i<j
Aij
(89)
i<j
Hence the dependence of p(A) on A can indeed be expressed fully in terms of the
P
number L(A) = i<j Aij of links in A, via
p(A) = (p? )L(A) (1 − p? )N (N −1)/2−L(A) (90)
• Claim: the graph probabilities (88) of the ER ensemble can equivalently be written as
N
" ! #
Y hki hki
p(A) = δAij ,1 + 1 − δAij ,0 (91)
i<j=1 N −1 N −1
Proof: This follows directly from the above result hki = p? (N − 1).
In the ER ensemble we control the likelihood of graphs via just one graph observable, which
can either be k̄(A) or the number of links L(A) (one follows from the other), and all graphs
with the same value for this parameter are equally probable. In spite of this superficial
simplicity, analysing this model turns out to be less than trivial.
50
• Claim: the average clustering coefficient Ci = hCi (A)i of any node i in graphs generated
from the ER ensemble (88), with the definition of Ci (A) given in (14), is
hCi (A)i = p? [1 − (1−p? )N −1 − p? (N −1)(1−p? )N −2 ] (92)
Proof:
We use definition (14), and have to be careful to distinguish between ki (A) < 2 and
ki (A) ≥ 2. To handle this implicit conditioning on the degree value we use the integral
Rπ
representation of the Kronecker δ-symbol (see 8.5), δnm = (2π)−1 −π dω ei(n−m)ω :
* + * P +
X X Air Ars Asi
r6=s
hCi (A)i = δk,ki (A) Ci (A) = δk,ki (A)
k≥0 k≥2 ki (A)(ki (A) − 1)
1
X X
= δk,ki (A) Air Ars Asi
k≥2 k(k−1) r6=s
*Z +
X 2 X πdω iω(k−Pj Aij )
= e Air Ars Asi
k≥2 k(k−1) r<s −π 2π
* +
2 X Z π dω
eiωk Air Ars Asi e−iωAij
X Y
=
k≥2 k(k−1) r<s, r,s6=i −π 2π j6=i
* +
2 X Z π dω Y
eiωk Ars Air e−iωAir Ais e−iωAis e−iωAij
X
=
k≥2 k(k−1) r<s, r,s6=i −π 2π j ∈{i,r,s}
/
So far we have only substituted definitions, and rearranged factors such that entries of
the adjacency matrix are grouped together. Now we do the actual ensemble averages.
The measure p(A) in the ER ensemble (88) factorises over the links, reflecting the fact
that they are indeed generated independently, which means that the average over p(A)
above simplifies to so the above can be reduced to the product of ensemble averages:
* +
Y
−iωAir −iωAis −iωAij
= hArs ihAir e−iωAir ihAis e−iωAis i he−iωAij i
Y
Ars Air e Ais e e
j ∈{i,r,s}
/ j ∈{i,r,s}
/
? ? −iω 2 ? −iω ? N −3 ? 3 −2iω ? −iω ? N −3
= p (p e ) (p e +1−p ) = (p ) e (p e +1−p )
Next we use Newton’s binomium formula to work out the quantity (p? e−iω +1−p? )N −3 :
N −3
* +
−iωAir
−iωAis
Y
−iωAij N −3 ? ` −`iω
= (p? )3 e−2iω (1−p? )N −3−`
X
Ars Air e Ais e e (p ) e
j ∈{i,r,s}
/ `=0
`
N −3
N −3 ? `+3 −(`+2)iω
(1−p? )N −3−`
X
= (p ) e
`=0
`
We insert this into our expression for hCi (A)i, use 1 = 21 (N −1)(N −2) , and
P
r<s, r,s6=i
do some simple cleaning up:
−3
(N −1)(N −2) Z π dω iωk NX N −3 ? `+3 −(`+2)iω
(1−p? )N −3−`
X
hCi (A)i = e (p ) e
k>2 k(k−1) −π 2π `=0
`
51
−3
X (N −1)(N −2) NX N −3 ? `+3 ? N −3−`
Z π
dω iω(k−`−2)
= (p ) (1−p ) e
k>2 k(k−1) `=0
` −π 2π
At this stage we use the integral representation of the Kronecker delta-symbol to get
rid of the ω-integral:
−3
(N −1)(N −2) NX N −3 ? `+3
(p ) (1−p? )N −3−` δk,`+2
X
hCi (A)i =
k>2 k(k−1) `=0
`
N −3
N −3 (N −1)(N −2) ? `+3
(p ) (1−p? )N −3−`
X
=
`=0
` (`+2)(`+1)
We now write explicitly the combinatorial factor, and clean up the various quantities
where possible:
N −3
(N −3)! (N −1)(N −2) ? `+3
(p ) (1−p? )N −3−`
X
hCi (A)i =
`=0 `!(N −3−`)! (`+2)(`+1)
N −3
(N −1)!
(p? )`+3 (1−p? )N −3−`
X
=
`=0 (`+2)!(N −3−`)!
N −3
N −1 ? `+3
(p ) (1−p? )N −3−`
X
=
`=0
`+2
N −3 N −1
N −1 ? `+2 N −1 ? `0 0
?
(p ) (1−p? )N −1−(`+2) = p? (p ) (1−p? )N −1−`
X X
=p 0
`=0
`+2 `0 =2
`
N −1
N −1 ? `0 0
= p? (p ) (1−p? )N −1−` − p? (1−p? )N −1 − p? (N −1)p? (1−p? )N −2
X
0
`0 =0
`
We then recognise that Newton’s binomial formula can be used to do the sum over `,
and proceed to our final result:
n N −1 o
hCi (A)i = p? p? + 1 − p? − (1−p? )N −1 − p? (N −1)(1−p? )N −2
n o
= p? 1 − (1−p? )N −1 − p? (N −1)(1−p? )N −2
The above proof is a useful exercise in the use of various bookkeeping tools, such
us summation formulae from Calculus, Newton’s binomial formula, and the integral
representation of the Kronecker delta-symbol. These tools will continue to serve us.
6.3. The Erdös-Renyi model in the finite connectivity regime
We are usually interested in large networks with a finite average degree – these tend to be
found in the real world. Therefore many properties of the ER ensemble have been studied in
the so-called finite connectivity regime, starting from (91), where: N → ∞ with hki finite.
It follows from a relation found earlier, namely hk̄(A)i = p? (N − 1), that in this regime
p? = O(N −1 ). The probability for an individual link to be present must indeed scale as
52
O(N −1 ) in order to have on average a finite number of partners per node in the system. We
now investigate properties of the ER ensemble in this finite connectivity limit.
• Claim: in the finite connectivity limit, i.e. for N → ∞ with hki fixed, the degree
distribution of the Erdös-Rènyi ensemble has the Poissonnian form
lim hp(k|A)i = e−hki hkik /k! (93)
N →∞
Proof:
X
lim p(k|A) = lim p(k|A)p(A|hki) (94)
N →∞ N →∞
A∈G
As always we manipulate all ensemble averages until they factorise over the bond
variables, since the entries of A are in the ER model distributed independently. Again we
use the symmetry and absence of diagonal elements of A, and the integral representation
of the Kronecker δ-symbol to achieve this:
1 X P 1 X Z π dω iωk −iω Pj Aij
lim hp(k|A)i = lim h δk, Aij i = lim e he i
N →∞ N →∞ N j N →∞ N −π 2π
i i
1 X Z π dω iωk −iω Pjs Asj δis
= lim e he i
N →∞ N −π 2π
i
1 X Z π dω iωk − 12 iω Pjs Asj (δis +δij )
= lim e he i
N →∞ N −π 2π
i
1 X Z π dω iωk −iω Pj<s Asj (δis +δij )
= lim e he i
N →∞ N −π 2π
i
1 X Z π dω iωk Y −iωAsj (δis +δij )
= lim e he i
N →∞ N −π 2π
i j<s
1 X Z π dω iωk Y X hki hki
= lim e δA,1 + (1− )δA,0 e−iωA(δis +δij )
j<s A∈{0,1} N −1 N −1
N →∞ N −π 2π
i
1 X Z π dω iωk Y h hki −iω(δis +δij ) i
= lim e 1+ (e − 1)
N →∞ N
i −π 2π j<s N −1
Next, since N → ∞ and hki is finite, we can use the expansion 1 + x = exp(x − 12 x2 +
O(x3 )). We also note that e−i(δis +δij ) − 1 = 0 unless either s = i or j = i or both, so
that j<s (e−i(δis +δjs ) −1) = O(N ) and j<s (e−i(δis +δjs ) −1)2 = O(N ) as N → ∞. Hence
P P
1 X Z π dω iωk Y N− hki hki2
(e−i(δis +δij ) −1)− 12 (e−iω(δis +δij ) −1)2 +O(N −3 )
lim hp(k|A)i = lim e e 1 (N −1)2
N →∞ N →∞ N −π 2π
i j<s
1 X Z π dω iωk+ hki P
(e−iω(δis +δij ) −1)+O(N −1 )
= lim e N j<s
N →∞ N −π 2π
i
1 X π dω iωk+ hki
Z P
(e−iω(δis +δij ) −1)+O(N −1 )
= lim e 2N j6=s
N →∞ N −π 2π
i
53
N = 50, hki = 5 N = 500, hki = 5 N = 5000, hki = 5
0.2 0.2 0.2
p(k)
0.1 0.1 0.1
0 0 0
0 5 10 15 0 5 10 15 0 5 10 15
k k k
Figure 26. Comparison between the theoretical prediction (93) for the average degree
distribution of infinitely large ER graphs (triangles) and the observed distributions in
random samples from the ER ensemble, for N = 50, 500, 5000 (histograms). Clearly,
for N = 500 the differences between actual degree distributions and the N → ∞ formula
are already small, and for N = 5000 they are more or less negligible. This means that
asymptotic results are useful descriptions of large but finite graphs.
1 X Z π dω iωk+ hki P
(e−iω −1)+O(N −1 )
= lim e N j6=i
N →∞ N −π 2π
i
1 X π dω iωk+hki(e−iω −1)+O(N −1 )
Z Z π
dω iωk+hkie−iω
= lim e = e−hki e
N →∞ N −π 2π −π 2π
i
The last step is the remaining integral over ω. It looks nasty, but is in fact simple.
Just expand exp(hkie−iω ) as a power series, and use the integral representation of the
Kronecker delta again:
−hki
Z π
dω iωk X hki` −i`ω −hki
X hki` Z π dω
lim hp(k|A)i = e e e =e eiω(k−`)
N →∞ −π 2π `≥0 `! `≥0 `! −π 2π
hki`
= e−hki δk` = e−hki hkik /k!
X
`≥0 `!
In Fig 26 we see that this asymptotic result (i.e. a formula derived for N → ∞) is accurate
already for large but finite graphs of size N ∼ 102 − 103 . In other words: in the finite
connectivity regime, size N ∼ 102 − 103 graphs appear to behave like infinite ones.
• Claim: in the finite connectivity limit, i.e. for N → ∞ with hki fixed, the average
clustering coefficients of the Erdös-Rènyi ensemble become
hki h i
hCi (A)i = 1 − e−hki − hkie−hki + O(N −2 ) (95)
N
Proof:
54
We substitute p? = hki/(N − 1) into (92) and expand the result for N → ∞, using
log(1 + x) = x + O(x2 ) and ex = 1 + x + O(x2 ):
hki h hki N −1 hki N −2 i
hCi (A)i = 1 − (1− ) − hki(1− )
N −1 N −1 N −1
hki h hki hki i
= 1 − e(N −1) log(1−N−1 ) − hkie(N −2) log(1−N−1 )
N −1
hki h hki −1 hki −1
i
= 1 − e−(N −1) N−1 +O(N ) − hkie−(N −2) N−1 +O(N )
N −1
hki h −1 −1
i
= 1 − e−hki+O(N ) − hkie−hki+O(N )
N −1
hki h i
= 1 − e−hki − hkie−hki + O(N −2 )
N
So in the finite connectivity scaling regime all clustering coefficients of typical Erdös-Rényi
graphs vanish for N → ∞, and the number of triangles per node is order N −1 . Using in
principle similar tools (but involving calculations that are more tedious), one can show that
large random graphs generated from the Erdös-Rényi ensemble (88) with fixed hki will be
locally tree-like (i.e. have a vanishing number of short loops per node) and will on average
have vanishing degree correlations,
for all (k, k 0 ) : lim hW (k, k 0 |A)i = [ lim hW (k|A)i][ lim hW (k 0 |A)i] (96)
N →∞ N →∞ N →∞
with W (k, k 0 |A) as defined in (36).
6.4. Generating functions
Many averages over the degree distribution p(k) of a graph or an ensemble of graphs can be
expressed in terms of the following generating function, calculation of which will reduce the
amount of work (and the likelihood or error) in our calculations:
• Definition: the generating function of the degree distribution is defined for x ∈ [0, 1] as
p(k)xk
X
G(x) = (97)
k≥0
d
We see that it obeys: dx
G(x) ≥ 0, with G(0) = p(0) and G(1) = 1.
• Claim: the degree distribution follows from its generating function via
1 dk G(x)
p(k) = lim (98)
x→0 k! dxk
Proof:
This follows directly from application of the Taylor expansion to the function G(x),
which tells us that G(x) = `≥0 `!1 G(`) (0)x` .
P
55
• Claim: all moments hk m i of the degree distribution, with m ∈ IN, follow from the
generating function via
d m
hk m i = lim x G(x) (99)
x→1 dx
Proof:
For m = 0 the claim holds trivially. We just work out the recipe on the right for m > 0:
d m d m X d m−1 X d
x G(x) = x p(k)xk = x p(k)x xk
dx dx k≥0 dx k≥0 dx
d m−1 X d m−2 X
= x p(k)kxk = x p(k)k 2 xk
dx k≥0 dx k≥0
= ......
d 0 X
p(k)k m xk = p(k)k m xk
X
= x
dx k≥0 k≥0
Setting x → 1 then leads to the above claim.
Let us work out the generating function (97) for some simple degree distributions, with
average degree hki = q ≥ 0:
• Claim: the generating function of the degree distribution for regular random graphs,
where p(k) = δqk , is
G(x) = xq (100)
Proof: this is trivial, in the sum over k we retain only the term k = q.
• Claim: the generating function of the degree distribution for Poissonnian random
graphs, i.e. where p(k) = e−q q k /k! with q ≥ 0 (like finitely connected ER ones) is
G(x) = e−q(1−x) (101)
Proof:
y k /k! = ey :
P
We do the sum over k in (106), using k≥0
X q k xk
G(x) = e−q = e−q eqx = e−q(1−x) (102)
k≥0 k!
• Claim: the generating function of the degree distribution for random graphs with
q k
exponential degree distributions, i.e. where p(k) = ( 1+q ) /(1+q) with q ≥ 0, is
1
G(x) = (103)
1 + q(1 − x)
P P
(see exercises for proofs that this distribution obeys k p(k) = 1 and k p(k)k = q).
56
Proof:
y k = 1/(1−y):
P
We do the sum over k in (106), using k≥0
1 X qx k 1 1
G(x) = =
1+q k≥0 1+q 1+q 1 − qx/(1+q)
1 1
= = (104)
1 + q − qx 1 + q(1 − x)
In the exercises we confirm for all three examples that they indeed obey G(0) = 0, G(1) = 1,
d
and limx→1 x dx G(x) = q.
6.5. The giant component in random tree-like graphs
Definition and general formula. We saw that in the finite connectivity regime the ER model
generates locally tree-like graphs. These have convenient mathematical features. The main
one is this: given the statistical features of a node i, those of the ki nodes in its environment
∂i can in leading order be taken as statistically independent, since each ‘branch’ of the tree
centred at i is connected to each other branch only via node i. See Figure 27. Here we
investigate locally tree-like random graphs with a given degree distribution p(k).
We consider the largest connected component LCC of a graph G (see definition in
section 2), and define f as the fraction of the N nodes in the graph that is in the LLC, so
size of the largest component : |LCC| = f N (105)
Note that f is then also the probability that a randomly drawn node from G is in the LCC.
• Definition: a graph G has a ‘giant component’ if |LCC| = O(N ), i.e. if f > 0 and of
order O(1).
Clearly, having a giant component will have a significant impact on processes running
on the graph. Therefore we would like to calculate f . Since each randomly drawn node has
degree distribution p(k), we may use the following simple argument
1−f = Prob(randomly drawn node not in LCC)
X
= p(k).Prob(neighbours of randomly drawn node with degree k not in LCC)
k
Since the graph is tree-like, the only possible correlations among local topological features
of nodes in a generation g are those caused by their common ancestor (if any), so
Prob(k neighbours are not in LCC) = (1 − f )k , and hence we find that f is the solution of
the simple equation 1 − f = k≥0 p(k)(1 − f )k , or equivalently
P
f = 1 − G(1 − f ) (106)
where G(x) is the generating function (97). Since G(1) = 1 we see that f = 0 is always
a solution of (106), describing a graph with a non-extensive largest component, since the
57
' $
∂i
i
& %
Figure 27. In locally tree-like graphs the number of short loops is vanishingly small, for the
vast majority of the nodes the local topology is that of a tree. Hence, starting from a node
i, we would find that the tree branches descending from i are nearly disconnected – they
connect only at site i. In this example p(k) = δk,3 . With non-regular degree distributions
we will see local randomness in this environment.
relative size of the giant component is f N . The next question is whether there are solutions
of (106) with f > 0.
The solution of equation (106) can be found graphically by intersecting the function
F (f ) on the interval f ∈ [0, 1] with the diagonal, since this intersection has f = F (f ), in
which
F (f ) = 1 − G(1 − f )
regular random graphs, hki = q : F (f ) = 1 − (1 − f )q
f initely connected ER graphs, hki = q : F (f ) = 1 − e−f q (107)
exponential random graphs, hki = q : F (f ) = qf /(1 + qf )
(where we used the generating functions calculated in the previous subsection). We observe
that regular graphs are a special case. Here for q = 1 all values f ∈ [0, 1] obey f = F (q),
and for q > 1 the value f = 1 is always a solution of f = F (q).
The result of plotting the functions F (f ) on f ∈ [0, 1] for the above choices for p(k),
and of solving numerically the equation f = F (f ) for hki = q ∈ [0, 6] is shown in Figure
28. In all three cases the system undergoes a percolation phase transition at hki = q = 1,
where the system switches from f = 0 (for q < 1) to f > 0 (for q > 1). Exactly at hki = 1
the networks develop a giant component. The size of this component is largest for regular
graphs, and smallest for the exponential ones.
Universality of the percolation transition. It is no accident that in all three examples above
58
random regular finitely connected ER random exponential
1 1 1
0.8 0.8 0.8
q =3 q =3
F (f )
0.6 0.6 0.6 q =3
0.4
q = 12 0.4 0.4
0.2 0.2
q = 12 0.2 q = 12
0 0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1
f f f
1 1 1
0.8 0.8 0.8
f
0.6 0.6 0.6
0.4 0.4 0.4
0.2 0.2 0.2
0 0 0
0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
hki hki hki
Figure 28. Top row: shapes of the function F (f ) for three random graph types with average
degree hki = q: regular graphs with p(k) = δkq , finitely connected Erdös-Rèyi graphs (for
q k
large N ) with p(k) = e−q q k /k!, and exponential graphs with p(k) = ( 1+q ) /(1+q). Solid lines
in each panel: F (f ) for q ∈ { 12 , 1, 32 , 2, 52 , 3}, from bottom to top. Dotted: the diagonal,
whose intersection point with F (f ) marks the value f that gives the relative size of the
largest connected component in the graph. Bottom row: corresponding expected relative
sizes of the largest connected component (i.e. solutions of F (f ) = f ) in each of the there
random graphs, shown as a function of the average degree hki. In all cases a giant component
appears in the graphs at hki = 1, which is interpreted as a percolation transition point.
the percolation transition occurs at the same point hki = 1. The transition point correspond
to the value of hki where the trivial solution f = 0 of F (f ) = f ceases to be unique, this event
is called a bifurcation of a new solution of (106). Figure 28 (bottom row) shows that, except
for the degenerate case of regular graphs, the transition is generally continuous, i.e. there
is no jump in the solution f when we vary hki. This prompts us to do a simple continuous
bifurcation analysis of (106) near f = 0, by expansion in powers of f :
k
k k
(−f )`
X X X
f =1− p(k)(1 − f ) = 1 − p(k)
k≥0 k≥0 `=0
`
59
0.9
0.8
hki = 2.0
0.7
0.6
Frac(dij ≤ d) hki = 1.8
0.5
0.4 hki = 1.6
0.3
0.2 hki = 1.4
0.1 hki = 1.2
0 ← hki = 1.0, 0.8, 0.6, 0.4, 0.2
0 20 40 60 80 100
Figure 29. The fraction of node pairs (i, j) in randomly generated ER graphs that are
found to have a distance dij ≤ d, shown versus d. Here N = 1000 and hki ∈ [0, 2]. One
observes clearly that there is a sharp transition at hki ≈ 1. For hki < 1 the fraction of node
pairs at a finite distance from each other is vanishing small. For hki > 1 this fraction all of
sudden becomes finite, which marks the emergence of the giant component in the graph.
k
(−f )`
X X
=1− p(k)
`≥0 k≥`
`
nX k k o
+ f2 + O(f 3 )
X X
=1− p(k) − f p(k) p(k)
k≥` k≥1
1 k≥2
2
k!
p(k)k − f 2 + O(f 3 )
X X
=f p(k)
k≥1 k≥2 2(k−2)!
1 X
= f hki − f 2 p(k)k(k−1) + O(f 3 )
2 k≥2
1 X
= f hki − f 2 p(k)k(k−1) + O(f 3 )
2 k≥0
1
= f hki − f 2 hk(k−1)i + O(f 3 ) (108)
2
So our equation for f can be written as
1
f 1 − hki + f hk(k−1)i + O(f 3 ) = 0 (109)
2
60
For sufficiently small f we may neglect the cubic term and conclude
hki−1
f = 0 or f = 2 (110)
hk 2 i−hki
It can be shown (see exercises) that always hk 2 i > hki unless we have a graph without
links. Hence, as soon as hk 2 i − hki < ∞ a new solution f > 0 bifurcates exactly when
hki = 1, irrespective of the shape of the degree distribution p(k). Only for power law degree
distributions, where hk 2 i = ∞, this bifurcation does not occur, and we have to evaluate
(106) in full to study whether and when a giant component may appear.
In Figure 29 we show that the predicted emergence of a giant component at a sharply
defined value of hki is real, for numerically generated random Erdös-Rènyi graphs of size
N = 1000, and with hki ∈ [0, 2]. We plot the fraction of node pairs (i, j) (with i 6= j)
that have a distance dij ≤ d, as a function of d. Clearly, there is a phase transition at
hki ≈ 1, where all of a sudden the typical distances between nodes in the graph become
finite, marking the creation of the giant component.
Note that all calculations in this subsection were based on the assumption that the
neighbours of any randomly picked node have degrees that are distributed independently.
Just giving the degree distribution of a graph is not enough, as we have already seen in e.g.
Figure 20; we need to specify the full ensemble probabilities p(A) to check when this assumed
degree independence holds. It is easy to construct graphs with hki > 1 (see exercises for an
example of a regular graph with hki = 2) without a giant component. For the Erdös-Renyi
ensemble, where we indeed have a fully specified p(A), a more precise calculation can be
done, and here (106) is indeed found to be exact in the limit N → ∞.
6.6. Tailoring topologies via maximum entropy random graph ensembles
The ensemble (88,91) is the simplest nontrivial graph ensemble, and many of its properties are
consequently rather different from those observed in real networks. Hence using the graphs
produced by (88,91) as a statistical ‘null models’ to quantify the relevance of observations
that we make in real networks is pointless – if our null model is too simple nearly anything we
measure will seem special. So we need to think about this in a more sophisticated manner.
Given an observed network with adjacency matrix A? , we want to build random graph
ensembles {G, p} that generate graphs with adjacency matrices A that are similar to A? .
How do we define similar? We choose specific measurements Ωµ (A? ), with µ = 1 . . . K, that
we want our graphs to inherit from A? , and demand that their values are either reproduced
by all graphs in the ensemble (via a hard constraint), or that they are reproduced on
average (via a soft constraint). See Figure 30. Abbreviating the set of chosen features
as Ω(A) = (Ω1 (A), . . . , ΩK (A)), this gives
hard constraints : graphs must have the features Ω(A? ) individually,
61
Ω(A? ) = Ω(A) for all A ∈ G with p(A) > 0 (111)
soft constraints : graphs must have the features Ω(A? ) on average,
Ω(A? ) =
X
p(A)Ω(A) (112)
A∈G
Both (111) and (112) give us conditions, but they do not yet specify the probabilities p(A)
in full, for that we need information-theoretic arguments. We want to construct an ensemble
{G, p} that builds in the chosen features Ω(A) but is otherwise strictly noninformative and
unbiased. Given a choice for the set G, this will be true only for the distribution p(A) that,
subject to the chosen constraints (111) or (112), maximises the Shannon entropy
X
S[p, G] = − p(A) log p(A) (113)
A∈G
The Shannon entropy defines the information content of a typical sample from the
distribution p(A). If we choose any p(A) other than the one for which the entropy is
maximal (subject to the chosen constraints), we would already know something about our
graphs in addition to the information contained in our constraints. In other words: we would
introduce an ad hoc bias into our graph ensembles. We now show how maximisation of (139),
subject to the constraints, leads us to unique formulas for our tailored graph ensembles.
Tailored random graphs with hard constraints. If we go for (111), we need only define p(A)
for all graphs A that obey Ω(A) = Ω(A? ). All other graphs are forbidden. We choose
the collection of allowed graphs to be our set G, and we take the functions Ωµ (A) to be
P
integer-valued. Maximisation of (139) subject to the constraint A∈G p(A) = 1, using
Lagrange’s method (see Appendix 8.8), then gives the following equations that are to be
solved simultaneously for {p(A)}:
∂ h i
p(A0 )
X
∀A ∈ G : 0= S[p, G] + λ 1 −
∂p(A)
A0 ∈G
∂ h i
p(A0 ) log p(A0 ) − λ p(A0 )
X X
= −
∂p(A)
A0 ∈G A0 ∈G
∂ h i
= − p(A) log p(A + λp(A) = − log p(A) − 1 − λ (114)
∂p(A)
Hence log p(A) = −1 − λ for all A ∈ G, or p(A) = e−1−λ . Normalisation tells us that
−1−λ
= |G|−1 . The end result is the following maximum entropy
P
A∈G p(A) = 1, hence e
ensemble, in which all graphs A that meet our constraints are equally probable
1
∀A ∈ G : p(A|Ω) = , Z(Ω) = |G| (115)
Z(Ω)
2
Z(Ω) ≥ 1 is the number of graphs in {0, 1}N that exhibit Ω(A) = Ω(A? ). We could also
2
choose to work with the set G = {0, 1}N of all N -node graphs, and forbid those graphs A
62
' $
all N -node graphs
' $
Ω1 (A) = Ω1 (A? )
' $
Ω2 (A) = Ω2 (A? )
' $
Ω3 (A) = Ω3 (A? )
• A?
&
& % %
&
& % %
Figure 30. Systematic tailoring of random graph ensembles, in order to generate random
graphs that resemble a given graph A? , by prescribing that a series of K measurements
Ωµ (A) give values identical to those found for A? . The larger K, the smaller the ‘box’
of graphs that meet all K imposed conditions, and the more similar the graphs in the
remaining box will be to A? . The probabilities p(A) assigned to all graphs A in each box
are determined via entropy maximisation.
that do not satisfy the constraints by assigning to them p(A) = 0. This givesk
δΩ(A),Ω(A? ) X
∀A ∈ G : p(A|Ω) = Z(Ω) = δΩ(A),Ω(A? ) (116)
Z(Ω)
A∈G
Global constraints such as nondirectionality or simplicity can in principle be incorporated
via the quantities Ωµ (A), but it is often more transparent to build such constraints into the
definition of G. Ensembles of the type (116) are also called microcanonical ensembles.
Tailored random graphs with soft constraints. If we choose the soft constraints (112),
we have to build any global constraints into the set G, and maximise the entropy (139)
subject to A∈G p(A) = 1 and A∈G p(A)Ωµ (A) = Ωµ (A? ) for all µ = 1 . . . K. The
P P
Lagrange maximisation methods will now involve K + 1 Lagrange parameters {λµ }, K of
which corresponding to the imposed constraints and with λ0 representing the normalisation
requirement A∈G p(A) = 1. Our equations for {p(A)} become
P
K
∂ h i
p(A0 ) + λµ Ωµ (A? ) − p(A0 )Ωµ (A0 )
X X X
∀A ∈ G : 0= S[p, G] + λ0 1 −
∂p(A)
A0 ∈G µ=1 A0 ∈G
Q
k We use the standard notation convention δx,y = µ δxµ yµ .
63
K
∂ h i
p(A0 ) log p(A0 ) − λ0 p(A0 ) − p(A0 )Ωµ (A0 )
X X X X
= − λµ
∂p(A)
A0 ∈G A0 ∈G µ=1 A0 ∈G
K
∂ h X i
= − p(A) log p(A) + λ0 p(A) + λµ p(A)Ωµ (A)
∂p(A) µ=1
K
X
= − 1 − log p(A) − λ0 − λµ Ωµ (A) (117)
µ=1
Thus the solution of Lagrange’s equations takes the following form, after having determined
P
the value of λ0 from the normalisation requirement A∈G p(A) = 1:
PK
λµ Ωµ (A)
e− µ=1 PK
λµ Ωµ (A)
e−
X
∀A ∈ G : p(A) = , Z(Ω) = µ=1 (118)
Z(Ω)
A∈G
in which the parameters {λ1 , . . . , λK } are found by solving the coupled equations
Ωµ (A? ) =
X
∀µ ∈ {1, . . . , K} : p(A)Ωµ (A)
A∈G
1 X − PK λν Ων (A)
= e ν=1 Ωµ (A). (119)
Z(Ω)
A∈G
One can show that equations (119) have a unique solution, but solving them numerically
is nontrivial. Even for simple nondirected graphs it involves sampling a space of size
|G| = 2N (N −1)/2 . Sometimes one can proceed analytically, if one chooses the Ωµ (A) wisely
and N is large. The ensembles (118) are also called exponential or canonical ensembles.
In the above derivations of the hard-constrained and the soft-constrained ensembles we
should in principle have included also the inequality constraints p(A) ≥ 0 for all A ∈ G
when maximising the Shannon entropy (139). However, it turned out in both cases that
even without imposing them explicitly, the inequality constraints are satisfied automatically
by the maximum entropy distributions. Hence they are obsolete.
Ensembles with constrained average degree. We first inspect ensembles of simple non-directed
graphs in which the only information we choose to carry over from the given graph A? is
the value k̄ = N −1 ij A?ij of the average degree, i.e. K = 1 and Ω1 (A) = N −1 ij Aij .
P P
It turns out that the maximum entropy ensemble of simple nondirected graphs in which
this average degree is imposed via a soft constraint is the Erdös-Rényi ensemble (88). See
exercises. Imposing the average degree as a hard constraint, in contrast, leads to the following
ensemble defined on the set G of all simple non directed N -node graphs:
1 X
p(A) = δP Aij ,N k̄ , Z(k̄) = δP Aij ,N k̄ (120)
Z(k̄) ij ij
A∈G
Each graph with average degree k̄ is equally likely, but for this ensemble not to be empty
we need N k̄ ∈ IN; this will automatically be the case if k̄ = N −1 i ki (A? ) for some N -node
P
64
graph A? . The factor Z(k̄) gives the number of graphs in G with average degree k̄.
Ensembles with hard-constrained degree sequences. The natural next step up is to impose
instead of only the average degree the values of all N degrees k = (k1 , . . . , kN ); typically
these would be the degrees of an observed graph A? . If the degrees k are imposed as hard
constraints, so we allow only for graphs A for which k(A) = k, we obtain an ensemble on
the set G of simple non directed graphs that is called the ‘configuration model’:
1 X
p(A|k) = δk,k(A) , Z(k) = δk,k(A) . (121)
Z(k)
A∈G
All graphs A that have the degree sequence k are equally probable, and all graphs that do
not have this degree sequence are assigned probability zero.
Ensembles with soft-constrained degree sequences. We obtain ensembles of simple nondirected
graphs with soft-constrained degree sequences from the general formulae (118,119) by
inserting the N degrees ki (A) for our observables Ωµ (A). We then find
PN PN
e− i=1
λi j=1
Aij
X −
PN
λi
PN
Aij
p(A) = , Z(k) = e i=1 j=1 (122)
Z(k)
A∈G
We can rewrite the probability distribution, using the symmetry of A:
PN 1
PN P
e− i,j=1
Aij λi
e− 2 i,j=1
Aij (λi +λj )
e− i<j
Aij (λi +λj )
p(A) = = =
Z(k) Z(k) Z(k)
1 Y −Aij (λi +λj ) 1 Y h −λi −λj i
= e = e δAij ,1 + δAij ,0 (123)
Z(k) i<j Z(k) i<j
The normalisation sum Z(k) then becomes
X Yh i h i
e−λi −λj δAij ,1 + δAij ,0 = e−λi −λj δAij ,1 + δAij ,0
Y X
Z(k) =
A∈G i<j i<j Aij ∈{0,1}
Yh i
= 1 + e−λi −λj (124)
i<j
In combination we can now write
Y h e−λi −λj 1 i
p(A) = δ
−λi −λj Aij ,1
+ δ A ,0 (125)
i<j 1 + e 1 + e−λi −λj ij
Finally, the equations (119) from which to solve the {λi } now become k` =
P
A∈G p(A)k` (A)
for all `. This gives
X Yh e−λi −λj 1 i
∀` ∈ {1, . . . , N } : k` = δ A ,1 + δ A ,0 k` (A)
1 + e−λi −λj ij
1 + e−λi −λj ij
A∈G i<j
N X
X Yh e−λi −λj 1 i
= A`r δ A ,1 + δA ,0
r=1 A∈G i<j 1 + e−λi −λj ij
1 + e−λi −λj ij
65
Figure 31. The Watts-Strogatz non-directed network model. Starting from a ring in which
each node is connected to its K ≥ 2 nearest neighbours (shown on the left, here with K = 4),
one subsequently replaces a given fraction p of the original nearest neighbour edges with
randomly selected alternative edges (not necessarily between neighbours in the ring). The
total number of edges remains 21 N K, and the average connectivity is always k̄(A) = K.
N
X X h e−λ` −λr 1 i
= A`r δ A ,1 + δA ,0
r=1 A`r ∈{0,1} 1 + e−λ` −λr `r
1 + e−λ` −λr `r
N N
X e−λ` −λr X 1
= −λ −λ
= λ` +λr
(126)
r=1 1 + e r=1 1 + e
` r
In the same manner one can impose further topological features (degree correlations, number
of loops, etc), via soft constraints, hard constraints, or even a mixture of the two.
7. Further topics
7.1. Watts-Strogatz and shifted-Poissonnian small-world networks
Various social experiments suggest that most people in the world are connected via only a
small number of ‘friends’ links – typically between 3 and 10. This phenomenon has been
called Six Degrees of Separation (after an idea in a 1929 story from a Hungarian writer). We
can indeed see in Figure 29 that in large random graphs one needs just hki ∼ 2 to achieve
such short typical distances. However, in real-world social networks we expect that physical
distances constrain us - we expect on average to have more friends living near us than friends
at the other side of the globe. The ‘small world’ networks aim to shed light on this question:
can we achieve the above short distances also in networks where most links are ‘local’ ?
The Watts-Strogatz construction. This non-directed network model interpolates between
a regular ring of N nodes with non-random links that are all short-ranged, and a random
graph. See Figure 31 for details of the construction. The relevant question is how the various
66
1 K = 2.08, 2.10
0.8
K = 2.06
0.6 K = 2.04
Frac(dij ≤ d)
0.4
K = 2.02
0.2
K = 2.00
0
0 5 10 15 20 25 30 35 40 45 50
Figure 32. The fraction of node pairs (i, j) that are found to have a distance dij ≤ d,
shown versus d, measured in small world graphs created by superimposing an Erdös-Rènyi
graph with average degree K −2 upon a ring with nearest-neighbour interactions only. The
combined graph has expected average degree hki = K. For K = 2 we would have only
short-range links. Here N = 1000 and hki ∈ [2.0, 2.1], and each curve refers to a single
graph (hence there are fluctuations). One observes a relatively sharp transition – at around
K = 2.07 where there is still only a small fraction of ‘long-range’ links – to graphs with the
short typical distances that characterise the small-world effect.
distance-related quantities in the graph depend on the fraction p of links that have become
random and long-range, as opposed to short-range.
Superposition construction. An alternative construction that is very similar but more easily
analysed mathematically is the following. Again all N nodes are initially placed on a ring.
We then (a) connect all nearest neighbours, and (b) superimpose on this an Erdös-Rènyi
graph with average degree hki = K − 2. Provided N is large and K is small, the likelihood
of a proposed random link coinciding with an existing nearest neighbour link on the ring is
negligible – if it happens we simply don’t add the random one. We then obtain the following
adjacency matrix A, built from the deterministic ring AD and the random ER graph AR :
Aij = AD R D R
ij + Aij − Aij .Aij (127)
AD
ij = δi,j+1 mod N + δi,j−1 mod N (128)
Y K −2 K −2
p(AR ) = δARij ,1 + (1− )δ R (129)
i<j N −1 N −1 Aij ,0
67
Inspection reveals (see e.g. Figure 32) that only a small fraction of the edges in the graph
need to be non-local to achieve the ‘small world’ effect.
7.2. Preferential attachment networks
Not all of the panels in Figure 18 are equally convincing straight lines, but the WWW, the
internet, and the power grid data do suggest power law degree distributions with powers in
the range that give scale-free graphs. Preferential attachment networks are models of graphs
that seek too provide a generative explanation for power-law degree distributions, which
strictly random graphs (such as Erdös-Rènyi type graphs) would not give. One possible
explanation turns out to be that scale-free graphs result from growth processes in which new
links are more likely to be attached to nodes that already have a high degree. Although
usually attributed to Albert and Barabasi, the basic idea goes back to earlier studies.
The preferential attachment process is a stochastic growth process for a simple non-
directed graph, whereby at each step we add one node and one or more links in a very
specific way. There are many different versions, the one below is just the simplest:
initiation: create the first node i = 1, with no links.
iterate for ` = 1, 2, 3, . . .:
• ` is the present number of nodes, add one new node `+1
• generate randomly one link from the new node to one of the ` existing nodes.
The node to connect to is selected with probabilities
ki (`−1)
∀i ≤ ` : Prob(Ai,`+1 = 1) = P` (130)
j=1 kj (`−1)
Here kj (`) is the degree of node j after ` steps of the process. We terminate if the size of
the network is what we want it to be.
Next we show that it leads to a power-law degree distribution. Let us first summarise
a few facts regarding the number of nodes N and links L, and the degrees.
(i) At step `: we go from (N, L) = (`, `−1) to (N, L) = (`+1, `).
(ii) After ` steps we have N = `+1 nodes and L = ` links.
(iii) The most recently created node always has degree 1, so k`+1 (`) = 1 for all `
1 P`+1
(iv) The average degree after ` steps is `+1 j=1 kj (`) = 2`/(` + 1)
From (iv) we conclude that `+1
P
j=1 kj (`) = 2` for all `. Therefore the selection probability
(130) at step ` can be written as Prob(Ai,`+1 = 1) = ki (`−1)/2(`−1).
The degrees evolve stochastically, so we must introduce the probability p` (k|i) that
after step ` we will have ki (`) = k. It is defined only for i ≤ ` + 1, and we know that
68
p` (k|`+1) = δk1 . At each step ` of the process, the degree of each node i ≤ ` either stays the
same, this happens with probability 1 − Prob(Ai,`+1 = 1), or increases by one, which happens
with probability Prob(Ai,`+1 = 1). Hence
no degree increase at step ` degree increase at step `
z }| { z }| {
k k−1
∀i ≤ ` : p` (k|i) = p`−1 (k|i) 1 − + p`−1 (k−1|i) (131)
2(`−1) 2(`−1)
Next we move to the overall degree distribution after ` steps, defined as
`+1 `
1 X 1 X 1
p` (k) = p` (k|i) = p` (k|i) + δk1 (132)
`+1 i=1 `+1 i=1 `+1
Inserting (131) into the right-hand side of this latter expression gives
` n
1 X k k−1 o 1
p` (k) = p`−1 (k|i) 1 − + p`−1 (k−1|i) + δk1
`+1 i=1 2(`−1) 2(`−1) `+1
` `
` k 1 X ` k−1 1 X 1
= 1− p`−1 (k|i) + p`−1 (k−1|i) + δk1
`+1 2(`−1) ` i=1 `+1 2(`−1) ` i=1 `+1
` k ` k−1 1
= 1− p`−1 (k) + p`−1 (k−1) + δk1 (133)
`+1 2(`−1) `+1 2(`−1) `+1
So now we have a closed dynamical equation for the evolving overall degree distribution.
Let us check that the probabilities in our equation remain properly normalised. Suppose
P
k≥0 p`−1 (k) = 1. Summation over all k in our equation gives:
X ` X k ` X k−1 1
p` (k) = 1− p`−1 (k) + p`−1 (k−1) +
k≥0 `+1 k≥0 2(`−1) `+1 k≥0 2(`−1) `+1
` ` 1 X ` 1 X
= − kp`−1 (k) + (k+1)p`−1 (k)
`+1 `+1 2(`−1) k≥0 `+1 2(`−1) k≥0
` 1 1
− +
`+1 2(`−1) `+1
` 1
= + =1 (134)
`+1 `+1
Hence normalisation is preserved, as it should. In the same manner one can confirm form
the dynamical equation (133) that the average degree after ` iterations is indeed given by
2`/(`+1) (see Exercises).
The final step is to find the asymptotic solution of (133). To do this we introduce a
real-valued time variable t` = `τ , with 0 < τ 1, and adapt our notation according to
p` (k) → pt` (k). Our equation then becomes
` k−1 ` k 1 1
pt` (k) − pt`−1 (k) = pt`−1 (k−1) − pt`−1 (k) − pt`−1 (k) + δk1
`+1 2(`−1) `+1 2(`−1) `+1 `+1
pt` (k) − pt`−1 (k) 1 n k−1 k o
= pt`−1 (k−1) − pt`−1 (k) − pt`−1 (k) + δk1
τ t` + τ 2(1−τ /t` ) 2(1−τ /t` )
69
pt` (k) − pt` −τ (k) 1 n k−1 k o
= pt` −τ (k−1) − pt` −τ (k) − pt` −τ (k) + δk1
τ t` + τ 2(1−τ /t` ) 2(1−τ /t` )
(135)
We now take the limit τ → 0 (assuming that it exists) and find
d 1 1
t pt (k) = (k−1)pt (k−1) − (k+2)pt (k) + δk1 (136)
dt 2 2
Stationary solutions of this equation are apparently to be solved from
(k−1)p(k−1) − (k+2)p(k) + 2δk1 = 0 (137)
One can confirm (see Exercises) that this equation is solved by:
4
p(0) = 0, k > 0 : p(k) = (138)
k(k+1)(k+2)
This is clearly a power law degree distribution, with p(k) ∼ k −3 for large k. The average
degree is finite, but k k 2 p(k) diverges, so the width of p(k) is infinite (see Exercises).
P
Variations on the above preferential attachment process include e.g. starting with more
than one disconnected node, or making multiple links at each iteration step.
7.3. Complexity – counting graphs
Graph complexity can be quantified as follows. A graph with features Ω(A) is more complex
than one with features Ω0 (A), if there exist fewer graphs with features Ω(A) then graphs
with features Ω0 (A). The more ‘unique’ are a graph’s characteristics, the more complex
is this graph. There is an intimate connection with the Shannon entropy of information
theory. The Shannon entropy of a discrete random variable x with probability distribution
p(x) is defined (apart from an overall constant ln 2) as S = − x p(x) log p(x). The Shannon
P
entropy of a random graph ensemble with macroscopic characteristics Ω(A) is
X
S(Ω) = − p(A|Ω) log p(A|Ω) (139)
A
For the hard-constrained ensembles (115) this gives S(Ω) = A δΩ,Ω(A) Z −1 (Ω) log Z(Ω) =
P
log Z(Ω). With the definition of Z(Ω) as given in (115) we then obtain
X
δΩ,Ω(A) = exp[S(Ω)] (140)
A
The left-hand side is exactly the number of graphs that have features Ω(A) = Ω, so we
can define the complexity of typical graphs with Ω(A) = Ω simply as the logarithm of this
number, i.e. simply as the Shannon entropy (139) of the ensemble. The same definition
(139) can then be used also for the soft-constrained ensembles (118).
Total number of N -node graphs. The total number of N -node graphs is simply the number
of ways we can choose the binary entries of the adjacency matrix. For directed graphs this
70
2 1
Z = 2N , for non-directed graphs we find Z = 2 2 N (N +1) , and for simple non-directed graphs
1
we get Z = 2 2 N (N −1) . So in all cases log Z ∼ 12 N 2 in leading order for large N . In the
finite connectivity regime, however, we allow only for a finite number of nonzero entries per
row and per column of the adjacency matrix. This reduces the number of possibilities. The
question is: by how much? Below we study this problem for simple-nondirected graphs,
similar results can be derived for directed ones (see also the exercises).
Simple non-directed graphs with specified average degree. Let us calculate the number of
N -node simple nondirected graphs that have average degree k̄, given that N k̄ ∈ IN. This is
simply Z(k̄) in the ensemble (120). Upon writing the Kronecker symbol in Z(k̄) in integral
form, and upon choosing G to be the set of all simple non-directed graphs, we obtain
Z π
X dω iωN k̄/2 X −iω Pi<j Aij
Z(k̄) = δN k̄,P
A = e e
ij ij −π 2π
A∈G A∈G
Z π Z π
dω iωN k̄/2 Y X −iωAij dω iωN k̄/2
= e e = e (1 + e−iω )N (N −1)/2
−π 2π i<j Aij ∈{0,1} −π 2π
−1)/2
dω iωN k̄/2 N (NX
!
N (N − 1)/2
Z π
= e e−iωm
−π 2π m=0 m
N (N −1)/2 ! !
X N (N − 1)/2 N (N − 1)/2
= δm,N k̄/2 = (141)
m=0 m N k̄/2
This result can be understood easily, as it gives the number of possible ways in which one
can draw N k̄/2 links from a set of N (N − 1)/2 possible candidates.
For large N and finite k̄ (the finite connectivity regime) we can inspect the leading
orders in N , using Stirling’s formula log n! ≈ n log n − n + O(log n) for n → ∞. If both n
and m are large (with m n), this formula, together with log(1 + x) = x + O(x2 ), allows
us to write
n!
log = log n! − log m! − log(n−m)!
(n−m)! m!
≈ nnlog n − (n−m) log(n−m) − m log m +oO(log n, log m)
m m
= n log n − (1− ) log(n−m) − log m + O(log n, log m)
n n
n m m m m o
= n log n−(1− ) log n−(1− ) log(1− )− log m + O(log n, log m)
n n n n
nm n mo m2
=n log + + O(log n, log m) + O( 3 )
n m n n
n m2
= m log + m + O(log n, log m) + O( 3 ) (142)
m n
Application of this expansion to n = 12 N (N −1) and m = 21 N k̄ then gives us
1 1 log N
N −1 log Z(k̄) = k̄ log[(N −1)/k̄] + k̄ + O( )
2 2 N
1 1 log N
= k̄ log(N/k̄) + k̄ + O( ) (143)
2 2 N
71
Thus for large N the leading order of the number of graphs with finite average degree k̄ still
grows super-exponentially as Z(k̄) ∼ exp( 21 k̄N log(N ) + . . .). This means that one can never
hope to sample numerically the space of all such graphs, even for relatively modest sizes N .
For instance, working out the formula gives
N = 32, k̄ = 2 : Z(k̄) ≈ 2.7 1052 (144)
91
N = 50, k̄ = 2 : Z(k̄) ≈ 4.1 10 (145)
These are very big numbers (for comparison: the total number of atoms in the observable
universe is estimated to be somewhere between 1078 and 1082 ).
Simple non-directed graphs with specified degree distribution. The next stage is to impose
not only the average degree k̄, but the full degree distribution p(k). The calculation is not
fundamentally different from the previous one but does require some new tools (saddle-point
integration), so here we mention only the result:
1 1 1 X p(k) log N
log Z({p(k)}) = k̄ log(N/k̄) + k̄ − p(k) log[ ] + O( ) (146)
N 2 2 k π(k) N
Here k̄ = k kp(k), and π(k) = e−k̄ k̄ k /k! (the degree distribution of Erdös-Rènyi graphs with
P
average degree k̄). Comparison to (143) shows that, due to the prescribed degree distribution,
N −1 log Z has been reduced by an amount which is the Kullback-Leibler distance (see
Information Theory) between p(k) and the degree distribution of an ER graph with the
same k̄. We see that if we impose the degree statistics p(k) = π(k) for all k, formula (146)
reduces to (143). Hence
Z({p(k)}) P
= e−N k p(k) log[p(k)/π(k)]+O(log N ) (147)
Z({π(k)})
This tells us that, for large N , nearly all graphs with a given finite average degree k̄ have a
Poissonnian degree distribution.
Simple non-directed graphs with specified degree distribution and specified degree correlations.
We can in the same way prescribe further information beyond the degree distribution, such
as the degree correlation kernel W (k, k 0 ). This turns out to give
1 1 1 p(k)
log Z({p(k), W (k, k 0 )}) = k̄ log(N/k̄) + k̄ −
X
p(k) log[ ]
N 2 2 k π(k)
1 X h W (k, k 0 ) i log N
− k̄ W (k, k 0 ) log 0
+ O( ) (148)
2 k,k0 W (k)W (k ) N
Comparison to (146) shows that prescribing W (k, k 0 ) reduces the quantity N −1 log Z further
by an amount which is proportional to the mutual information (see Information Theory) of
the degrees of connected nodes. We see that if we impose that degrees of connected nodes
are uncorrelated, i.e. W (k, k 0 ) = W (k)W (k 0 ) for all (k, k 0 ), formula (148) reduces to (146).
Hence nearly all graphs with a given degree distribution p(k) have uncorrelated degrees.
72
8. Appendices
8.1. Network software
Some network tools are available in the (commercial) Mathematica program. The following
software resources for imaging and/or analysis of networks, created within the academic
community, are free:
• Cytoscape: [Link]
• R – with igraph package: [Link]
• Pajek: [Link]/pub/networks/pajek/
8.2. The Pearson correlation
The Pearson correlation of two random variables (u, v) with joint distribution P (u, v) is
defined as
huvi − huihvi
PC = q (149)
(hu2 i − hui2 )(hv 2 i − hvi2 )
It tests for statistical dependence in the form a (partially) linear relationship between u and
v. To get some intuition for this, let us work out two simple extreme cases:
• Statistically independent u and v
Now P (u, v) = P (u)P (v), and hence
X X X X
huvi = P (u, v)uv = P (u)P (v)uv = P (u)u P (v)v = huihvi
uv uv u v
Hence we obtain PC = 0.
• Linearly related u and v
Suppose u = λv + c for all combinations (u, v). Now we obtain
huvi = hv(λv + c)i = λhv 2 i + chvi
hu2 i = h(λv + c)2 i = λ2 hv 2 i + c2 + 2λchvi
hui = hλv + ci = λhvi + c
Inserting all this into formula (149) then leads to
huvi − huihvi
PC = q
(hu2 i − hui2 )(hv 2 i − hvi2 )
λhv 2 i + chvi − λhvi2 − chvi
=q q
λ2 hv 2 i + c2 + 2λchvi − λ2 hvi2 − c2 − 2λchvi hv 2 i − hvi2
λ hv 2 i − hvi2
= q q = sgn(λ)
|λ| hv 2 i − hvi2 hv 2 i − hvi2
73
Hence if u and v are perfectly positively linearly correlated we find PC = 1, and if they
are perfectly negatively linearly related we find PC = −1.
8.3. Properties of symmetric matrices
Eigenvectors and eigenvalues. We derive some properties of real symmetric N × N matrices
A. The eigenvalue polynomial det (A − λ1I) = 0 is of order N , so A will have N (possibly
complex) solutions λ (where some may coincide) of the eigenvalue problem
Ax = λx, x 6= 0 (150)
We denote complex conjugation of complex numbers z in the usual way: if z = a + ib (where
| N is x · y = i x∗i yi .
a, b ∈ IR), then z ∗ = a − ib and |z|2 = z ∗ z ∈ IR. The inner product on C
P
• Claim: all eigenvalues of the matrix A are real.
Proof:
Take the inner product in (150) with the conjugate vector x∗ , which gives
N N
x∗i Aij xj = λ |xi |2
X X
i,j=1 i=1
We use the symmetry of A, and substitute Aij → 21 (Aij + Aji ):
x∗i (Aij + Aji )xj Aij (x∗i xj + xi x∗j )
P P
1 ij 1 ij
λ= PN 2
= PN 2
2 i=1 |xi | 2 i=1 |xi |
Since (x∗i xj + xi x∗j )∗ = xi x∗j + x∗i xj = x∗i xj + xi x∗j , the above fraction is real-valued.
• Claim: all eigenvectors of the matrix A can be chosen real-valued.
Proof:
We separate real and imaginary parts of every eigenvector:
1 1
x = Re x + iIm x Re x = (x + x∗ ) Im x = (x − x∗ )
2 2i
N N
with Re x ∈ IR and Im x ∈ IR . Complex conjugation of (150) gives Ax∗ = λx∗
(since λ is real). Hence, if x is an eigenvector with eigenvalue λ, so is x∗ . By
adding/subtracting the conjugate equation to/from (150) it follows: if x and x∗ are
eigenvectors, so are Re x and Im x. Since the space spanned by x and x∗ is the same as
the space spanned by Re x and Im x, we are always allowed to choose the real-valued
pair Re x and Im x.
• Claim: for every linear subspace L ⊆ IRN the following holds:
if AL ⊆ L then also AL⊥ ⊆ L⊥
in which L⊥ denotes the orthogonal complement, i.e. IRN = L ⊕ L⊥ .
74
Proof:
For each x ∈ L and y ∈ L⊥ we find (x · Ay) = (y · Ax) = 0 (since Ax ∈ L and
y ∈ L⊥ ). Therefore Ay ∈ L⊥ , which completes the proof.
• Claim: we can construct a complete orthogonal basis in IRN of A-eigenvectors.
Proof:
Consider two eigenvectors xa and xb of A, corresponding to different eigenvalues:
Axa = λa xa Axb = λb xb λa 6= λb
We now form:
0 = (xa · Axb ) − (xa · Axb ) = (xa · Axb ) − (xb · Axa )
= λb (xa · xb ) − λa (xb · xa ) = (λa − λb )(xa · xb )
Since λa 6= λb it follows that xa · xb = 0. If all eigenvalues are distinct, this completes
the proof, since now there will be N eigenvalues with eigenvectors x 6= 0. Since these N
eigenvectors are orthogonal, after normalization they form a complete orthogonal basis.
To deal with degenerate eigenvalues we need the third property above. If Ax = λx,
then ∀y with x · y = 0: (Ay) · x = 0. Having found an eigenvector for eigenvalue λ (not
unique in the case of a degenerate eigenvalue), a new reduced (N −1) × (N −1) matrix
can be constructed by restricting ourselves to the subspace x⊥ . The new matrix is again
symmetric, the eigenvalue polynomial is of order N − 1 (and contains all the previous
roots except for one corresponding to the eigenvector just eliminated), and we can repeat
the argument. This shows that there must again be N orthogonal eigenvectors.
Basis of eigenvectors and diagonal form. The final consequence of the above facts is that
there exist a set of N vectors {êi }, where i = 1, . . . , N and êi ∈ IRN for all i, with the
following properties:
Aêi = λi êi , λi ∈ IR, λi > 0, êi · êj = δij (151)
We can now bring A onto diagonal form by a simple unitary transformation U , which we
construct from the components of the normalised eigenvectors ê: Uij = êji . We denote the
transpose of U by U † , Uij† = Uji , and show that U is indeed unitary, i.e. U † U = U U † = 1I:
(U † U )ij xj = U ki Ukj xj = êik êjk xj =
X X X X
δij xj = xi
j jk jk j
(U U † )ij xj = U ik Ujk xj = êki êkj xj = êki (ê · x) = xi
X X X X
j jk jk k
(since {ê } is a complete orthogonal basis). From U being unitary it follows that U and U †
`
leave inner products, and therefore also lengths, invariant:
(U x) · (U y) = x · U † U y = x · y U †x · U †y = x · U U †y = x · y
75
We can see explicitly that U indeed brings A onto diagonal form:
N N N
†
(U † AU )ij = êik Akl êjl = λj êik êjk = λj δij
X X X
Uik Akl Ulj = (152)
kl=1 kl=1 k=1
Note that the inverse A−1 of the matrix A exists, and can be written as follows:
N
(A−1 )ij = λ−1 k k
X
k êi êj (153)
k=1
To prove that this is the inverse of A, we work out for any x ∈ IRN the two expressions
N N N
−1
λ−1 ` `
ê`i (ê` · x) = xi
X X X
(AA x)i = Aik ` êk êj xj =
kj=1 `=1 `=1
`
(again since {ê } forms a complete orthogonal basis), and
N X
N N
(A−1 Ax)i = λ−1 ` `
ê`i (ê` · x) = xi
X X
` êi êk Akj xj =
kj=1 `=1 `=1
8.4. Diagonalisation of symmetric matrices
Finding the eigenvalues of a symmetric N ×N matrix B requires solving the following coupled
equations for x = (x1 , . . . , xN ) and µ, where the length of x is arbitrary (but nonzero):
B11 B12 . . . B1N x1 x1
B21 B22 . . . B2N . .
. . . . . . . = µ .
. . . . . . . .
BN 1 BN 2 . . . BN N xN xN
Since B is symmetric we know that (i) there are precisely N real-valued eigenvalues with
distinct eigenvectors (but these eigenvalues need not be distinct), and (ii) all eigenvectors
can be constructed to be orthogonal.
One way to determine the N eigenvalues {µ1 , . . . , µN } by solving the equation Det[B −
µ1I] = 0, which is an order-N polynomial that will have the N eigenvalues as solutions.
However, if many of the rows of B are identical (which means that B can be written in a
block form with homogeneous blocks), it is sometimes easier to write the above equations
explicitly; since many will be identical, there will be in effect just a small number of them.
Moreover, if we also need the eigenvectors, we would have to solve these equations anyway.
While doing so, we can often make good use of the orthogonality of the eigenvectors.
For instance, if we have already found the eigenvector ê1 = √12 (1, 1, 0, 0, . . . , 0), we know
that all other eigenvectors êk must have êk · ê1 = 0, which for the present example translates
into ek1 + ek2 = 0 for all k > 1.
76
8.5. Integral representation of the Kronecker δ-symbol
Here we show that for any n, m ∈ ZZ the Kronecker δ can be written in the integral form
Z π
dω i(n−m)ω
δnm = e (154)
−π 2π
To see this one simply does the integral on the right:
Z π
dω i(n−m)ω Z π dω
n=m: e = =1
−π 2π −π 2π
Z π
dω i(n−m)ω Z π dω
n 6= m : e = cos((n−m)ω) + i sin((n−m)ω)
−π 2π −π 2π
1 h 1 i iω=π
= sin((n−m)ω) − cos((n−m)ω)
2π n−m n−m ω=−π
1
= .0 = 0
2π
Hence the integral is indeed equal to δnm .
8.6. The δ-distribution
We can define the δ-distribution as the probability distribution δ(x) corresponding to a
random variable in the limit where the randomness in the variable vanishes. If x is
‘distributed’ around zero, this implies
Z
dx f (x)δ(x) = f (0) for any function f
The problem arises when we want to actually write down an expression for δ(x). Intuitively
one could think of writing something like
1 2 2
δ(x) = lim G∆ (x) G∆ (x) = √ e−x /2∆ (155)
∆→0 ∆ 2π
This is not a true function in a mathematical sense; δ(x) is zero for x 6= 0 and δ(0) = ∞. The
way to interpret and use expressions like (155) is to realize that δ(x) only has a meaning
when appearing inside an integration. One then takes the limit ∆ → 0 after performing
the integration. Upon adopting this convention, we can use (155) to derive the following
properties (for sufficiently well-behaved and differentiable functions¶ f ):
Z Z Z
dx −x2 /2
dx δ(x)f (x) = lim dx G∆ (x)f (x) = lim √ e f (∆x) = f (0)(156)
∆→0 ∆→0 2π
( )
Z
0
Z
d
dx δ (x)f (x) = lim dx [G∆ (x)f (x)] − G∆ (x)f 0 (x) (157)
∆→0 dx
= lim [G∆ (x)f (x)]∞ 0 0
−∞ − f (0) = −f (0) (158)
∆→0
¶ The conditions on the so-called ‘test-functions’ f can be properly formalized; this not being a course on
distribution theory, we just concentrate on the basic ideas and properties.
77
These statements can be summarized in and generalized to the single expression:
Z
dn dn
dx f (x) n δ(x) = (−1)n lim n f (x) (n = 0, 1, 2, . . .) (159)
dx x→0 dx
Equivalently we can take the result (159) as our definition of the δ-distribution.
8.7. Series
I refer to first year Calculus courses for general results on the convergence of ordinary series,
of the form k≥0 ak , or power series, of the form k≥0 ak z k with z ∈ C | . For this course on
P P
networks we only need to remember and use some specific results such as:
(
X
−γ convergent if γ > 1
γ ∈ IR : k = (160)
k>0
divergent if γ≤1
n
1 − z n+1
zk =
X
∀z ∈ C
| , z 6= 1 (161)
k=0 1−z
X zk
= ez ∀z ∈ C
| (162)
k≥0 k!
8.8. The Lagrange method
To find the maximum over x ∈ IRn of a function f : IRn → IRn subject to a constraint
written in the form C(x) = 0, we must solve the following set of n + 1 coupled equations for
x ∈ IR and the so-called Lagrange parameter λ ∈ IR:
∂
∂xi
f (x) = λ ∂x∂ i C(x) ∀i ∈ {1, . . . , n}
(163)
C(x) = 0
If we have m ≥ 1 constraints, written as C` (x) = 0 for all ` = 1 . . . m, then each constraint
will have a Lagrange parameter λ` and we must solve the following set of n + m coupled
equations for x ∈ IR and the m Lagrange parameters λ1 . . . λm ∈ IR:
Pm
∂
∂xi
f (x) = `=1 λ` ∂x∂ i C` (x) ∀i ∈ {1, . . . , n}, ∀` ∈ {1, . . . , m}
(164)
C` (x) = 0 ∀` ∈ {1, . . . , m}
If there are multiple solutions, we must select the one for which f (x) is maximal.
78
9. Exercises
Section 2
(i) Which if the three graphs below is simple? Which of them is directed? Give for each
these graphs the vertex set V and the edge set E.
5 4
9
•6 7 7
•
•@I •K
A
•@ •6
@ A @
@ A @
2 • •
-@
6I
@
-A •4 1 • •
@
@
•3
3@@ 2@@
10 • • 11
@
8 • •9
@
• •
6 5
(ii) Calculate the adjacency matrices for each of the three graphs above, upon relabelling
the nodes of the first graph such that its vertex set becomes V = {1, . . . , 9}.
(iii) Use the adjacency matrices calculated in the previous exercise to prove that the first
of the three graphs has exactly four paths of length three and no paths of length 4 or
larger. Argue why we can be sure that the middle and right graphs will contain paths
of any length ` > 0.
Section 3
(iv) Calculate all in-degrees and all out-degrees of the above three graphs.
(v) Prove that in nondirected graphs always kiin (A) = kiout (A).
Prove that for non-directed graphs one always has ki (A) = (A2 )ii .
(vi) Show that in any simple non-directed graph with adjacency matrix A one has Ci (A) =
2Ti (A)/ki (A)[ki (A) − 1], where Ti (A) is the number of triangles in which node i
participates, and ki (A) is its degree.
(vii) Calculate the clustering coefficients for all nodes in the second and the third of of the
above graphs. Why would we not calculate them for the first graph?
(viii) Define the neighbourhood ∂i of a node i in a nondirected graph with adjacency matrix
A as follows: ∂i = {j ≤ N | Aij = 1}. Show that the order-2 generalised degrees can be
(2) (2)
written as ki (A) = j∈∂i kjin (A). Calculate all order-2 generalised degrees ki (A) of
P
the second and third graph above.
79
(ix) Prove that in directed graphs always L = i kiin (A) = kiout (A). Show that in a
P P
i
simple non-directed graph one has L = 21 N k̄(A).
(x) Verify that the order-` generalised degrees in a nondirected graph with adjacency matrix
A can be written as
N
(`)
(A`−1 )ij kj (A)
X
ki (A) =
j=1
Show that the corresponding expressions for directed graphs are, with (A† )ij = Aji :
N N
(`)in (`)out
`−1
)ij kjin (A), (A† `−1
)ij kjout (A)
X X
ki (A) = (A ki (A) =
j=1 j=1
`
(xi) Prove the matrix identity (1I − γA)−1 = `≥0 γ ` A . Given any matrix norm |A| that
P
satisfies the usual conditions (i.e. |A| ∈ IR+ , |λA| = |λ||A| for any λ ∈ IR, |A| = 0 if
and only if A = 0, |A1 + A2 | ≤ |A1 | + |A2 |), show that there is always a sufficiently
small but nonzero value of γ such that the series `≥0 γ ` A` converges in norm.
P
(xii) Consider the N -node graph with N > 2 and the following adjacency matrix entries:
Aij = δi,j+1 mod N + δi,j−1 mod N . Prove that for this graph
−1
−1 1 NX e2πi`(r−s)/N
r, s ∈ {1, . . . , N } : [(1I − γA) ]rs =
N `=0 1 − 2γ cos(2π`/N )
(you may find the geometric series helpful in proving this, as well as the series
(1 − )−1 = m≥0 m ; see Calculus lectures).
P
(xiii) Calculate the closeness centrality and the betweenness centrality of nodes i = 2 and
i = 3 in the second and the third of of the graphs in exercise (i).
(xiv) Show that the definition of the Pearson correlation similarity τij (A) can be derived from
the definition of the Pearson correlation of two random variables (u, v), upon choosing
P (u, v) = N1 k δu,Aik δv,Ajk .
P
(xv) Let x · y denote an inner product on IRN , so that it meets the defining criteria:
(a) (∀x, y, z ∈ IRN ) : (x + y) · z = x · z + y · z
(b) (∀x · y ∈ IRN )(∀λ ∈ IR) : x · (λy) = λx · y
(c) (∀x · y ∈ IRN ) : x · y = y · x
(d) (∀x ∈ IRN ) : x · x ≥ 0, with equality if and only if x = 0
Prove the Schwartz inequality: |x·y| ≤ |x||y|. Hint: calculate |x+λy|2 |y|2 with λ ∈ IR,
and choose a clever value for λ at the end.
(xvi) Explain why the two expressions given for the cosine similarity σij (A) of two nodes i
and j in a nondirected graph are identical. Show that |σij (A)| ≤ 1, and that σij (A) = 1
if and only if ∂i = ∂j . Hint: define for each node i the vector a(i) = (Ai1 , Ai2 , . . . , AiN ) ∈
{0, 1}N , and write σij (A) in terms of the two vectors a(i) and a(j) .
80
(xvii) Explain why the two expressions given for the Pearson correlation similarity τij (A) of
two nodes i and j in a nondirected graph are identical. Show that |τij (A)|
√ ≤ 1. Hint:
(i) (i) 1 P
define for each node i the vector a with entries ak = [Aik − N ` Ai` ]/ N , and write
τij (A) in terms of a(i) and a(j) .
Section 4
in
(xviii) Prove that the average in-degree k (A) = N −1 i kiin (A) and the average out-degree
P
out
k (A) = N −1 i kiout (A) of any graph (directed or non-directed) are always identical.
P
Show that the total number of links in a directed graph can be written as either
L = N
P in PN out
i=1 ki (A) or L = i=1 ki (A). Show that in simple nondirected graphs the
number of links is L = 12 N k̄(A), where k̄(A) = N −1 i≤N ki (A) is the average degree.
P
(xix) Prove the following identities for the density ρ(A) of a graph with adjacency matrix A:
directed graphs : ρ(A) = k(A)/N
X
nondirected graphs : ρ(A) = k(A)/(N +1) + Aii /N (N +1)
i
simple nondirected graphs : ρ(A) = k(A)/(N −1)
(xx) Calculate the diameter d(A) and the degree distribution p(k|A) for the middle and the
right graph in question (i).
(xxi) Consider the following degree distribution for an infinitely large non-directed graph:
p(k) = e−q q k /k! ∀k ∈ IN. Calculate the average degree hki = k≥0 p(k)k and the
P
degree variance σk2 = hk 2 i − hki2 .
(xxii) Consider the following degree distribution for an infinitely large non-directed graph:
p(k) = Ce−k ∀k ∈ IN. Give a formula for the constant C. Calculate the average degree
hki = k≥0 p(k)k and the degree variance σk2 = hk 2 i − hki2 .
P
(xxiii) Consider the following degree distribution for an N -node non-directed graph: p(k) = 0
for k = 0 or k > N , and p(k) = CN k −γ for 0 < k ≤ N . Calculate CN . For which γ
values is p(k) normalisable for N → ∞? Give formulas for hki and the degree variance
σk2 = k≥0 p(k)k 2 − hki2 . For which γ values is hki finite in the limit N → ∞? For what
P
values of γ is the variance finite for N → ∞? Give an estimate of the average and the
variance for γ = 2.5 and N = 10,000, using the approximation N −λ
≈ 1N dk k −λ .
P R
k=1 k
(xxiv) Calculate the degree distributions for the N -node graphs with the following adjacency
matrices (check carefully whether they are directed or non-directed, and use the correct
degree distribution definition in each case):
(a) Aij = δi,j+1 for j < N , and AiN = 0.
(b) Aij = 1 for all i, j ∈ {1, . . . , N }
(c) Aij = 0 for all i, j ∈ {1, . . . , N }
(d) Aij = 1 if either i, j ∈ {1, . . . , N/2} or i, j ∈ {N/2+1, . . . , N }; Aij = 0 otherwise
(e) Ai1 = 1 for all i > 1, Aij = 0 for all other (i, j).
81
(xxv) Show that the degree correlation ratio Π(k, k 0 |A) of a ‘regular’ simple non-directed
graph A, i.e. one with p(k|A) = δk,k? for some k ? ∈ IN, is always equal to 1 for any
(k, k 0 ).
(xxvi) Prove that W1 (~k|A) = p(~k|A)k in /k̄(A) and that W2 (~k 0 |A) = p(~k 0 |A)k out0 /k̄(A).
(xxvii) Prove the following general bounds for the modularity: − 21 ≤ Q(A) ≤ 12 .
(xxviii) Assign the following module labels to the nodes of the right graph in exercise (i):
x1 = x2 = 1, x3 = x4 = x5 = 2. Calculate the graph’s modularity Q(A). Next
turn to graphs (b) and (d) in exercise (xxiv). Assign the following module labels to the
nodes: xi = 1 for i ≤ N/2 and xi = 2 for i > N/2 (take N to be even). Calculate the
modularity Q(A) for both graphs.
Section 5
(xxix) Show how the average degree k̄(A) and the total number of triangles T (A) in a simple
non-directed N -node graph can be calculated directly from the spectrum %(µ|A) of its
adjacency matrix.
(xxx) Calculate the adjacency matrix eigenvalue spectrum %(µ|A) of the middle graph in
exercise (i). Use your result to calculate the average degree, and to prove that this
graph has no closed paths of odd length.
(xxxi) Calculate the Laplacian matrix L of the middle graph in exercise (i), and its eigenvalue
spectrum %Lap (µ|A). Hint: write L = 1I + B and first find the eigenvalues of B, where
1I is the unity matrix. Use your result to prove that this graph has only one connected
component.
(xxxii) Use the results of the previous exercise to solve the dynamical equations describing a
diffusion process on the middle graph in exercise (i), that starts with zi (t) = z0 δi2 (i.e.
diffusion from the central node i = 2). Verify that your result makes sense for t = 0
and in the limit t → ∞. Verify that the quantity i zi (t) is conserved over time.
P
(xxxiii) Show that for regular N -node graphs, i.e. those for which all N degrees ki (A) are
identical, one can express the Laplacian eigenvalue spectrum %Lap (µ|A) in terms of the
adjacency matrix eigenvalue spectrum %(µ|A). Give the mathematical relation between
the two in explicit form.
(xxxiv) Consider the N -node graph with the following adjacency matrix entries, with N > 2:
Aij = δi,j+1 mod N + δi,j−1 mod N . Calculate the adjacency matrix spectrum %(µ|A) and
the Laplacian spectra and %Lap (µ|A). Hints: use the result of the previous exercise, and
try Fourier modes xk = eiωk as an ansatz for the eigenvectors. Confirm that the smallest
eigenvalue of the Laplacian is zero, and use the spectrum to determine the number of
connected components in the graph.
82
Section 6
(xxxv) For the Erdös-Rènyi model we know that hk̄(A)i = p? (N − 1). Calculate hk̄ 2 (A)i.
Calculate the variance σk̄2 = hk̄ 2 (A)i − hk̄(A)i2 in the finite connectivity regime, and
express it in terms of hki for N → ∞. What can you conclude from the result?
P P
(xxxvi) Show for the following degree distribution that k≥0 p(k) = 1 and k≥0 p(k)k = q,
without using its generating function:
q k
p(k) = ( ) /(1+q) (165)
1+q
(xxxvii) Calculate the generating function G(x) for the following degree distribution, with
α ∈ [0, 1] and q1 , q2 ∈ IN:
p(k) = αδk,q1 + (1−α)e−q2 q2k /k!
(xxxviii) Confirm that the three generating functions for regular, Poissonnian, and exponential
d
random graphs all obey: G(0) = p(0), G(1) = 1, and limx→1 x dx G(x) = hki. Calculate
2
expressions for hk i from the three generating functions.
(xxxix) Prove that hk 2 i ≥ hki for all graphs, with equality if and only if p(k) = 0 for all k > 1.
(xl) Construct a large 2-regular graph, i.e. one with p(k) = δk,2 and large N , that does not
have a giant component. Prove your claim.
(xli) Show that the distribution p(A) which maximises the Shannon entropy for the
set of simple nondirected graphs, subject to the soft average degree constraint
A∈G p(A)k̄(A) = hki and subject to normalisation, is the Erdös-Rényi ensemble.
P
(xlii) Show that the probabilities in the ensemble of simple nondirected graphs with soft-
constrained degree sequences can, for large N and finite degrees {ki }, be written as
Y h ki kj 1 ki kj 1 i
p(A|k) = + O( 2 ) δAij ,1 + 1 − + O( 2 ) δAij ,0
i<j N hki N N hki N
Section 7
(xliii) Calculate the degree distribution of small-world graphs built by superimposing a
Poissonnian graph with average degree q on a one-dimensional periodic ring, for N → ∞.
You may assume that there are no common entries in the adjacency matrices of both.
(xliv) Show that the distribution p(k = 0) = 0 and p(k > 0) = 4/k(k + 1)(k + 2) solves the
preferential attachment equation 12 (k−1)p(k−1) − 21 (k+2)p(k) + δk1 = 0.
(xlv) Show that the previous distribution obeys k≥0 p(k) = 1 and hki = k≥0 kp(k) = 2.
P P
Hint: find constants a, b, c such that 1/k(k+1)(k+2) = a/k+b/(k+1)+c/(k+2) ∀k > 0.
(xlvi) Calculate the leading orders in N of the number of directed N -node graphs with average
degree k̄, in the finite connectivity regime where k̄N ∈ IN and k̄ N .
You might also like
- Network Analysis: Probability & StatisticsNo ratings yetNetwork Analysis: Probability & Statistics42 pages
- Graph Theory and Complex Networks An Introduction 1st Ed Edition Steen Ebook Testbank Solutions With Full Chapters100% (1)Graph Theory and Complex Networks An Introduction 1st Ed Edition Steen Ebook Testbank Solutions With Full Chapters132 pages
- Graven in Grafen - Graph Theory and Complex Networks-110208 PDFNo ratings yetGraven in Grafen - Graph Theory and Complex Networks-110208 PDF299 pages
- Mining Complex Networks, 1st Edition ISBN 9781032112053, 1032112050 full downloadNo ratings yetMining Complex Networks, 1st Edition ISBN 9781032112053, 1032112050 full download16 pages
- Introduction to Graph Theory and NetworksNo ratings yetIntroduction to Graph Theory and Networks299 pages
- Complex Network Dynamics and CentralityNo ratings yetComplex Network Dynamics and Centrality13 pages
- Combinatorial Models in Complex SystemsNo ratings yetCombinatorial Models in Complex Systems194 pages
- Higher-Order Network Dynamics ExplainedNo ratings yetHigher-Order Network Dynamics Explained134 pages
- Complex Networks An Algorithmic Perspective 1st Edition ISBN 9781138033894, 1138033898 Complete Book DownloadNo ratings yetComplex Networks An Algorithmic Perspective 1st Edition ISBN 9781138033894, 1138033898 Complete Book Download16 pages
- Graph Theory and Interconnection Networks 1st Edition Lih-Hsing Hsu Ebook Testbank Solutions Reading Now Available100% (2)Graph Theory and Interconnection Networks 1st Edition Lih-Hsing Hsu Ebook Testbank Solutions Reading Now Available84 pages
- Graph Theory: Key Concepts and Applications100% (2)Graph Theory: Key Concepts and Applications722 pages
- Introduction To Graph Theory and Basic Algorithms: Mikhail Tuzhilin Dong ZhangNo ratings yetIntroduction To Graph Theory and Basic Algorithms: Mikhail Tuzhilin Dong Zhang88 pages
- Charles Bordenave Random Graphs Course NotesNo ratings yetCharles Bordenave Random Graphs Course Notes99 pages
- Graph Spectra for Complex Networks completed100% (1)Graph Spectra for Complex Networks completed217 pages
- A Guide To Temporal Networks ISBN 9781786341143, 178634114X Instant DOCX DownloadNo ratings yetA Guide To Temporal Networks ISBN 9781786341143, 178634114X Instant DOCX Download14 pages
- Understanding Random Graphs and NetworksNo ratings yetUnderstanding Random Graphs and Networks6 pages
- Complex Networks Principles, Methods and Applications ISBN 9781107103184, 1107103185 Full TextNo ratings yetComplex Networks Principles, Methods and Applications ISBN 9781107103184, 1107103185 Full Text14 pages
- A Simple Introduction To Graph Theory (Inglés) Autor Brian HeinoldNo ratings yetA Simple Introduction To Graph Theory (Inglés) Autor Brian Heinold134 pages
- Algorithmic Graph Theory - David Joyner, Minh Van Nguyen, Nathann CohenNo ratings yetAlgorithmic Graph Theory - David Joyner, Minh Van Nguyen, Nathann Cohen319 pages
- 6 Spanning Subgraphs 89: II Basic Model Extensions 149No ratings yet6 Spanning Subgraphs 89: II Basic Model Extensions 1494 pages