CS-7280 L4: Degree-preserving Randomizaon
L4: Degree-preserving Randomization : Network Science – CS-7280-O01
Degree Preserving Randomization, Figure 4.17 from networksciencebook.com by Albert-László Barabási
Suppose that you analyze a certain network G and you find it has an interesting property P. For example, P may be one of the robustness properties we discussed in the previous page about the size of the largest connected component under random or targeted node removals. How can you check statistically whether P is caused by the degree distribution of the network G (as opposed to other network characteristics)?
Copyright By PowCoder代写 加微信 powcoder
One approach to do is to ”randomize” the network G but without modifying the degree of any node. If we have a way to do so, we can create a large number of “degree-preserving” random networks – and then examine whether these networks also exhibit the property P. To make the analysis convincing we can also
https://gatech. instructure. com/courses/265324/pages/l4-degree-preserving-randomization?module_item_id=2520292 1/2
9/14/22, 6:54 AM L4: Degree-preserving Randomization : Network Science – CS-7280-O01
create another ensemble of randomized networks that do NOT have the same degree distribution with G but that maintain the same number of nodes and edges. Let us call these networks ”fully randomized”.
If the property P of G is present in the degree-preserving randomized networks – but P is not present in the fully randomized networks, we can be confident that the property P is a consequence of the degree distribution of G and not of any other property of G.
To perform ”full randomization”, we can simply pick each edge (S1, T1) of G and change it to (S1, T2), where T2 is a randomly selected node. Note that this does not change the number of nodes or edges (and so the network density remains the same). The degree distribution however can change significantly.
To perform “degree-preserving randomization”, we can pick two random edges(S1, T1) and (S2, T2) and rewire them to (S1,T2) and (S2, T1). Note that this approach preserves the degree of every node. This approach is repeated until we have rewired each edge at least once.
The visualization at the lower part of the panel shows an example of a power-law network and two randomized networks. The degree-preserving network maintains the presence of hubs as well as the connected nature of the original network. The fully randomized network on the other hand does not have hubs (and it could even include disconnected nodes – even though that does not happen in this example).
Food for Thought
There are more randomization approaches that can preserve more network properties than the degree distribution. How would you randomize a directed network so that the in-degree and the out-degree distributions remain the same?
https://gatech. instructure. com/courses/265324/pages/l4-degree-preserving-randomization?module_item_id=2520292 2/2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com