×

Large low-diameter graphs are good expanders. (English) Zbl 1482.05084

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 71, 15 p. (2018).
Summary: We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that “sufficiently large” graphs of fixed diameter and degree must be “good” expanders. We prove this statement for various definitions of “sufficiently large” multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research.
For the entire collection see [Zbl 1393.68010].

MSC:

05C12 Distance in graphs
05C48 Expander graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 9(04):585-603, 2007. · Zbl 1140.60301
[2] Baba Arimilli, Ravi Arimilli, Vicente Chung, Scott Clark, Wolfgang Denzel, Ben Drerup, Torsten Hoefler, Jody Joyner, Jerry Lewis, Jian Li, et al. The percs high-performance inter-connect. In High Performance Interconnects (HOTI), 2010 IEEE 18th Annual Symposium on, pages 75-82. IEEE, 2010.
[3] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. · Zbl 1193.68112
[4] Eiichi Bannai and Tatsuro Ito. Regular graphs with excess one. Discrete Mathematics, 37(2):147-158, 1981. · Zbl 0473.05036
[5] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phe-nomena. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 463-472. ACM, 2003. · Zbl 1192.52025
[6] J-C Bermond, Nathalie Homobono, and Claudine Peyrat. Large fault-tolerant interconnec-tion networks. Graphs and Combinatorics, 5(1):107-123, 1989. · Zbl 0672.94021
[7] Jean-Claude Bermond. De bruijn and kautz networks: a competitor for the hypercube? Hypercube and distributed computers, pages 279-293, 1989.
[8] Maciej Besta and Torsten Hoefler. Slim fly: A cost effective low-diameter network topo-logy. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 348-359. IEEE Press, 2014.
[9] Norman Biggs. Algebraic graph theory. Cambridge university press, 1993. · Zbl 0797.05032
[10] B Bollobás. Extremal Graph Theory. Dover Publications, 1978. · Zbl 0419.05031
[11] C Bordenave. A new proof of friedman’s second eigenvalue theorem and its extension to random lifts. Preprint, available at https://arxiv.org/abs/1502.04482, 2015.
[12] William G Brown. On graphs that do not contain a thomsen graph. Canad. Math. Bull, 9(2):1-2, 1966. · Zbl 0178.27302
[13] Eduardo A Canale and José Gómez. Asymptotically large (δ, d)-graphs. Discrete applied mathematics, 152(1):89-108, 2005. · Zbl 1080.05027
[14] Oliver Collins, Sam Dolinar, Robert McEliece, and Fabrizio Pollara. A vlsi decomposition of the de bruijn graph. Journal of the ACM (JACM), 39(4):931-948, 1992. · Zbl 0809.94038
[15] DG De Bruijn. A combinatorial problem, koninklijke nederlandsche academie van wetenschappen et amsterdam. Proceedings Qt the Section gt Sciences, 49:27, 1946.
[16] Charles Delorme. Grands graphes de degré et diametre donnés. European Journal of Combinatorics, 6(4):291-302, 1985.
[17] Charles Delorme. Large bipartite graphs with given degree and diameter. Journal of graph theory, 9(3):325-334, 1985. · Zbl 0623.05048
[18] Michael Dinitz, Michael Schapira, and Asaf Valadarsky. Explicit expanding expanders. Algorithmica, pages 1-21, 2016. doi:10.1007/s00453-016-0269-x. · Zbl 1372.68208 · doi:10.1007/s00453-016-0269-x
[19] Bernard Elspas, William H Kautz, and James Turner. Theory of cellular logic networks and machines. Technical report, DTIC Document, 1968.
[20] Paul Erdos, Alfréd Rényi, and VT Sós. On a problem in the theory of graphs. Publ. Math. Inst. Hungar. Acad. Sci, 7:215-235, 1962.
[21] A-H Esfahanian and S. Louis Hakimi. Fault-tolerant routing in de bruijn comrnunication networks. IEEE Transactions on Computers, 100(9):777-788, 1985. · Zbl 0565.94027
[22] Harold Fredricksen. A survey of full length nonlinear shift register cycle algorithms. SIAM review, 24(2):195-221, 1982. · Zbl 0482.68033
[23] D. Guo, T. Chen, D. Li, M. Li, Y. Liu, and G. Chen. Expandable and cost-effective network structures for data centers using dual-port servers. IEEE Transactions on Computers, 62(7):1303-1317, July 2013. doi:10.1109/TC.2012.90. · Zbl 1365.68048 · doi:10.1109/TC.2012.90
[24] Ki-ichiro Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties., pages 211-280, 1989. · Zbl 0709.22005
[25] Alan J Hoffman and Robert R Singleton. On moore graphs with diameters 2 and 3. IBM Journal of Research and Development, 4(5):497-504, 1960. · Zbl 0096.38102
[26] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. · Zbl 1147.68608
[27] Brian Karrer, Mark EJ Newman, and Lenka Zdeborová. Percolation on sparse networks. Physical review letters, 113(20):208702, 2014.
[28] Simon Kassing, Asaf Valadarsky, Gal Shahaf, Michael Schapira, and Ankit Singla. Beyond fat-trees without antennae, mirrors, and disco-balls. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pages 281-294. ACM, 2017.
[29] John Kim, Wiliam J Dally, Steve Scott, and Dennis Abts. Technology-driven, highly-scalable dragonfly topology. In ACM SIGARCH Computer Architecture News, volume 36, pages 77-88. IEEE Computer Society, 2008.
[30] John Kim, William J Dally, and Dennis Abts. Flattened butterfly: a cost-efficient topology for high-radix networks. In ACM SIGARCH Computer Architecture News, volume 35, pages 126-137. ACM, 2007.
[31] John Kim, William J Dally, Steve Scott, and Dennis Abts. Cost-efficient dragonfly topology for large-scale systems. In Optical Fiber Communication Conference, page OTuI2. Optical Society of America, 2009.
[32] Michihiro Koibuchi, Hiroki Matsutani, Hideharu Amano, D Frank Hsu, and Henri Casanova. A case for random shortcut topologies for hpc interconnects. In Computer Architecture (ISCA), 2012 39th Annual International Symposium on, pages 177-188. IEEE, 2012.
[33] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zde-borová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935-20940, 2013. · Zbl 1359.62252
[34] F Thomson Leighton. Introduction to parallel algorithms and architectures: Arrays• trees• hypercubes. Elsevier, 2014.
[35] Abraham Lempel. On a homomorphism of the de bruijn graph and its applications to the design of feedback shift registers. IEEE Transactions on Computers, 100(12):1204-1209, 1970. · Zbl 0225.94028
[36] Nathan Linial, Avner Magen, and Assaf Naor. Girth and euclidean distortion. Geometric & Functional Analysis GAFA, 12(2):380-394, 2002. · Zbl 0991.05037
[37] Ankit Singla Chi-Yao Hong Lucian and Popa Brighten Godfrey. Jellyfish: Networking data centers randomly. CoRR, abs/1110.1687, 2011. URL: http://arxiv.org/abs/1110.1687.
[38] Travis Martin, Xiao Zhang, and MEJ Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.
[39] Brendan D McKay, Mirka Miller, and Jozef Širáň. A note on large graphs of diameter two and given maximum degree. Journal of Combinatorial Theory, Series B, 74(1):110-118, 1998. · Zbl 0911.05031
[40] Carl D Meyer. Matrix analysis and applied linear algebra, volume 2. Siam, 2000. · Zbl 0962.15001
[41] Mirka Miller and Jozef Širán. Moore graphs and beyond: A survey of the degree/diameter problem. Electronic Journal of Combinatorics, 61:1-63, 2005. · Zbl 1079.05043
[42] Dhiraj K Pradhan. Fault-tolerant multiprocessor link and bus network architectures. IEEE Trans. Comput.;(United States), 100, 1985. · Zbl 0547.94020
[43] Ankit Singla, P Brighten Godfrey, and Alexandra Kolla. High throughput data center topology design. In 11th USENIX Symposium on Networked Systems Design and Imple-mentation (NSDI 14), pages 29-41, 2014.
[44] Patrick Solé. The second eigenvalue of regular graphs of given girth. Journal of Combinat-orial Theory, Series B, 56(2):239-249, 1992 · Zbl 0723.05084
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.