Paper Info
Title
Distribution and Dependence of Extremes in Network Sampling Processes
Abstract
We explore the dependence structure in the sampled sequence of complex networks. We consider randomized algorithms to sample the nodes and study external properties in any associated stationary sequence of characteristics of interest like node degrees, number of followers or income of the nodes in Online Social Networks etc, which satisfy two mixing conditions. Several useful extremes of the sampled sequence like kth largest value, clusters of exceedances over a threshold, first hitting time of a large value etc are investigated. We abstract the dependence and the statistics of extremes into a single parameter that appears in Extreme Value Theory, called external index (EI). In this work, we derive this parameter analytically and also estimate it empirically. We propose the use of EI as a parameter to compare different sampling procedures. As a specific example, degree correlations between neighboring nodes are studied in detail with three prominent random walks as sampling techniques.
Year
DOI
Venue
2014
10.1109/SITIS.2014.91
Signal-Image Technology and Internet-Based Systems
Keywords
Field
DocType
complex networks,randomised algorithms,sampling methods,social networking (online),complex network sampled sequence,external index,extreme value theory,extremes dependence,extremes distribution,network sampling processes,online social networks,randomized algorithms,sampling techniques,stationary sequence,network sampling,extremal index,random walks on graph
Markov process,Random walk,Artificial intelligence,Complex network,Hitting time,Statistical physics,Randomized algorithm,Pattern recognition,Extreme value theory,Sampling (statistics),Stationary sequence,Statistics,Mathematics
Conference
Volume
Issue
ISSN
2
1
2197-4314
Citations 
PageRank 
References 
2
0.38
10
Authors
3
Name
Order
Citations
PageRank
Konstantin Avrachenkov11250126.17
Natalia M. Markovich2347.06
Jithin Kazuthuveettil Sreedharan3103.39