×

Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition. (English) Zbl 1436.68239

Summary: The average path length in a network is an important parameter for measuring the end-to-end delay for message delivery. The delay between an arbitrary pair of nodes is smaller if the average path length is low. It is possible to reduce the average path length of a network by adding one or more additional links between pairs of nodes. However, a naïve algorithm is often very expensive for determining which additional link can reduce the average path length in a network the most. In this paper, we present two efficient algorithms to minimize the average network path length by link addition. Our algorithms can process significantly larger networks compared to the naïve algorithm. We present simple implementations of our algorithms, as well as performance studies.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Comellas, F.; Sampels, M., Deterministic small-world networks, Phys. A Stat. Mech. Appl., 309, 1, 231-235 (2002) · Zbl 0995.60103
[2] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA
[3] Chang, M. F.; Cong, J.; Kaplan, A.; Naik, M.; Reinman, G.; Socher, E.; Tam, S. W., CMP network-on-chip overlaid with multi-band RF-interconnect, Proc. International Symposium on High Performance Computer Architecture, 191-202 (2008)
[4] Chang, M. F.; Socher, E.; Tam, S. W.; Cong, J.; Reinman, G., RF interconnects for communications on-chip, Proc. 2008 International Symposium on Physical Design, 78-83 (2008)
[5] Fall, K., A delay-tolerant network architecture for challenged internets, Proc. ACM SIGCOMM, 27-34 (2003)
[6] A. Gozzard, Thesis available from, http://www.ucc.gu.uwa.edu.au/ gozzarda/minapl_thesis.pdf; A. Gozzard, Thesis available from, http://www.ucc.gu.uwa.edu.au/ gozzarda/minapl_thesis.pdf
[7] Gaur, N.; Chakraborty, A.; Manoj, B. S., Delay optimized small-world networks, IEEE Commun. Lett., 18, 11, 1939-1942 (2014)
[8] Jin, E. M.; Girvan, M.; Newman, M., The Structure of Growing Social Networks (2001)
[9] Milgram, S., The small-world problem, Psychol. Today, 1, 1, 61-67 (1967)
[10] Meyerson, A.; Tagiku, B., Minimizing average shortest path distances via shorcut edge addition, Proc. 13th International Workshop on Approximation, Randomization and Combinatorial Optimization, LNCS, vol. 5687, 272-285 (2009) · Zbl 1255.68307
[11] Newman, M., The structure and function of complex networks, SIAM Rev., 45, 2, 167-256 (2003) · Zbl 1029.68010
[12] Ogras, U.; Marculescu, R., It’s a small world after all: Noc performance optimization via long-range link insertion, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 14, 7, 693-706 (2006)
[13] Pickavet, M.; Demeester, P., A zoom-in approach to design SDH mesh restorable networks, J. Heurist., 6, 107-130 (2000) · Zbl 1064.90586
[14] Watts, D.; Strogatz, S., Collective dynamics of small-world network, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139
[15] Lu, Z.; Su, Y.; Guo, S., Deterministic scale-free small world networks of arbitrary order, Phys. A Stat. Mech. Appl., 392, 17, 3555-3562 (2013) · Zbl 1395.05161
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.