Node diversification in complex networks by decentralized colouring
Abstract
We develop a decentralized colouring approach to diversify the nodes in a complex network. The key is the introduction of a local conflict index (LCI) that measures the colour 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 colouring as measured by the size of the largest colour-induced connected component. Interestingly, for scale-free networks further improvement of diversity can be achieved by tuning a degree-biasing weighting parameter in the LCI.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 03, 2018
- Source ID
- 10.1093/comnet/cny031
Entities
People
- David J Myers
- Jie Sun
- Richard Garcia-lebron
- Shouhuai Xu
Organizations
- Air Force Research Laboratory
- Army Research Office
- Clarkson University
- National Science Foundation
- Simons Foundation
- University of Texas at San Antonio