Self-Adjusting Networks
Network size 30 * 30. Number of clusters 8, 50% of nodes are inactive
In this animation we can see how a local greedy switching algorithm adjusts the network so that the nodes belonging to the same cluster (same color) will be located closer together thus, minimizing the expected path (route) length. Nodes surrounded by a black rectangle are the centers of their clusters.
The algorithm goes as following. Every node can switch (exchange locations) with its direct neighbor (any node at the distance of 1 hop in torus) or with a node that is located at the distance 3 but not at the same line (i.e., a node that can be reached by a move of a chess knight). The switch is performed only if the expected path length of the network decreases as a result of the switch.
In the animation bellow we have 900 nodes randomly separated into 16 clusters, i.e., there are in average 900/16 nodes in every cluster.
In the second animation bellow, we have 450 inactive randomly located nodes, and the rest 450 nodes are separated into 8 clusters, i.e., there are in average 450/8 = 900/16 nodes in every cluster.