EE6605 HW#2 Solutions 2020 2-1
Model A: The resultant network is a homogeneous network because the new incoming edges tend to connect to small nodes, where the attachment probability is larger for smaller degrees. As the process continues, more and more small-degree nodes receive preferential attachments from new nodes, so they become bigger. Thus, gradually, every node has about the same degree. The resultant network will be similar to a (growing and homogeneous) random network.
Note that the basic random-graph model is non-growing, which does not imply that there is no other growing random-graph network; the basic scale-free network is generated via preferential attachment, which does not imply that there is no other (non-scale-free) network also generated via preferential attachment.
Model B: The resultant network is actually the “complementary network” of a random network (homogenous), therefore is also a random network (also homogenous).
2-2
(i) is bad and (ii) is good technically. Because following rule (i) to do rewiring, there is a possibility that before a certain node the edge is disconnected at the last end, but after this same node the next edge is disconnected at the first end. As a result, this node will become isolated (see the figure below) therefore will be removed. Following rule (ii), however, no node can become isolated because the rewired edge will connect the original node to another node in the network.
become isolated
2-3
rewiring
(a)
Left: 𝑃(1,2)=1×0 =0, 𝑃(1,3)=1×2 =1, 𝑃(2,2)=2×0 =0, 𝑃(2,3)=1×2 =1, 𝑃(3,3)=2×1 =1
2×6 2×6 6 2×6 2×6 6 2×6 6
Right: 𝑃(1,2)=1×1= 1, 𝑃(1,3)=1×3=1, 𝑃(2,2)=2×0=0, 𝑃(2,3)=1×1= 1, 𝑃(3,3)=2×1=1 2×6 12 2×6 4 2×6 2×6 12 2×6 6
(b)
√3×3=3, √3×1=√3, √3×2=6, √3×1=√3, √3×1=√3, √2×1=√2