 |
Center for Nonlinear Studies |
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: Garrett Kenyon, gkenyon@lanl.gov, 7-1900, IS & T