Node Diversification in Complex Networks by Decentralized Coloring

Abstract

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.

References in corpus (9)

• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Synchronization in complex networks
• Critical phenomena in complex networks
• Epidemic dynamics and endemic states in complex networks
• Self-similar community structure in organisations
• Efficient Immunization Strategies for Computer Networks and Populations
• Exact solution of site and bond percolation on small-world networks