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 .
Previous Page Next Page