Conference proceeding
On Random Walks and Random Sampling to Find Max Degree Nodes in Assortative Erdos Renyi Graphs
2016 IEEE Global Communications Conference (GLOBECOM), pp 1-7
Dec 2016
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Social networks are naturally modeled as graphs, with edges indicating associations of users, and as such user popularity or influence is captured by the degree of the node corresponding to the user. It is of natural interest to seek maximum degree nodes, i.e., most popular members, in this graph, and as these networks are large, this requires an efficient search algorithm. In this paper we address the problem of finding a maximum degree node (as distinct from finding the maximum degree) in Erdos Renyi (ER) random graphs, where these graphs are ``rewired'' in a way to reach a target assortativity without affecting the marginal degree distribution. We address two questions: i) how many maximum degree nodes are in such a graph, on average, and ii) is it easier to find such a node via a biased random walk (BRW) or via random (star) sampling (RSS)? To answer the first question, we show that large ER graphs possess on average a unique maximum degree node. The answer to the second question is that the superiority of BRW vs. RSS depends critically on the assortativity. In particular, RSS is independent of, and BRW is highly sensitive to, the assortativity. We demonstrate numerically the sensitivity of BRW to assortativity is connected to the prevalence of local maxima; these maxima limit the ability of BRW to follow a gradient on the graph. Finally, we establish how the prevalence of local maxima may be computed from the joint degree distribution of the graph.
Metrics
Details
- Title
- On Random Walks and Random Sampling to Find Max Degree Nodes in Assortative Erdos Renyi Graphs
- Creators
- Jonathan Stokes - Drexel UniversitySteven Weber - Drexel University
- Publication Details
- 2016 IEEE Global Communications Conference (GLOBECOM), pp 1-7
- Conference
- 2016 IEEE Global Communications Conference (GLOBECOM)
- Publisher
- IEEE
- Number of pages
- 1
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000401963303074
- Scopus ID
- 2-s2.0-85015202060
- Other Identifier
- 991019167345604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Engineering, Electrical & Electronic
- Telecommunications