what-when-how
In Depth Tutorials and Information
possible number of undirected edges between neighbors of the node is
k
i
(
k
i
- 1)/2;
for directed edges, this is doubled. his can be visualized as the number of triangles
that exist in the graph which include the node as one of the vertices of the triangle.
he clustering coefficient of the graph
C
(
G
) is then the average of the clustering
coefficients of all nodes. Watts and Strogatz show that many real-world networks
exhibit small-world behavior [31]. hey calculate the clustering coeicient for
some networks to be: 1 for cliques, 0.79 for the network of collaborating actors in
Hollywood, a maximum of 0.75 for circulant graphs, 0.28 for the neural network
of
Caenorhabditiselegans
, and almost 0 for random networks.
Small-world networks are desirable features to have in a communication sys-
tem, and especially in peer-to-peer file sharing systems, as they are expected to be
efficient at delivering messages to all nodes in the system. Latora and Marchiori
[21] measured the efficiency of the information exchange in small-world networks.
hey find that the small-world networks are both globally and locally efficient at
exchanging information over the network. his was also examined by Comellas et.
al. [14,13], who looked at broadcasting and the spreading of epidemics in small-
world communication networks. hey ind that the networks are very eicient at
both broadcasting and the spreading of viruses, both of which are similar to the
distribution of a file in a file-sharing system such as BitTorrent.
Many existing peer-to-peer systems (e.g., Gnutella [24], Freenet [18,36], and
DHT-based systems [19]) are known to be small-world. It is natural to expect that
torrents would exhibit small-world characteristics, particularly since clustering has
been previously observed in the early stages of torrents [22].
Figure 6.15 shows the characteristic path lengths of the four networks in
our BitTorrent experiment. Note that, for the directed Interest, Unchoked, and
Download graphs, the path lengths were calculated on the graphs after they were
reduced to their largest strongly connected component to avoid the disconnected
nature of BitTorrent graphs. he characteristic path length increases rapidly during
the startup stage, though all but the Unchoked network slow their increase even
before the startup stage is complete. he Unchoked graph reaches its inal value
early in the transient stage, after which none of the networks vary much at all.
he characteristic path lengths for the Connection, Interest, and Download
networks are short, due mostly to the density of the graph (430 nodes with an
average degree of 65). he Unchoked graph's characteristic path length is larger
due to the reduced average degree (about 4) of nodes in this graph. Also shown
are the characteristic path lengths of a randomly constructed graph [11] with the
same number of nodes and edges, and with similar limits on the node degree.
he random graph results are almost not visible, as the Connection, Interest, and
Download graphs have nearly the same characteristic path lengths as their random
graph counterparts. he only exception is the Unchoked graph, which is about 10%
larger, probably due to the scale-free nature of this graph which causes it to vary
slightly from being truly random.
