How does NKN perform efficient decentralization

Due to the dynamical nature of NKN, network topology between nodes is constantly updating. Proper updating mechanism is critical to achieve decentralization of the resulting topology. If, for example, the updating mechanism is chosen such that a newly joined node has higher chance to choose node with more neighbors to be its neighbor, and the probability to choose a node is proportional to the degree of that node, then the resulting network will be scale-free: the degree distribution follows a power law form. Such networks have centralized hubs defined by nodes with huge degree. Although hubs could potentially increase efficiency, they make network less robust as the failure of hubs will have much larger impact than the failure of other nodes.

One of the NKN’s goals is to design and build networks that are decentralized while still being efficient in information transmission. This should be done by using a proper topology updating mechanism that considers both algorithm and incentive. On the algorithm side, neighbors should be sampled and chosen randomly; on the incentive side, reward for data transmission should be sublinear (grows slower than linear function) so that hubs are discouraged. Sparse random network is one possible topology that could be generated from such mechanism. It is decentralized and thus robust to the failure of any node, while still being efficient in routing due to its small network diameter.