On certain connectivity properties of the internet topology

摘要

We show that random graphs in the preferential connectivity model have constant conductance, and hence have worst-case routing congestion that scales logarithmically with the number of nodes. Another immediate implication is constant spectral gap between the first and second eigenvalues of the random walk matrix associated with these graphs. We also show that the expected frugality (overpayment in the Vickrey–Clarke–Groves mechanism for shortest paths) of a sparse Erdős–Renyi random graph is bounded by a small constant.