Format

Send to

Choose Destination
PLoS One. 2016 Jun 21;11(6):e0157868. doi: 10.1371/journal.pone.0157868. eCollection 2016.

Analysis of the Effect of Degree Correlation on the Size of Minimum Dominating Sets in Complex Networks.

Author information

1
Department of Bioscience and Bioinformatics, Kyushu Institute of Technology, Iizuka, Fukuoka, Japan.
2
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan.

Abstract

Network controllability is an important topic in wide-ranging research fields. However, the relationship between controllability and network structure is poorly understood, although degree heterogeneity is known to determine the controllability. We focus on the size of a minimum dominating set (MDS), a measure of network controllability, and investigate the effect of degree-degree correlation, which is universally observed in real-world networks, on the size of an MDS. We show that disassortativity or negative degree-degree correlation reduces the size of an MDS using analytical treatments and numerical simulation, whereas positive correlations hardly affect the size of an MDS. This result suggests that disassortativity enhances network controllability. Furthermore, apart from the controllability issue, the developed techniques provide new ways of analyzing complex networks with degree-degree correlations.

PMID:
27327273
PMCID:
PMC4915616
DOI:
10.1371/journal.pone.0157868
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for Public Library of Science Icon for PubMed Central
Loading ...
Support Center