Topology Control - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 62

4.4 Unstructured Topology Control
Dale et al. [Dale et al., 2008] proposed novel modifications to the tracker
servers' peer selection mechanisms in BitTorrent. The objective is to make a
BitTorrent network exhibit small-world characteristics. Their proposed mod-
ifications are based on a detailed theoretical analysis described below.
To create a small-world network with peers having a known maximum
degree, Dale et al. first try to maximize the clustering coe cient of a regular
graph of the peers. Cliques are considered for this purpose because a network of
cliques has a perfect clustering coe cient of 1 and each clique has a maximum
node degree. Specifically, a single edge is deleted from each clique and the two
incident nodes of the deleted edge are connected to neighboring cliques. This
is done uniformly for all cliques in order to maintain regularity. Consequently,
a cycle of k identical n-cliques is formed, where n is the maximum node degree
and k = N/n (N is the number of nodes).
Now because the network comprises a cycle of identical cliques, it su ces
to compute the clustering coe cient of a single n-clique. Recall that each
n-clique has two kinds of nodes: (1) n−2 interior nodes connected only to
neighbors in the same clique, and (2) two border nodes that connect to neigh-
bor cliques. Notice that the clustering coe cient of a node is equal to the
number of triangles including the node. Thus, Dale et al. check how many
triangles are lost by deleting the single edge so as to connect to neighboring
cliques. Obviously, because the interior nodes lose only a single triangle after
one edge is deleted, we have:

(n−1)(n−2)
2 −1
(n−1)(n−2)
2

= 1− 2
(n−1)(n−2)

C i = (4.4)

On the other hand, the border nodes lose a triangle for each node that
was incident with the missing edge. Because there are n−2 such nodes, the
clustering coe cient C b is given by:

(n−1)(n−2)
2 −(n−2)
(n−1)(n−2)
2

= 1− 2
(n−1)

C b = (4.5)

Now considering the average over the n-clique, the clustering coe cient of
the entire network is given by:

(n−2)C i + 2C b
n

= 1− 6
n(n−1)

C G = (4.6)

Next we consider the diameter and characteristic path length of the net-
work constructed by Dale et al.'s method. Observe that we need to traverse
three edges to get past a single clique. In the worst case, we need to traverse