# King's College London

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

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Original language English Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 165-178 14 7323 LNCS https://doi.org/10.1007/978-3-642-30541-2_13 2012 Link to publication in Scopus 9th Workshop on Algorithms and Models for the Web Graph, WAW 2012 - Halifax, NS, CanadaDuration: 22 Jun 2012 → 23 Jun 2012

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7323 LNCS 03029743 16113349

### Conference

Conference 9th Workshop on Algorithms and Models for the Web Graph, WAW 2012 Canada Halifax, NS 22/06/2012 → 23/06/2012

## Abstract

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 biassed 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 which 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 biassed random walk which makes transitions along undirected edges {x,y} proportional to (d(x)d(y)) b, where d(x) is the degree of vertex x and b>0 is a constant parameter. Choosing the parameter b=(c-1)(c-2)/(2c-3), the random walk discovers the set S a completely in Õ(t 1-2ab(1-ε)) steps with high probability. The error parameter ε depends on c,a and m. We use the notation Õ(x) to mean O(x log k x) for some constant k>0. The cover time of the entire graph G(t) by the biassed walk is Õ(t). Thus the expected time to discover all vertices by the biassed walk is not much higher than in the case of a simple random walk Θ(t logt). The standard preferential attachment process generates graphs with power law c=3. Choosing 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 www with power law c ∼3 which support the claimed property.

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454