Lab Home  Phone  Search  


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: Scalefree 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 subclass 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 zeroone laws and for the corresponding critical scalings. These results are byproducts of wellknown 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 powerlaw 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 postdoc with CyLab at CMU). Host: Garrett Kenyon, gkenyon@lanl.gov, 71900, IS & T 