2017/06/05 by Akrati Saxena, Saxena, Akrati, Ralucca Gera +3 · 6 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Algorithm #Artificial intelligence #Complex Network Analysis Techniques #Complex network #Computer science #Data mining #Degree (music) #Degree distribution #FOS: Computer and information sciences #Mathematics #Node (physics) #Opinion Dynamics and Social Influence #Rank (graph theory) #Ranking (information retrieval) #Sampling (signal processing) #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.1706.01205
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2017/06/05 · arxiv created 2017/06/10 · arxiv updated 2017/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Most real world dynamic networks are evolved very fast with time. It is not feasible to collect the entire network at any given time to study its characteristics. This creates the need to propose local algorithms to study various properties of the network. In the present work, we estimate degree rank of a node without having the entire network. The proposed methods are based on the power law degree distribution characteristic or sampling techniques. The proposed methods are simulated on synthetic networks, as well as on real world social networks. The efficiency of the proposed methods is evaluated using absolute and weighted error functions. Results show that the degree rank of a node can be estimated with high accuracy using only 1% samples of the network size. The accuracy of the estimation decreases from high ranked to low ranked nodes. We further extend the proposed methods for random networks and validate their efficiency on synthetic random networks, that are generated using Erdős-Rényi model. Results show that the proposed methods can be efficiently used for random networks as well.