Node Diversification in Complex Networks by Decentralized Coloring
This work addresses node diversification in complex networks, which is incremental as it builds on existing coloring methods by adding a decentralized and tunable approach.
The paper tackled the problem of diversifying nodes in complex networks by introducing a decentralized coloring approach with a local conflict index, resulting in significantly outperforming random coloring in reducing the size of the largest color-induced connected component, with further improvements possible in scale-free networks through parameter tuning.
We develop a decentralized coloring approach to diversify the nodes in a complex network. The key is the introduction of a local conflict index that measures the color conflicts arising at each node which can be efficiently computed using only local information. We demonstrate via both synthetic and real-world networks that the proposed approach significantly outperforms random coloring as measured by the size of the largest color-induced connected component. Interestingly, for scale-free networks further improvement of diversity can be achieved by tuning a degree-biasing weighting parameter in the local conflict index.