2008/09/04 by N. Prasanth Anthapadmanabhan, Anthapadmanabhan, N. Prasanth, Armand M. Makowski +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.0809.0918
openalex publication_date 2008/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When studying networks using random graph models, one is sometimes faced with situations where the notion of adjacency between nodes reflects multiple constraints. Traditional random graph models are insufficient to handle such situations. A simple idea to account for multiple constraints consists in taking the intersection of random graphs. In this paper we initiate the study of random graphs so obtained through a simple example. We examine the intersection of an Erdos-Renyi graph and of one-dimensional geometric random graphs. We investigate the zero-one laws for the property that there are no isolated nodes. When the geometric component is defined on the unit circle, a full zero-one law is established and we determine its critical scaling. When the geometric component lies in the unit interval, there is a gap in that the obtained zero and one laws are found to express deviations from different critical scalings. In particular, the first moment method requires a larger critical scaling than in the unit circle case in order to obtain the one law. This discrepancy is somewhat surprising given that the zero-one laws for the absence of isolated nodes are identical in the geometric random graphs on both the unit interval and unit circle.