2

1. GRAP H THEOR Y I N THE INFORMATION AGE

• Powe r la w degree distributio n — The degree of a vertex is the number

of vertice s adjacen t t o it . Th e powe r la w assert s tha t th e numbe r o f

vertices wit h degre e k is proportional t o k~@ fo r some exponent (3 1.

FIGURE

1. A powe r

FIGUR E

2 . Th e sam e

law distributio n i n th e distributio n i n th e log-

usual scale . lo g scale.

The first two characteristics (larg e and sparse) com e naturally an d the third (smal l

world phenomenon ) ha s long bee n withi n th e mindset o f the public consciousness .

The mos t critica l an d striking fac t i s the power law . For example, wh y should the

email grap h an d the collaboration grap h hav e simila r degre e distributions ? Wh y

should th e phon e graph s hav e th e sam e shap e fo r differen t time s o f the day and

different regions ? Wh y should the biological networks constructed usin g the genome

database hav e distribution s simila r t o those o f various socia l networks ? I s Mothe r

Nature finall y revealin g a glimpse of some first principle s fo r the discrete world ?

The powe r la w allows u s to use one single paramete r (th e exponent /? ) to de-

scribe the degree distribution o f billions of nodes. Wit h a short descriptio n o f such

a family o f graphs, it is then possibl e to carry out a comprehensive analysi s of these

networks. O n one hand, w e can use various know n method s an d tools, combina -

torial, probabilisti c an d spectral, t o deal wit h problem s o n power la w graphs. O n

the othe r hand , thes e realisti c graph s (i.e. , graph s derive d fro m collectio n o f dat a

from rea l worl d applications ) provid e insigh t an d suggest man y ne w and excitin g

directions fo r researc h i n graph theory . Indeed , i n the pursui t o f these larg e bu t

attackable, spars e bu t comple x graphs , w e have t o retool man y method s fro m ex -

tremal an d random graphs . Muc h i s to be learned fro m thi s broa d scop e an d new

connections.

In fact , eve n a t th e end of the 19th century, th e powe r la w had bee n note d

in variou s scenario s (mor e histor y wil l b e mentione d i n late r sections) . However ,

only i n 1999 were th e dots connecte d an d a more complet e pictur e emerged . Th e

topic has spontaneously intrigued numerous researchers from diverse areas including

physics, socia l science , compute r science , telecommunications , biolog y an d mathe -

matics. A new area o f network complexit y ha s since bee n rapidl y developin g and

is particularl y enriche d b y the cross-fertilization o f abundan t disciplines . Mathe -

maticians an d especiall y grap h theorist s hav e muc h t o contribut e t o buildin g th e

scientific foundatio n o f this area .