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 a _t_-vertex graph, with degree sequence power law _c_ ≥ 3 generated by a generalized preferential attachment process that adds _m_ edges at each step. Let _S__a be the set of all vertices of degree at least _t_^a 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)/(2_c_ − 3), the random walk discovers the set _S__a completely in

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

. 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.

A Fast Algorithm to Find All High-Degree Vertices in Graphs with a Power-Law Degree Sequence

This website uses cookies