CHAPTER 1
Graph Theor y i n th e Informatio n Ag e
1.1. Introductio n
Graph theor y ha s a histor y datin g bac k mor e tha n 25 0 year s (startin g wit h
Leonhard Eule r an d hi s quest fo r a walk linkin g seven bridge s i n Konigsber g [17]).
Since then , grap h theory , th e stud y o f network s i n thei r mos t basi c for m a s inter -
connections amon g objects , ha s evolve d fro m it s recreationa l root s int o a ric h an d
distinct subject . O f particula r significanc e i s its vita l rol e i n ou r understandin g o f
the mathematic s governin g th e discret e universe .
Throughout th e years , grap h theorist s hav e bee n studyin g variou s type s o f
graphs, such as planar graph s (draw n without edge s crossing in the plane) , interva l
graphs (arisin g i n scheduling) , symmetri c graph s (hypercubes , platoni c solid s an d
those fro m grou p theory) , routin g network s (fro m communications ) an d computa -
tional graph s tha t ar e use d i n designing algorithm s o r simulations .
In 1999, a t th e daw n o f th e ne w Millennium , a mos t surprisin g typ e o f grap h
was uncovered . Indeed , it s universa l importanc e ha s brough t grap h theor y t o th e
heart o f a ne w paradig m o f scienc e i n thi s informatio n age . Thi s famil y o f graph s
consists o f a wid e collectio n arisin g fro m divers e arena s bu t havin g completel y
unexpected coherence . Example s includ e th e WWW-graphs , th e phon e graphs ,
the emai l graphs , th e so-calle d "Hollywood " graph s o f costars, th e "collaboration "
graph o f coauthors, a s well a s legions o f others fro m al l branche s o f natural, socia l
and lif e sciences . Th e prevailin g characteristic s o f these graph s ar e th e following :
Larg e The siz e of the network typically range s from hundred s o f thou-
sands to billions of vertices. Brut e forc e approache s ar e no longer feasible .
Mathematical wizardr y i s in demand agai n how can we use a relativel y
small numbe r o f parameters t o captur e th e shap e o f the network ?
Spars e Th e numbe r o f edge s i s linear, i.e. , withi n a smal l multipl e o f
the numbe r o f vertices. Ther e migh t b e dense graph s (havin g a quadrati c
number o f edges in term s o f vertices) ou t ther e bu t th e larg e graph s tha t
we encounter ar e mostl y sparse .
Th e smal l worl d phenomeno n This i s used t o refe r t o tw o distinc t
properties: small distance (tw o stranger s ar e typicall y joine d b y a shor t
chain of mutual acquaintances) , an d the clustering effect (tw o people wh o
share a commo n neighbo r ar e mor e likel y t o kno w eac h other )
http://dx.doi.org/10.1090/cbms/107/01
Previous Page Next Page