1.2. BASI C DEFINITION S 3

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].

REMARK

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 .

REMARK

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 .

3

Indegree

10000 100000

FIGURE

3 . Degre e dis -

tribution o f a call graph

in log-lo g scale.

FIGURE

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 :