User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Local leaders in random networks

Primary tabs

Blondel, Vincent [UCL] Guillaume, Jean-Loup Hendrickx, Julien [UCL] de Kerchove D'Exaerde, Cristobald [UCL] Lambiotte, Renaud

We consider local leaders in random uncorrelated networks, i.e., nodes whose degree is higher than or equal to the degree of all their neighbors. An analytical expression is found for the probability for a node of degree k to be a local leader. This quantity is shown to exhibit a transition from a situation where high-degree nodes are local leaders to a situation where they are not, when the tail of the degree distribution behaves like the power law ~k(-gamma(c)) with gamma(c)=3 . Theoretical results are verified by computer simulations, and the importance of finite-size effects is discussed.

Document type Article de périodique (Journal article) – Article de recherche – Journal Article
Access type Accès restreint
Publication date 2008
Language Anglais
Journal information "Physical review. E, Statistical, nonlinear, and soft matter physics" - Vol. 77, no. 3 Pt 2, p. 036114 (2008)
Peer reviewed yes
issn 1539-3755
Publication status Publié
Affiliation UCL - FSA/INMA - Département d'ingénierie mathématique
Links
  1. Newman M. E. J., The Structure and Function of Complex Networks, 10.1137/s003614450342480
  2. A.-L. Barabási, Linked (2002)
  3. Barabási A., Emergence of Scaling in Random Networks, 10.1126/science.286.5439.509
  4. Boguñá Marián, Pastor-Satorras Romualdo, Vespignani Alessandro, Absence of Epidemic Threshold in Scale-Free Networks with Degree Correlations, 10.1103/physrevlett.90.028701
  5. Sood V., Redner S., Voter Model on Heterogeneous Graphs, 10.1103/physrevlett.94.178701
  6. Galam Serge, Application of statistical physics to politics, 10.1016/s0378-4371(99)00320-9
  7. Lambiotte R, How does degree heterogeneity affect an order-disorder transition?, 10.1209/0295-5075/78/68002
  8. Callaway Duncan S., Newman M. E. J., Strogatz Steven H., Watts Duncan J., Network Robustness and Fragility: Percolation on Random Graphs, 10.1103/physrevlett.85.5468
  9. Pastor-Satorras Romualdo, Vespignani Alessandro, Epidemic Spreading in Scale-Free Networks, 10.1103/physrevlett.86.3200
  10. May Robert M., Lloyd Alun L., Infection dynamics on scale-free networks, 10.1103/physreve.64.066112
  11. Moreira André Auto, Andrade José S., Nunes Amaral Luís A., Extremum Statistics in Scale-Free Network Models, 10.1103/physrevlett.89.268703
  12. Krapivsky P. L., Redner S., Statistics of Changes in Lead Node in Connectivity-Driven Networks, 10.1103/physrevlett.89.258703
  13. Łuczak Tomasz, Component behavior near the critical point of the random graph process, 10.1002/rsa.3240010305
  14. Erdös Paul, Łuczak Tomasz, Changes of leadership in a random graph process, 10.1002/rsa.3240050122
  15. GALAMBOS JANOS, THE ASYMPTOTIC THEORY OF EXTREME ORDER STATISTICS, The Theory and Applications of Reliability with Emphasis on Bayesian and Nonparametric Methods (1977) ISBN:9780127021010 p.151-164, 10.1016/b978-0-12-702101-0.50014-7
  16. C. de Kerchove, Positive Systems (2006)
  17. Newman M. E. J., Assortative Mixing in Networks, 10.1103/physrevlett.89.208701
  18. H. E. Stanley, Introduction to Phase Transitions and Critical Phenomena (1971)
  19. R. L. Graham, Concrete Mathematics: A Foundation for Computer Science (1989)
  20. Catanzaro Michele, Boguñá Marián, Pastor-Satorras Romualdo, Generation of uncorrelated random scale-free networks, 10.1103/physreve.71.027103
  21. Park Juyong, Newman M. E. J., Origin of degree correlations in the Internet and other networks, 10.1103/physreve.68.026112
  22. Maslov Sergei, Sneppen Kim, Zaliznyak Alexei, Detection of topological patterns in complex networks: correlation profile of the internet, 10.1016/j.physa.2003.06.002
  23. Moreno Y., Vázquez A., Disease spreading in structured scale-free networks, 10.1140/epjb/e2003-00031-9
  24. Krapivsky P. L., Redner S., Organization of growing random networks, 10.1103/physreve.63.066123
  25. Wai-Ho Au, Chan K.C.C., Xin Yao, A novel evolutionary data mining algorithm with applications to churn prediction, 10.1109/tevc.2003.819264
  26. Krapivsky P. L., Redner S., Network growth by copying, 10.1103/physreve.71.036118
  27. Lambiotte R, Ausloos M, Growing network with j-redirection, 10.1209/0295-5075/77/58002
  28. Newman M. E. J., The Structure and Function of Complex Networks, 10.1137/s003614450342480
Bibliographic reference Blondel, Vincent ; Guillaume, Jean-Loup ; Hendrickx, Julien ; de Kerchove D'Exaerde, Cristobald ; Lambiotte, Renaud. Local leaders in random networks. In: Physical review. E, Statistical, nonlinear, and soft matter physics, Vol. 77, no. 3 Pt 2, p. 036114 (2008)
Permanent URL http://hdl.handle.net/2078.1/12645