Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T05:52:57.414Z Has data issue: false hasContentIssue false
  • English
  • Français

The degree-wise effect of a second step for a random walk on a graph

Part of: Graph theory Combinatorial probability Mathematical sociology Markov processes

Published online by Cambridge University Press:  16 January 2019

Kenneth S. Berenhaut ,
Hongyi Jiang ,
Katelyn M. McNab  and
Elizabeth J. Krizay
Kenneth S. Berenhaut*
Affiliation:
Wake Forest University
Hongyi Jiang*
Affiliation:
Johns Hopkins University
Katelyn M. McNab*
Affiliation:
Wake Forest University
Elizabeth J. Krizay*
Affiliation:
Georgia Institute of Technology
*
* Postal address: Department of Mathematics and Statistics, Wake Forest University, Winston-Salem, NC 27109, USA.
*** Postal address: Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218, USA.
* Postal address: Department of Mathematics and Statistics, Wake Forest University, Winston-Salem, NC 27109, USA.
**** Postal address: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider the degree-wise effect of a second step for a random walk on a graph. We prove that under the configuration model, for any fixed degree sequence the probability of exceeding a given degree threshold is smaller after two steps than after one. This builds on recent work of Kramer et al. (2016) regarding the friendship paradox under random walks.

Keywords

Friendship paradoxgraphrandom walkconfiguration model

MSC classification

Primary: 05C81: Random walks on graphs
Secondary: 05C07: Vertex degrees 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 60C05: Combinatorial probability 91D30: Social networks 05C80: Random graphs
Type
Research Papers
Information
Journal of Applied Probability , Volume 55 , Issue 4 , December 2018 , pp. 1203 - 1210
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. and Fill, J. (2014). Reversible Markov Chains and Random Walks on Graphs. University of California, Berkeley.Google Scholar
[2]Avena, L., Guldas, H., van der Hofstad, R. and den Hollander, F. (2018). Mixing times of random walks on dynamic configuration models. Ann. Appl. Prob. 28, 1977–2002.Google Scholar
[3]Bender, E. A. and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory A 24, 296–307.Google Scholar
[4]Ben-Hamou, A. and Salez, J. (2017). Cutoff for non\-backtracking random walks on sparse random graphs. Ann. Prob. 45, 1752–1770.Google Scholar
[5]Berenhaut, K. S. and Jiang, H. (2018). The friendship paradox for weighted and directed networks. To appear in Prob. Eng. Inf. Sci. Available at https://doi.org/10.1017/S0269964818000050.Google Scholar
[6]Berestycki, N., Lubetzky, E., Peres, Y. and Sly, A. (2018). Random walks on the random graph. Ann. Prob. 46, 456–490.Google Scholar
[7]Bordenave, C., Caputo, P. and Salez, J. (2018). Random walk on sparse random digraphs. Prob. Theory. Relat. Fields 170, 933–960.Google Scholar
[8]Brémaud, P. (2017). Random walks on graphs. In Discrete Probability Models and Methods. Springer, Cham, pp. 185–214.Google Scholar
[9]Cao, Y. and Ross, S. M. (2016). The friendship paradox. Math. Sci. 41, 61–64.Google Scholar
[10]Chen, N. and Olvera-Cravioto, M. (2013). Directed random graphs with given degree distributions. Stoch. Syst. 3, 147–165.10.1287/12-SSY076Google Scholar
[11]Christakis, N. A. and Fowler, J. H. (2010). Social network sensors for early detection of contagious outbreaks. PLoS ONE 5, e12948.Google Scholar
[12]Cohen, R., Havlin, S. and Ben-Avraham, D. (2003). Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91, 247901.Google Scholar
[13]Eom, Y.-H. and Jo, H.-H. (2014). Generalized friendship paradox in complex networks: the case of scientific collaboration. Sci. Rep.-UK 4, 4603.Google Scholar
[14]Eom, Y.-H. and Jo, H.-H. (2015). Tail-scope: using friends to estimate heavy tails of degree distributions in large-scale complex networks. Sci. Rep.-UK 5, 09752.10.1038/srep09752Google Scholar
[15]Feld, S. L. (1991). Why your friends have more friends than you do. Amer. J. Soc. 96, 1464–1477.Google Scholar
[16]Fotouhi, , B., Momeni, N.and Rabbat, M. G. (2014). Generalized friendship paradox: an analytical approach. In International Conference on Social Informatics. Springer, Cham, pp. 339–352.Google Scholar
[17]Garcia-Herranz, M.et al. (2014). Using friends as sensors to detect global-scale contagious outbreaks. PLoS ONE 9, e92413.Google Scholar
[18]Herrera, J. L.et al. (2016). Disease surveillance on complex social networks. PLoS Comput. Biol. 12, e1004928.Google Scholar
[19]Hodas, N. O., Kooti, F.and Lerman, K. (2013). Friendship paradox redux: your friends are more interesting than you. In Proc. 7th Int. Conf. on Weblogs and Social Media, ICWSM.Google Scholar
[20]Jackson, M. O. (2016). The friendship paradox and systematic biases in perceptions and social norms. Preprint. Available at http://dx.doi.org/10.2139/ssrn.278003.Google Scholar
[21]Jo, H.-H and Eom, Y.-H (2014). Generalized friendship paradox in networks with tunable degree-attribute correlation. Phys. Rev. E 90, 022809.Google Scholar
[22]Kim, D. A.et al. (2015). Social network targeting to maximise population behaviour change: a cluster randomised controlled trial. Lancet 386, 145–153.Google Scholar
[23]Kooti, F., Hodas, N. O.and Lerman, K. (2014). Network weirdness: exploring the origins of network paradoxes. In Proc. 8th Int. AAAI Conf. Weblogs and Social Media. AAAI Press, Palo Alto, CA, pp. 266–274.Google Scholar
[24]Kramer, J. B., Cutler, J. and Radcliffe, A. (2016). The multistep friendship paradox. Amer. Math. Monthly 123, 900–908.Google Scholar
[25]Lerman, K., Yan, X. and Wu, X.-Z. (2016). The “majority illusion” in social networks. PLoS ONE 11, e0147617.Google Scholar
[26]Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times, American Mathematical Society, Providence, RI.Google Scholar
[27]Lovász, L. (1993). Random Walks on Graphs: A Survey. In Combinatorics, Paul Erdős is Eighty (Bolyai Soc. Math. Studies 2), János Bolyai Math. Soc., Budapest, pp. 1–46.Google Scholar
[28]Lubetzky, E. and Sly, A. (2010). Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153, 475–510.10.1215/00127094-2010-029Google Scholar
[29]Milo, R.et al. (2003). On the uniform generation of random graphs with prescribed degree sequences. Preprint. Available at https://arxiv.org/abs/cond-mat/0312028.Google Scholar
[30]Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6, 161–180.Google Scholar
[31]Molloy, M. and Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Comb. Prob. Comput. 7, 295–305.Google Scholar
[32]Momeni, N. and Rabbat, M. (2016). Qualities and inequalities in online social networks through the lens of the generalized friendship paradox. PLoS ONE 11, e0143633.Google Scholar
[33]Momeni, N. and Rabbat, M. G. (2015). Measuring the generalized friendship paradox in networks with quality-dependent connectivity. In Complex Networks VI. Springer, Berlin, pp. 45–55.Google Scholar
[34]Singer, Y. (2016). Influence maximization through adaptive seeding. ACM SIGecom Exchanges 15, 32–59.Google Scholar
[35]Van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol 1. Cambridge University Press.Google Scholar
[36]Wu, X.-Z., Percus, A. G. and Lerman, K. (2016). Neighbor-neighbor correlations explain measurement bias in networks. Sci. Rep.-UK 7, 5576.10.1038/s41598-017-06042-0Google Scholar