City University of Hong Kong

EE 6605

5-1 Internet has many small building blocks as those shown in the following figure, called motif
of type (a), type (b), ... , type (f) here.
(a) (b) (c) (d) (e) (f)
(i) Rank the above motifs in terms of their robustness against node-removal attack, from the
strongest to the weakest.
(ii) From your above ranking, comment whether the "coreness" values can be used as a
unique measure of the robustness against node-removal attack?
5-2 Consider the following undirected and unweighted network:
(i) Convert the network to be a weighted network, in such a way that the weight of the edge
connecting node i and node j is defined as wij  kik j , where ki is the degree of node i
and
k j is the degree of node j . For every edge in the network, mark its weight nearby on
the graph.
(ii) For the weighted network you obtained in part (i), a “distance” between two adjacent
nodes may be defined as the reciprocal of the edge weight between them, namely,
dij 1/ wij . Convert all the weights to distances on the above-obtained weighted network,
and mark each distance nearby on the graph.
(iii) If the network is part of the Internet, and all nodes are AS, explain why the abovedefined "distance" is meaningful.