Complex Networks

16 

Complex Networks: An Algorithmic Perspective

(a)

(b)

4

1

5

8

3

1

Figure 2.7: a) A weighted graph. b) A directed graph

E

′

= {(x

0

,x

1

),(x

1

,x

2

),..., (x

k−1

,x

k

)}. A path is usually refereed by the sequence of

its vertices. A cycle is a path that starts and ends at the same vertex and visits each

vertex exactly once and has at least a length of 3. The length of a cycle is the number

of vertices it has. The minimum length of a cycle in a graph G is called its girth, if

there is a cycle. When G does not have any cycle, the girth is defined as 0. A chord

of a graph G(V,E) is an edge e ∈E which joins two vertices of a cycle in G but is not

included in the cycle. A