It i s the goal of this monograph to cover some of the developments an d mentio n
what w e believe ar e promisin g furthe r directions . Sinc e thi s i s a fas t movin g field ,
there are already several books on this topic from th e physics or heuristics points of
view. Th e focus here is mainly on rigorous mathematical analysi s via graph theory .
The coverag e i s far fro m complete . Ther e ar e perhap s to o man y model s tha t hav e
been introduce d b y various groups . Her e we intend t o giv e a consistent an d simpl e
(but no t to o simple! ) pictur e rathe r tha n attemptin g t o giv e an exhaustiv e survey .
Instead, w e direc t th e reade r t o severa l book s [10, 46 , 118 ] an d relate d survey s
[3, 12, 102, 89 , 106].
1.1 . I n som e papers, powe r la w graphs ar e referred t o a s "scale-free "
graphs or networks. I f the word "scale-free " i s going to be used, the issue of "scale "
should first b e addressed . W e will consider scale-fre e graph s (se e Section 3.5 ) onl y
after th e notio n o f scale i s clarified .
1.2. I n Figure s 1 and 2 , we illustrate a power la w distribution i n th e
usual scal e an d an d i n a log-lo g scale , respectively . Figure s 3 an d 4 contai n th e
degree distributio n o f a cal l grap h (wit h edge s indicatin g telephon e calls ) an d it s
power la w approximation . I n a way , th e powe r la w distributio n i s a straigh t lin e
approximation fo r th e log-lo g scale. Som e might sa y tha t ther e ar e small "bumps "
in th e middl e o f th e curve s representin g variou s degre e distribution s o f realisti c
graphs. Indeed , th e power la w is a first-order estimat e an d a n important basi c cas e
in ou r understandin g o f networks . W e wil l interpre t powe r la w graph s i n a broa d
sense includin g an y grap h tha t exhibit s a power la w degree distribution .
10000 100000
3 . Degre e dis -
tribution o f a call graph
in log-lo g scale.
4 . Th e powe r
law approximatio n o f
Figure 3 in log-log scale.
1.2. Basi c definition s
In the study of complex networks, there have been an increasingly large numbe r
of new an d complicate d definition s o n various 'grap h metrics' . Her e we attempt t o
follow th e advic e o f Einstein :
Previous Page Next Page