Dominating complex networks by identifying minimum skeletons

Peng Gang Sun, Xiaoke Ma and Juan Chi

Chaos, Solitons & Fractals, 2017, vol. 104, issue C, 182-191

Abstract: By identifying important nodes (driver nodes), the minimum dominating set (MDS) provides an effective model to dominate complex networks. However, in many networks, the skeleton of driver nodes selected using the MDS is usually connected, which motivates us to explore a new framework and try to dominate a network by identifying its minimum skeleton. We define the minimum skeleton of a graph as a subgraph induced from the nodes within the minimum connected dominating set (MCDS), and the problem can be solved by a maximum spanning tree-based algorithm. For the domination of complex networks, in general, the MCDS needs more driver nodes, and is more robust than the MDS against link attack. Interestingly, for the MDS, it is harder to control the networks with weaker communities, while for the MCDS, this finding tends to be observed on the networks with homogeneous community sizes. In addition, for the MDS, the curves for the percentage of driver nodes on the networks with variable community strengths shift downward as the average degree of the networks increases, while for the MCDS, the curves, like power functions rotate clockwise. For the both, it tends to be harder to control the networks with stronger overlapping, and the number of driver nodes is dependent on the networks’ degree distribution.

Keywords: Minimum skeleton; Minimum connected dominating set (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077917303429
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:104:y:2017:i:c:p:182-191

DOI: 10.1016/j.chaos.2017.08.014

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().