Research PapersNo Access

Analytical solution for the size of the minimum dominating set in complex networks

Jose C. Nacher

Department of Information Science, Faculty of Science, Toho University, Miyama 2-2-1, Funabashi, Chiba 274-8510, Japan

E-mail Address: nacher@is.sci.toho-u.ac.jp

Corresponding authors.

Search for more papers by this author

and

Tomoshiro Ochiai

Faculty of Social Information Studies, Otsuma Women’s University, 2-7-1 Karakida, Tama-shi, Tokyo 206-8540, Japan

E-mail Address: ochiai@otsuma.ac.jp

Corresponding authors.

Search for more papers by this author

https://doi.org/10.1142/S1793962317500052Cited by:1 (Source: Crossref)

Abstract

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.

Keywords:

References

1. Newman M. E. J. , Networks: An Introduction, Oxford University Press, New York, 2010. Crossref, Google Scholar
2. Caldarelli G. , Scale-Free Networks: Complex Webs in Nature and Technology, Oxford University Press, Oxford, 2007. Crossref, Google Scholar
3. Barabási A.-L., Albert R. , Emergence of scaling in random networks, Science 286 :509, 1999. Crossref, Web of Science, Google Scholar
4. Pastor-Satorras R., Vespignani A. , Epidemic spreading in scale-free networks, Phys. Rev. Lett. 86 :3200, 2001. Crossref, Web of Science, Google Scholar
5. Cohen R., Erez K., ben-Avraham D., Havlin S. , Resilience of the internet to random breakdowns, Phys. Rev. Lett. 85 :4626, 2000. Crossref, Web of Science, Google Scholar
6. Albert R., Jeong H., Barabasi A.-L. , Error and attack tolerance of complex networks, Nature 406 :378, 2000. Crossref, Web of Science, Google Scholar
7. Motter A. E. , Cascade control and defense in complex networks, Phys. Rev. Lett. 93 :098701, 2004. Crossref, Web of Science, Google Scholar
8. Haynes T. W., Hedetniemi S. T., Slater P. J. , Fundamentals of Domination in Graphs, Pure Applied Mathematics, Chapman and Hall/CRC, New York, 1998. Google Scholar
9. Stojmenovic I., Seddigh M., Zunic J. , Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks, IEEE Trans. Parallel Distrib. Syst. 13 :14, 2002. Crossref, Web of Science, Google Scholar
10. Chen W., Lu Z., Wu W. , Dominating problems in swapped networks, Inform. Sci. 269 :286, 2014. Crossref, Web of Science, Google Scholar
11. Kelleher L., Cozzens M. , Dominating sets in social network graphs, Graphs. Math. Soc. Sci. 16 :267, 1988. Crossref, Web of Science, Google Scholar
12. Wang F. et al., On positive influence dominating sets in social networks, Theor. Comp. Sci. 412 :265, 2011. Crossref, Web of Science, Google Scholar
13. Eubank S., Anil Kumar V.S., Marathe M. V., Srinivasan A., Wang N. , Structural and algorithmic aspects of massive social networks, in SODA ’04 Proc. fifteenth Annual ACM-SIAM Symp. on Discrete algorithms, pp. 718–727 (2004). Google Scholar
14. Vazquez A. , Optimal drug combinations and minimal hitting sets, BMC Syst. Biol. 3 :81, 2009. Crossref, Web of Science, Google Scholar
15. Nacher J. C., Akutsu T. , Dominating scale-free networks with variable scaling exponent: heterogeneous networks are not difficult to control, New J. Phys. 14 :073005, 2012. Crossref, Web of Science, Google Scholar
16. Nacher J. C., Akutsu T. , Analysis on controlling complex networks based on dominating sets, J. Phys.: Conf. Ser. 410 :012104, 2013. Crossref, Google Scholar
17. Nacher J. C., Akutsu T. , Structural controllability of unidirectional bipartite networks, Sci. Rep. 3 :1647, 2013. Crossref, Web of Science, Google Scholar
18. Yang Y., Wang J., Motter A. E. , Network observability transitions, Phys. Rev. Lett. 109 :258701, 2012. Crossref, Web of Science, Google Scholar
19. Wuchty S. , Controllability in protein interaction networks, Proc. Natl. Acad. Sci. USA 111 :7156, 2014. Crossref, Web of Science, Google Scholar
20. Molnár F., Sreenivasan S., Szymanski B. K., Korniss G. , Minimum dominating sets in scale-free network ensembles, Sci. Rep. 3 :1736, 2013. Crossref, Web of Science, Google Scholar
21. Nacher J. C., Akutsu T. , Structurally robust control of complex networks, Phys. Rev. E 91 :012826, 2015. Crossref, Web of Science, Google Scholar
22. Molnár F., Derzsy N., Szymanski B. K., Korniss G. , Building damage-resilient dominating sets in complex networks against random and targeted attacks, Sci. Rep. 5 :8321, 2015. Crossref, Web of Science, Google Scholar
23. Garey M., Johnson D. S. , Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. Google Scholar
24. Cooper C., Zito M. , An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne–Goodman–Hedetniemi algorithm, Discrete Appl. Math. 157 :2010, 2009. Crossref, Web of Science, Google Scholar
25. Mezard M., Parisi G., Virasoro M. A. , Spin-Glass Theory and Beyond, Lecture notes in Physics, Vol. 9, World Scientific, Singapore, 1987. Google Scholar
26. Mezard M., Parisi G., Virasoro M. A. , Random free energies in spin glasses, J. Physique Lett. 46 :217, 1985. Crossref, Google Scholar
27. Weigt M., Hartmann A. K. , Number of guards needed by a Museum: A phase transition in vertex covering of random graphs, Phys. Rev. Lett. 84 :6118, 2000. Crossref, Web of Science, Google Scholar
28. Mezard M., Parisi G. , A replica analysis of the travelling salesman problem, J. Physique 47 :1285, 1986. Crossref, Web of Science, Google Scholar
29. Zdeborova L., Mezard M. , The number of matchings in random graphs, J. Stat. Mech. 2006 :P05003, 2006. Crossref, Web of Science, Google Scholar
30. Dall’Asta L., Pin P., Ramezanpour A. , Statistical mechanics of maximal independent sets, Phys. Rev. E 80 :061136, 2009. Crossref, Web of Science, Google Scholar
31. Lucibello C., Ricci-Tersenghi F. , The statistical mechanics of random set packing and a generalization of the karp-sipser algorithm, Int. J. Stat. Mech. 2014 :Article ID 136829, 2014. Crossref, Google Scholar
32. Bayati M., Borgs C., Braunstein A., Chayes J., Ramezanpour A., Zecchina R. , Statistical mechanics of steiner trees, Phys. Rev. Lett. 101 :037208, 2008. Crossref, Web of Science, Google Scholar
33. Liu Y.-Y., Slotine J.-J., Barabási A.-L. , Controllability of complex networks, Nature 473 :167, 2011. Crossref, Web of Science, Google Scholar
34. Mezard M., Parisi G. , The cavity method at zero temperature, J. Stat. Phys. 111 :1, 2003. Crossref, Web of Science, Google Scholar
35. Mezard M., Ricci-Tersenghi F., Zecchina R. , Two solutions to diluted $p$ $p$ -spin models and XORSAT problems, J. Stat. Phys. 111 :505, 2003. Crossref, Web of Science, Google Scholar
36. Rivoire O., Biroli G., Martin O. C., Mezard M. , Glass models on Bethe lattices, Eur. Phys. J. B 37 :55, 2004. Crossref, Web of Science, Google Scholar
37. Takahashi D., Satsuma J. , A soliton cellular automaton, J. Phys. Soc. Jpn. 59 :3514, 1990. Crossref, Google Scholar
38. Takahashi D., Tokihiro T., Grammaticos B., Ohta Y., Ramani A. , Constructing solutions to the ultradiscrete Painleve equations, J. Phys. A 30 :7953, 1997. Crossref, Google Scholar
39. Tokihiro T., Takahashi D., Matsukidaira J. , Box and ball system as a realization of ultradiscrete nonautonomous KP equation, J. Phys. A 33 :607, 2000. Crossref, Google Scholar
40. Tokihiro T., Takahashi D., Matsukidaira J., Satsuma J. , From soliton equations to integrable cellular automata through a limiting procedure, Phys. Rev. Lett. 76 :3247, 1996. Crossref, Web of Science, Google Scholar
41. Ochiai T., Nacher J. C. , Inversible Max-Plus algebras and integrable systems, J. Math. Phys. 46 :063507, 2005. Crossref, Web of Science, Google Scholar
42. Bayati M., Nair C., A rigorous proof of the cavity method for counting matchings, http://arxiv.org/abs/cond-mat/0607290. Google Scholar
43. Zhao J. H., Habibulla Y., Zhou H. J. , Statistical mechanics of the minimum dominating set problem, J. Stat. Phys. 159 :1154, 2015. Crossref, Web of Science, Google Scholar