Document Open Access Logo

Large Low-Diameter Graphs are Good Expanders

Authors Michael Dinitz, Michael Schapira, Gal Shahaf

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.71.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Michael Dinitz
  • Dept. of Computer Science, Johns Hopkins University, Baltimore, US
Michael Schapira
  • School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel
Gal Shahaf
  • Dept. of Mathematics, The Hebrew University, Jerusalem, Israel.

Funding

  • Dinitz, Michael: Supported in part by NSF awards 1464239 and 1535887

Cite As Get BibTex

Michael Dinitz, Michael Schapira, and Gal Shahaf. Large Low-Diameter Graphs are Good Expanders. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.71

Abstract

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Spectra of graphs
  • Mathematics of computing → Extremal graph theory
  • Networks → Network design principles
  • Networks → Network structure
Keywords
  • Network design
  • Expander graphs
  • Spectral graph theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. Google Scholar
  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 interconnect. In High Performance Interconnects (HOTI), 2010 IEEE 18th Annual Symposium on, pages 75-82. IEEE, 2010. Google Scholar
  3. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  4. Eiichi Bannai and Tatsuro Ito. Regular graphs with excess one. Discrete Mathematics, 37(2):147-158, 1981. Google Scholar
  5. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 463-472. ACM, 2003. Google Scholar
  6. J-C Bermond, Nathalie Homobono, and Claudine Peyrat. Large fault-tolerant interconnection networks. Graphs and Combinatorics, 5(1):107-123, 1989. Google Scholar
  7. Jean-Claude Bermond. De bruijn and kautz networks: a competitor for the hypercube? Hypercube and distributed computers, pages 279-293, 1989. Google Scholar
  8. Maciej Besta and Torsten Hoefler. Slim fly: A cost effective low-diameter network topology. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 348-359. IEEE Press, 2014. Google Scholar
  9. Norman Biggs. Algebraic graph theory. Cambridge university press, 1993. Google Scholar
  10. B Bollobás. Extremal Graph Theory. Dover Publications, 1978. Google Scholar
  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. Google Scholar
  12. William G Brown. On graphs that do not contain a thomsen graph. Canad. Math. Bull, 9(2):1-2, 1966. Google Scholar
  13. Eduardo A Canale and José Gómez. Asymptotically large (δ, d)-graphs. Discrete applied mathematics, 152(1):89-108, 2005. Google Scholar
  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. Google Scholar
  15. DG De Bruijn. A combinatorial problem, koninklijke nederlandsche academie van wetenschappen et amsterdam. Proceedings Qt the Section gt Sciences, 49:27, 1946. Google Scholar
  16. Charles Delorme. Grands graphes de degré et diametre donnés. European Journal of Combinatorics, 6(4):291-302, 1985. Google Scholar
  17. Charles Delorme. Large bipartite graphs with given degree and diameter. Journal of graph theory, 9(3):325-334, 1985. Google Scholar
  18. Michael Dinitz, Michael Schapira, and Asaf Valadarsky. Explicit expanding expanders. Algorithmica, pages 1-21, 2016. URL: http://dx.doi.org/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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  22. Harold Fredricksen. A survey of full length nonlinear shift register cycle algorithms. SIAM review, 24(2):195-221, 1982. Google Scholar
  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. URL: http://dx.doi.org/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. Google Scholar
  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. Google Scholar
  26. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  27. Brian Karrer, Mark EJ Newman, and Lenka Zdeborová. Percolation on sparse networks. Physical review letters, 113(20):208702, 2014. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  33. Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935-20940, 2013. Google Scholar
  34. F Thomson Leighton. Introduction to parallel algorithms and architectures: Arraysperiodcentered treesperiodcentered hypercubes. Elsevier, 2014. Google Scholar
  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. Google Scholar
  36. Nathan Linial, Avner Magen, and Assaf Naor. Girth and euclidean distortion. Geometric &Functional Analysis GAFA, 12(2):380-394, 2002. Google Scholar
  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. Google Scholar
  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. Google Scholar
  40. Carl D Meyer. Matrix analysis and applied linear algebra, volume 2. Siam, 2000. Google Scholar
  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. Google Scholar
  42. Dhiraj K Pradhan. Fault-tolerant multiprocessor link and bus network architectures. IEEE Trans. Comput.;(United States), 100, 1985. Google Scholar
  43. Ankit Singla, P Brighten Godfrey, and Alexandra Kolla. High throughput data center topology design. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), pages 29-41, 2014. Google Scholar
  44. Patrick Solé. The second eigenvalue of regular graphs of given girth. Journal of Combinatorial Theory, Series B, 56(2):239-249, 1992. Google Scholar
  45. Gabor Szeg. Orthogonal polynomials, volume 23. American Mathematical Soc., 1939. Google Scholar
  46. Asaf Valadarsky, Gal Shahaf, Michael Dinitz, and Michael Schapira. Xpander: Towards optimal-performance datacenters. In Proceedings of the 12th International on Conference on Emerging Networking EXperiments and Technologies, CoNEXT '16, pages 205-219, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2999572.2999580.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact