A framework for evaluating statistical dependencies and rank correlations in power law graphs

Y. Volkovich, Nelli Litvak, B. Zwart

Research output: Book/ReportReportProfessional

30 Downloads (Pure)

Abstract

We analyze dependencies in power law graph data (Web sample, Wikipedia sample and a preferential attachment graph) using statistical inference for multivariate regular variation. To the best of our knowledge, this is the first attempt to apply the well developed theory of regular variation to graph data. The new insights this yields are striking: the three above-mentioned data sets are shown to have a totally different dependence structure between different graph parameters, such as in-degree and PageRank. Based on the proposed methodology, we suggest a new measure for rank correlations. Unlike most known methods, this measure is especially sensitive to rank permutations for topranked nodes. Using this method, we demonstrate that the PageRank ranking is not sensitive to moderate changes in the damping factor.
Original languageUndefined
Place of PublicationEnschede
PublisherStochastic Operations Research (SOR)
Number of pages9
Publication statusPublished - Jun 2008

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.274/1868
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • CR-E.1
  • Web
  • IR-64783
  • Regular variation
  • Preferential attachment
  • METIS-250993
  • EWI-12798
  • PageRank
  • CR-G.3
  • Wikipedia

Cite this

Volkovich, Y., Litvak, N., & Zwart, B. (2008). A framework for evaluating statistical dependencies and rank correlations in power law graphs. Enschede: Stochastic Operations Research (SOR).
Volkovich, Y. ; Litvak, Nelli ; Zwart, B. / A framework for evaluating statistical dependencies and rank correlations in power law graphs. Enschede : Stochastic Operations Research (SOR), 2008. 9 p.
@book{cfd69b702e4e4b5e99982a820ef6f466,
title = "A framework for evaluating statistical dependencies and rank correlations in power law graphs",
abstract = "We analyze dependencies in power law graph data (Web sample, Wikipedia sample and a preferential attachment graph) using statistical inference for multivariate regular variation. To the best of our knowledge, this is the first attempt to apply the well developed theory of regular variation to graph data. The new insights this yields are striking: the three above-mentioned data sets are shown to have a totally different dependence structure between different graph parameters, such as in-degree and PageRank. Based on the proposed methodology, we suggest a new measure for rank correlations. Unlike most known methods, this measure is especially sensitive to rank permutations for topranked nodes. Using this method, we demonstrate that the PageRank ranking is not sensitive to moderate changes in the damping factor.",
keywords = "CR-E.1, Web, IR-64783, Regular variation, Preferential attachment, METIS-250993, EWI-12798, PageRank, CR-G.3, Wikipedia",
author = "Y. Volkovich and Nelli Litvak and B. Zwart",
year = "2008",
month = "6",
language = "Undefined",
publisher = "Stochastic Operations Research (SOR)",
number = "274/1868",

}

Volkovich, Y, Litvak, N & Zwart, B 2008, A framework for evaluating statistical dependencies and rank correlations in power law graphs. Stochastic Operations Research (SOR), Enschede.

A framework for evaluating statistical dependencies and rank correlations in power law graphs. / Volkovich, Y.; Litvak, Nelli; Zwart, B.

Enschede : Stochastic Operations Research (SOR), 2008. 9 p.

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - A framework for evaluating statistical dependencies and rank correlations in power law graphs

AU - Volkovich, Y.

AU - Litvak, Nelli

AU - Zwart, B.

PY - 2008/6

Y1 - 2008/6

N2 - We analyze dependencies in power law graph data (Web sample, Wikipedia sample and a preferential attachment graph) using statistical inference for multivariate regular variation. To the best of our knowledge, this is the first attempt to apply the well developed theory of regular variation to graph data. The new insights this yields are striking: the three above-mentioned data sets are shown to have a totally different dependence structure between different graph parameters, such as in-degree and PageRank. Based on the proposed methodology, we suggest a new measure for rank correlations. Unlike most known methods, this measure is especially sensitive to rank permutations for topranked nodes. Using this method, we demonstrate that the PageRank ranking is not sensitive to moderate changes in the damping factor.

AB - We analyze dependencies in power law graph data (Web sample, Wikipedia sample and a preferential attachment graph) using statistical inference for multivariate regular variation. To the best of our knowledge, this is the first attempt to apply the well developed theory of regular variation to graph data. The new insights this yields are striking: the three above-mentioned data sets are shown to have a totally different dependence structure between different graph parameters, such as in-degree and PageRank. Based on the proposed methodology, we suggest a new measure for rank correlations. Unlike most known methods, this measure is especially sensitive to rank permutations for topranked nodes. Using this method, we demonstrate that the PageRank ranking is not sensitive to moderate changes in the damping factor.

KW - CR-E.1

KW - Web

KW - IR-64783

KW - Regular variation

KW - Preferential attachment

KW - METIS-250993

KW - EWI-12798

KW - PageRank

KW - CR-G.3

KW - Wikipedia

M3 - Report

BT - A framework for evaluating statistical dependencies and rank correlations in power law graphs

PB - Stochastic Operations Research (SOR)

CY - Enschede

ER -

Volkovich Y, Litvak N, Zwart B. A framework for evaluating statistical dependencies and rank correlations in power law graphs. Enschede: Stochastic Operations Research (SOR), 2008. 9 p.