Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Student Program 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Wednesday, February 29, 2012
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)


On the critical transmission range in one-dimensional random networks under non-uniform node placement

Armand Makowski
University of Maryland

Following the work of Barabasi and Albert, the scale free nature of complex networks is often explained by growth models with a preferential attachment mechanism. Although in some context preferential attachment is a reasonable assumption, it is predicated on he information about the degree of each vertex being available to newly added nodes, either explicitly or implicitly. There are many situations where this assumption is questionable and where instead the creation of a link between two nodes results in a mutual benefit based on their intrinsic attributes, e.g., authority, friendship, social success, strength of interaction, etc. Hidden variable models incorporate this viewpoint in the establishment of links. Interest in them has been spurred in part by the following recent finding: Scale-free networks can arise in the context of hiddden variable models without having to invoke a preferential attachment mechanism. With this in mind, we consider a sub-class of hidden variable models, known as random threshold graphs. Their scaling properties for graph connectivity and the absence of isolated nodes are explored in the many node regime. We provide a complete characterization for the underlying zero-one laws and for the corresponding critical scalings. These results are by-products of well-known facts in Extreme Value Theory concerning the asymptotic behavior of running maxima on i.i.d. rvs. In one important special case we are able to show that the scalings ensuring a power-law degree distribution will not result in graph connectivity in the a.a.s sense. This is joint work with former Ph.D. student Osman Yagan (now a post-doc with CyLab at CMU).

Host: Misha Chertkov,, 665-8119