Estimating degree rank in complex networks
Loading...
Authors
Saxena, Akrati
Gera, Ralucca
Iyengar, S.R.S.
Subjects
Advisors
Date of Issue
2018
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Identifying top-ranked nodes can be performed using different centrality measures, based on their characteristics and influ- ential power. The most basic of all the ranking techniques is based on nodes degree. While finding the degree of a node requires local information, ranking the node based on its degree requires global information, namely the degrees of all the nodes of the network. It is infeasible to collect the global information for some graphs such as (i) the ones emerging from big data, (ii) dynamic networks, and (iii) distributed networks in which the whole graph is not known. In this work, we propose methods to estimate the degree rank of a node, that are faster than the classical method of computing the centrality value of all nodes and then rank a node. The proposed methods are modeled based on the network characteristics and sampling techniques, thus not requiring the entire network. We show that approximately 1% node samples are adequate to find the rank of a node with high accuracy.
Type
Article
Description
The article of record as published may be found at https://doi.org/10.1007/s13278-018-0520-3
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
20 p.
Citation
Saxena, Akrati, Ralucca Gera, and S. R. S. Iyengar. "Estimating degree rank in complex networks." Social Network Analysis and Mining 8.1 (2018): 42.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.