article

Conductance and congestion in power law graphs

Authors:

Christos Gkantsidis,

Amin SaberiAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 31, Issue 1

Pages 148 - 159

https://doi.org/10.1145/885651.781046

Published: 10 June 2003 Publication History

Abstract

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees d_u and d_v we have O(d_u d_v) units of demand. Thus the total demand is O(n²). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O(n log² n). This is to be compared with a bound O(n²) that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.

References

[1]

L. Adamic. Zipf, power-laws, and pareto, a ranking tutorial. http://www.hpl.hp.com/shl/papers/ranking/, 2002.]]

[2]

S. Agarwal, L. Subramanian, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points web page. http://www.cs.berkeley.edu/~1sagarwal/research/BGP-hierarchy/, 2002.]]

[3]

W. Aiello, F. R. K. Chung, and L. Lu. A random graph model for power law graphs. In Proc. 41st Symposium on Foundations of Computer Science (FOCS), pages 171--180. IEEE, 2000.]]

Digital Library

[4]

W. Aiello, F. R. K. Chung, and L. Lu. Random evolution in massive graphs. In Proc. 42nd Symposium on Foundations of Computer Science (FOCS), pages 510--519. IEEE, 2001.]]

Digital Library

[5]

D. Alderson, J. Doyle, and W. Willinger. Toward an optimization-driven framework for designing and generating realistic internet topologies. In HotNets, 2002.]]

[6]

A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.]]

[7]

C. Berge. Graphs and Hypergraphs. North Holland Publishing Company, 1973.]]

Digital Library

[8]

Bob metcalfe eats his words. Internet Computing Online, 1(3), 1997. http://www.computer.org/internet/v1n3/eats9702.htm.]]

[9]

B. Bollobás. Random Graphs, 2nd Ed. Cambridge University Press, 2001.]]

[10]

B. Bollobás and O. Riordan. The diameter of scale-free graphs. Combinatorica, To appear.]]

[11]

B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18(3):279--290, 2001.]]

Digital Library

[12]

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomikns, and J. Wiener. Graph structure in the web. 9th International World Wide Web Conference (WWW9)/Computer Networks, 33(1-6):309--320, 2000.]]

Digital Library

[13]

A. Broido and K. Claffy. Internet topology: Connectivity of ip graphs. http://www.caida.org/outreach/papers/2001/OSD/, 2001.]]

[14]

C. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. The origins of power-laws in internet topologies revisited. In Proc. Infocom. IEEE, 2002.]]

[15]

F. Chung and L. Lu. The average distance in a random graph with given expected degree. Available at http://math.ucsd.edu/~1fan/inet.html.]]

[16]

F. Chung and L. Lu. Connected components in random graphs with given degree sequences. http://www.math.ucsd.edu/~1fan, 2002.]]

[17]

F. R. Chung. Spectral Graph Theory. American Mathematical Society Book Series, 1997.]]

[18]

C. Cooper and A. Frieze. A general model for web graphs. In ESA, pages 500--511, 2001.]]

Digital Library

[19]

J. Doyle, J. Carlson, S. Low, F. Paganini, G. Vinnicombe, W. Willinger, J. Hickey, P. Parrilo, and L. Vandenberghe. Robustness and the internet: Theoretical foundations. http://netlab.caltech.edu/internet/, 2002.]]

[20]

A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically optimized tradeoffs: A new paradigm for powerlaws in the internet. ICALP 2002, 2002.]]

Digital Library

[21]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In Proc. SigComm. ACM, 1999.]]

Digital Library

[22]

N. L. for Applied Retwork Research. Route views archive. http://moat.nlanr.net/Routing/rawdata, 2002.]]

[23]

A. Frieze. Disjoint Paths in Expander Graphs via Random Walks: A Short Survey, volume 1518 of Lecture Notes in Computer Science. Springer Verlag, 1998.]]

Digital Library

[24]

L. Gao. On inferring autonomous system relationships in the internet. IEEE Glogal Internet, 2000.]]

[25]

C. Gkantsidis, M. Mihail, and E. Zegura. The markov chain simulation method for generating connected power law random graphs. In Proc. 5th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, January 2003.]]

[26]

C. Gkantsidis, M. Mihail, and E. Zegura. Spectral analysis of internet topologies. In Proc. Infocom. IEEE, 2003. To appear.]]

[27]

C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Technical Report CSE-TR-433-00, U. Michigan, Ann Arbor, 2000.]]

[28]

J. Kleinberg. Navigation in small world. Nature, 406, 2000.]]

[29]

J. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In Proc. 37th Symposium on Foundations of Computer Science (FOCS), pages 86--95. IEEE, 1996.]]

Digital Library

[30]

R. Kumar, P. Raghavan, S. Rajagopalan, S. D., A. Tomkins, and E. Upfal. Stochastic models for the web graphs. In Proc. 41st Symposium on Foundations of Computer Science (FOCS), pages 57--65. IEEE, 2000.]]

Digital Library

[31]

C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proc. Infocom. IEEE, 2003. To appear.]]

[32]

F. Leighton. Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.]]

[33]

F. Leighton and S. Rao. Circuit switching: Multicommodity flow based approach. In Workshop on Randomized Parallel Computing, 1996.]]

[34]

F. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46:787--832, 1999.]]

Digital Library

[35]

N. Linial, E. London, and Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.]]

[36]

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261--278, 1988.]]

[37]

A. Medina, I. Matta, and J. Byers. On the origin of power-laws in internet topologies. ACM Computer Communications Review, April 2000.]]

Digital Library

[38]

B. Metcalfe. Internet Collapses and Other InfoWorld Punditry. Hungry Minds, Inc., May 2000.]]

Digital Library

[39]

M. Mihail and C. Papadimitriou. Random 2002, 2002.]]

[40]

M. Mihail, C. Papadimitrious, and A. Saberi. On certain connectivity properties of internet graphs. submitted, 2003.]]

[41]

M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 6:161--180, 1995.]]

Digital Library

[42]

M. Molloy and B. Reed. The size of the largest component of a random graph on a fixed degree sequence. Combinatorics, Probability and Computing, 7:295--306, 1998.]]

Digital Library

[43]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.]]

Digital Library

[44]

M. Newman. Assortativity mixing in networks. Phys. Rev. Lett., 89, 2002.]]

[45]

V. Padmanabhan, L. Qiu, and H. Wang. Server-based inference of internet performance. In Proc. Infocom. IEEE, 2003. To appear.]]

[46]

C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.]]

[47]

N. Pippinger. Information theory and the complexity of switching networks. In Proc. 16th Symposium on Foundations of Computer Science (FOCS), pages 113--118, 1975.]]

Digital Library

[48]

N. Pippinger. Superconcentrators. SIAM Journal on Computing, 6(2):298--304, 1977.]]

[49]

N. Pippinger. On rearrangeable and non-blocking switching networks. Journal of Computer and System Sciences, 17(2):145--162, 1978.]]

[50]

J. S. Quarterman. Imminent death of the internet? Matrix News, 6(6), June 1996. Also, available at http://www2.aus.us.mids.org/mn/606/death.html.]]

[51]

Y. Rehkter and P. Gross. Application of the border gateway protocol in the internet. RFC 1655, IETF, July 1994.]]

[52]

A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Springer-Verlag, 1997.]]

Digital Library

[53]

L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proc. Infocom. IEEE, 2002.]]

[54]

H. Tagmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators: Degree-based vs structural. In Proc. SigComm. ACM, 2002.]]

Digital Library

[55]

H. Tagmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. Network topology generators: Degree-based vs structural. Technical Report 02-760, USC, 2002.]]

[56]

D. Towsley. Modeling the internet: Seeing the forest through the trees. Keynote Address, Sigmetrics, 2002.]]

[57]

V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.]]

Digital Library

[58]

W. Willinger and J. Doyle. Robustness and the internet: Design and evolution. http://netlab.caltech.edu/internet/, 2002.]]

[59]

H. Zhang, A. Goel, and R. Govindan. Using the small-world model to improve freenet performance. In Proc. Infocom. IEEE, 2002.]]

Digital Library

Cited By

Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Liu YZou LWei Z(2022)Building Graphs at Scale via Sequence of Edges: Model and Generation AlgorithmsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.308162434:12(5649-5663)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TKDE.2021.3081624
Aksoy SBruillard PYoung SRaugas M(2020)Ramanujan graphs and the spectral gap of supercomputing topologiesThe Journal of Supercomputing10.1007/s11227-020-03291-1Online publication date: 10-May-2020
https://doi.org/10.1007/s11227-020-03291-1
Show More Cited By

Index Terms

Conductance and congestion in power law graphs

Recommendations

Conductance and congestion in power law graphs
SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to ...
Comparing the Structure of Power-Law Graphs and the Internet AS Graph
ICNP '04: Proceedings of the 12th IEEE International Conference on Network Protocols

In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS Graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the ...
Intersection graphs of maximal hypercubes

In this paper we consider cube graphs, that is intersection graphs of maximal hypercubes of graphs. In contrast to the related concepts of line graphs and clique graphs, we show that any graph is a cube graph of a (bipartite) graph. We answer a question ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 31, Issue 1

June 2003

325 pages

ISSN:0163-5999

DOI:10.1145/885651

Issue’s Table of Contents

SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2003
338 pages
ISBN:1581136641
DOI:10.1145/781027
General Chairs:
Bill Cheng
TeleGIF
,
Satish Tripathi
University of California at Riverside
,
Program Chairs:
Jennifer Rexford
AT&T Labs -- Research, Florham Park, NJ
,
William H. Sanders
University of Illinois at Urbana-Champaign

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2003

Published in SIGMETRICS Volume 31, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,082
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Liu YZou LWei Z(2022)Building Graphs at Scale via Sequence of Edges: Model and Generation AlgorithmsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.308162434:12(5649-5663)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TKDE.2021.3081624
Aksoy SBruillard PYoung SRaugas M(2020)Ramanujan graphs and the spectral gap of supercomputing topologiesThe Journal of Supercomputing10.1007/s11227-020-03291-1Online publication date: 10-May-2020
https://doi.org/10.1007/s11227-020-03291-1
Molla APandurangan G(2018)Local Mixing Time: Distributed Computation and Applications2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2018.00084(743-752)Online publication date: May-2018
https://doi.org/10.1109/IPDPS.2018.00084
Huo RDurrett R(2018)Latent voter model on locally tree-like random graphsStochastic Processes and their Applications10.1016/j.spa.2017.08.004128:5(1590-1614)Online publication date: May-2018
https://doi.org/10.1016/j.spa.2017.08.004
Bianchi FMaiorino ELivi LRizzi ASadeghian A(2017)An agent-based algorithm exploiting multiple local dissimilarities for clusters mining and knowledge discoverySoft Computing - A Fusion of Foundations, Methodologies and Applications10.5555/3057124.305714721:5(1347-1369)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.5555/3057124.3057147
Molla APandurangan G(2017)Distributed Computation of Mixing TimeProceedings of the 18th International Conference on Distributed Computing and Networking10.1145/3007748.3007784(1-4)Online publication date: 5-Jan-2017
https://dl.acm.org/doi/10.1145/3007748.3007784
Ok JShin JYi Y(2017)Incentivizing strategic users for social diffusion: Quantity or quality?IEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8056958(1-9)Online publication date: May-2017
https://doi.org/10.1109/INFOCOM.2017.8056958
Sarma AMolla APandurangan GDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)Distributed Computation of Sparse Cuts via Random WalksProceedings of the 16th International Conference on Distributed Computing and Networking10.1145/2684464.2684474(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684474
Bianchi FMaiorino ELivi LRizzi ASadeghian A(2015)An agent-based algorithm exploiting multiple local dissimilarities for clusters mining and knowledge discoverySoft Computing10.1007/s00500-015-1876-121:5(1347-1369)Online publication date: 22-Sep-2015
https://doi.org/10.1007/s00500-015-1876-1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents