Local leaders in random networks

被引:40
作者
Blondel, Vincent D. [1 ]
Guillaume, Jean-Loup [2 ]
Hendrickx, Julien M. [1 ]
de Kerchove, Cristobald [1 ]
Lambiotte, Renaud [1 ,3 ]
机构
[1] Catholic Univ Louvain, Dept Engn Math, B-1348 Louvain, Belgium
[2] Univ Paris 06, CNRS, UMR 7606, LIP6, F-75005 Paris, France
[3] Univ Liege, GRAPES, B-4000 Liege, Belgium
来源
PHYSICAL REVIEW E | 2008年 / 77卷 / 03期
关键词
All Open Access; Green;
D O I
10.1103/PhysRevE.77.036114
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
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 similar to k(-gamma c) with gamma(c) = 3. Theoretical results are verified by computer simulations, and the importance of finite-size effects is discussed.
引用
收藏
页数:5
相关论文
共 29 条
[1]  
[Anonymous], 1990, Random Struct. Algorithms, DOI [DOI 10.1002/RSA.3240010305, 10.1002/rsa.3240010305]
[2]   A novel evolutionary data mining algorithm with applications to churn prediction [J].
Au, WH ;
Chan, KCC ;
Yao, X .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2003, 7 (06) :532-545
[3]  
Barabasi A.-L., 2002, LINKED
[4]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[5]  
Blondel V, 2006, LECT NOTES CONTR INF, V341, P231
[6]   Absence of epidemic threshold in scale-free networks with degree correlations -: art. no. 028701 [J].
Boguñá, M ;
Pastor-Satorras, R ;
Vespignani, A .
PHYSICAL REVIEW LETTERS, 2003, 90 (02) :4-028701
[7]   Network robustness and fragility: Percolation on random graphs [J].
Callaway, DS ;
Newman, MEJ ;
Strogatz, SH ;
Watts, DJ .
PHYSICAL REVIEW LETTERS, 2000, 85 (25) :5468-5471
[8]   Generation of uncorrelated random scale-free networks -: art. no. 027103 [J].
Catanzaro, M ;
Boguñá, M ;
Pastor-Satorras, R .
PHYSICAL REVIEW E, 2005, 71 (02)
[9]   CHANGES OF LEADERSHIP IN A RANDOM GRAPH PROCESS [J].
ERDOS, P ;
LUCZAK, T .
RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (01) :243-252
[10]   Application of statistical physics to politics [J].
Galam, S .
PHYSICA A, 1999, 274 (1-2) :132-139