×

Mathematical programming models for some smallest-world problems. (English) Zbl 1086.90056

Summary: Given a weighted graph \(G\), in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph \(G\). Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0-1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the ”small-worldness” of graphs.

MSC:

90C35 Programming involving graphs or networks
05C80 Random graphs (graph-theoretic aspects)
90C09 Boolean programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, R.; Barabasi, A.-L., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[2] Albert, R.; Barabasi, A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 47-97 (2002) · Zbl 1205.82086
[3] Barabasi, A.-L., LinkedHow Everything is Connected to Everything Else and What it Means (2003), Plume: Plume New York
[4] Buchanan, M., NexusSmall Worlds and the Groundbreaking Science of Networks (2002), W. W. Norton & Co.: W. W. Norton & Co. New York
[5] Chepoi, V.; Vaxes, Y., Augmenting trees to meet biconnectivity and diameter constraints, Algorithmica, 33, 243-262 (2002) · Zbl 1052.68099
[6] K.-F. Chung, A mathematical programming approach for the design of aircraft wings, Ph.D. Dissertation, The University of Texas at Arlington, 1997, pp. 58-62.; K.-F. Chung, A mathematical programming approach for the design of aircraft wings, Ph.D. Dissertation, The University of Texas at Arlington, 1997, pp. 58-62.
[7] Comellas, F.; Sampels, M., Deterministic small-world networks, Physica AStatist. Mech. Appl., 309, 231-235 (2002) · Zbl 0995.60103
[8] Diestel, R., Graph Theory (2000), Springer: Springer Berlin, New York · Zbl 0945.05002
[9] Guare, J., Six Degrees of SeparationA Play (1990), Vintage Books: Vintage Books New York
[10] W. Härdle, L. Simarm, Applied Statistical Analysis, e-book, , Springer, Berlin, 2003.; W. Härdle, L. Simarm, Applied Statistical Analysis, e-book, , Springer, Berlin, 2003.
[11] Higham, D., Unravelling small world networks, J. Comput. Appl. Math., 158, 61-74 (2003) · Zbl 1028.65034
[12] \( \sim;\).; \( \sim;\).
[13] .; .
[14] E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, Progress in integer programming: an exposition, Technical Report TLI/LEC-97-02, Georgia Institute of Technology, Atlanta, GA, 1997.; E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, Progress in integer programming: an exposition, Technical Report TLI/LEC-97-02, Georgia Institute of Technology, Atlanta, GA, 1997. · Zbl 1052.90048
[15] Kleinberg, J., The small-world phenomenonan algorithmic perspective, (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000), Association of Computing Machinery: Association of Computing Machinery New York), 163-170 · Zbl 1296.05181
[16] Latora, V.; Marchiori, M., Efficient behavior of small-world networks, Phys. Rev. Lett., 87, 1-4,198701 (2001)
[17] Li, C.-L.; McCormick, S.; Simchi-Levi, D., On the minimum-cardinality bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems, Oper. Res. Lett., 11, 303-308 (1992) · Zbl 0763.90085
[18] Milgram, S., The small world problem, Psychol. Today, 2, 60-67 (1967)
[19] Newman, M., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[20] Nishikawa, T.; Motter, A.; Lai, Y.-C.; Hoppensteadt, F., Smallest small-world network, Phys. Rev. E, 66, 1-5,046139 (2002)
[21] Schoone, A.; Bodlaender, H.; van Leeuwen, J., Diameter increase caused by edge deletion, J. Graph Theory, 11, 409-427 (1987) · Zbl 0646.05038
[22] Strogatz, S., Exploring complex networks, Nature, 410, 268-276 (2001) · Zbl 1370.90052
[23] Strogatz, S., SyncThe Emerging Science of Spontaneous Order (2003), Hyperion Press: Hyperion Press New York
[24] Travers, J.; Milgram, S., An experimental study of the small world problem, Sociometry, 32, 425-443 (1969)
[25] Wang, X.; Chen, G., Complex networkssmall-world, scale-free and beyond, IEEE Circuits Syst. Mag., 3, 6-20 (2003)
[26] Watts, D.; Strogatz, S., Collective dynamics of small-world networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[27] Watts, D. J., Small Worlds (1999), Princeton University Press: Princeton University Press Princeton
[28] Watts, D. J., Six Degrees, The Science of a Connected Age (2004), W. W. Norton & Co.: W. W. Norton & Co. New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.