### Abstract

Original language | English |
---|---|

Pages (from-to) | 1-19 |

Number of pages | 19 |

Journal | Internet mathematics |

Volume | 10 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 5 May 2014 |

### Fingerprint

### Keywords

- Random walk
- Detection of nodes with the largest degrees
- METIS-306037
- Stopping criteria
- EWI-25090
- Top $k$ list
- Complex networks
- IR-91970

### Cite this

*Internet mathematics*,

*10*(1-2), 1-19. https://doi.org/10.1080/15427951.2013.798601

}

*Internet mathematics*, vol. 10, no. 1-2, pp. 1-19. https://doi.org/10.1080/15427951.2013.798601

**Quick detection of nodes with large degrees.** / Avrachenkov, Konstatin; Litvak, Nelly; Sokol, Marina; Towsley, Don.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Quick detection of nodes with large degrees

AU - Avrachenkov, Konstatin

AU - Litvak, Nelly

AU - Sokol, Marina

AU - Towsley, Don

N1 - eemcs-eprint-25090

PY - 2014/5/5

Y1 - 2014/5/5

N2 - Our goal is to find top-$k$ lists of nodes with the largest degrees in large complex networks quickly. If the adjacency list of the network is known (not often the case in complex networks), a deterministic algorithm to find the top-$k$ list of nodes with the largest degrees requires an average complexity of $\mathcal{O}(n)$ , where $n$ is the number of nodes in the network. Even this modest complexity can be very high for large complex networks. We propose to use a random-walk-based method. We show theoretically and by numerical experiments that for large networks, the random-walk method finds good-quality top lists of nodes with high probability and with computational savings of orders of magnitude. We also propose stopping criteria for the random-walk method that requires very little knowledge about the structure of the network.

AB - Our goal is to find top-$k$ lists of nodes with the largest degrees in large complex networks quickly. If the adjacency list of the network is known (not often the case in complex networks), a deterministic algorithm to find the top-$k$ list of nodes with the largest degrees requires an average complexity of $\mathcal{O}(n)$ , where $n$ is the number of nodes in the network. Even this modest complexity can be very high for large complex networks. We propose to use a random-walk-based method. We show theoretically and by numerical experiments that for large networks, the random-walk method finds good-quality top lists of nodes with high probability and with computational savings of orders of magnitude. We also propose stopping criteria for the random-walk method that requires very little knowledge about the structure of the network.

KW - Random walk

KW - Detection of nodes with the largest degrees

KW - METIS-306037

KW - Stopping criteria

KW - EWI-25090

KW - Top $k$ list

KW - Complex networks

KW - IR-91970

U2 - 10.1080/15427951.2013.798601

DO - 10.1080/15427951.2013.798601

M3 - Article

VL - 10

SP - 1

EP - 19

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 1-2

ER -