Analytical solution for the size of the minimum dominating set in complex networks
Analytical solution for the size of the minimum dominating set in complex networks
复制标题
DOI：
10.1142/s1793962317500052
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
J. Nacher;T. Ochiai
中科院分区：
文献类型：
--
作者：
J. Nacher;T. Ochiai
支配是图论中发展最快的领域，在现实世界的应用中具有深刻的多样性和影响力，例如最近的突破性方法，该方法可以识别富含癌症相关基因的蛋白质的优化子集。尽管它的概念简单，支配是一个经典的NP完全决策问题，这使得解析解难以捉摸，并提出了困难的优化算法设计在一个大型网络中找到一个支配集的最小基数。本文首次将腔方法与超离散化方法相结合，得到了最小控制集密度的近似解析解。导出的方程允许我们仅使用给定网络的度分布信息作为输入来计算MDS的大小。
Domination is the fastest-growing field within graph theory with a profound diversity and impact in real-world applications, such as the recent breakthrough approach that identifies optimized subsets of proteins enriched with cancer-related genes. Despite its conceptual simplicity, domination is a classical NP-complete decision problem which makes analytical solutions elusive and poses difficulties to design optimization algorithms for finding a dominating set of minimum cardinality in a large network. Here we derive for the first time an approximate analytical solution for the density of the minimum dominating set (MDS) by using a combination of cavity method and Ultra-Discretization (UD) procedure. The derived equation allows us to compute the size of MDS by only using as an input the information of the degree distribution of a given network.