Node Diversification in Complex Networks by Decentralized Coloring

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-11
Main Authors: Garcia-Lebron, Richard, Myers, David J, Xu, Shouhuai, Sun, Jie
Format: Article
Language:English
Subjects:
Color
Coloring
Networks
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1811.11197