A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence

TY - JOUR

T1 - A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence

AU - Cooper, Colin

AU - Radzik, Tomasz

AU - Siantos, Yiannis

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We develop a fast method for finding all high-degree vertices of a connected graph with a power-law degree sequence. The method uses a biased random walk, where the bias is a function of the power law c of the degree sequence. Let G(t) be ta-vertex graph, with degree sequence power law c ≥ 3 generated by a generalized preferential attachment process that adds m edges at each step. Let Sa be the set of all vertices of degree at least ta in G(t). We analyze a biased random walk that makes transitions along undirected edges {x, y} with probabilities proportional to (d(x)d(y))b, where d(x) is the degree of vertex x and b > 0 is a constant parameter.With parameter b = (c − 1)(c − 2)/(2c − 3), the random walk discovers the set Sa completely in Õ(t1 − 2ab(1 −ϵ)) steps with high probability. The error parameter ϵ depends on c, a, and m. The cover time of the entire graph G(t) by the biased walk is Õ (t). Thus the expected time to discover all vertices by the biased walk is not much higher than the Θ(t log t) cover time of a simple random walk. The standard preferential attachment process generates graphs with power law c = 3. The search parameter b = 2/3 is appropriate for such graphs. We conduct experimental tests on a preferential attachment graph and on a sample of the underlying graph of the World Wide Web with power law c ≈ 3 that support the claimed property.

AB - We develop a fast method for finding all high-degree vertices of a connected graph with a power-law degree sequence. The method uses a biased random walk, where the bias is a function of the power law c of the degree sequence. Let G(t) be ta-vertex graph, with degree sequence power law c ≥ 3 generated by a generalized preferential attachment process that adds m edges at each step. Let Sa be the set of all vertices of degree at least ta in G(t). We analyze a biased random walk that makes transitions along undirected edges {x, y} with probabilities proportional to (d(x)d(y))b, where d(x) is the degree of vertex x and b > 0 is a constant parameter.With parameter b = (c − 1)(c − 2)/(2c − 3), the random walk discovers the set Sa completely in Õ(t1 − 2ab(1 −ϵ)) steps with high probability. The error parameter ϵ depends on c, a, and m. The cover time of the entire graph G(t) by the biased walk is Õ (t). Thus the expected time to discover all vertices by the biased walk is not much higher than the Θ(t log t) cover time of a simple random walk. The standard preferential attachment process generates graphs with power law c = 3. The search parameter b = 2/3 is appropriate for such graphs. We conduct experimental tests on a preferential attachment graph and on a sample of the underlying graph of the World Wide Web with power law c ≈ 3 that support the claimed property.

UR - https://www.scopus.com/pages/publications/84908159045

U2 - 10.1080/15427951.2013.819210

DO - 10.1080/15427951.2013.819210

M3 - Article

AN - SCOPUS:84908159045

SN - 1542-7951

VL - 10

SP - 137

EP - 161

JO - Internet Mathematics 1

JF - Internet Mathematics 1

IS - 1-2

ER -