Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Diameter, connectivity, and phase transition of the uniform random intersection graph

Diameter, connectivity, and phase transition of the uniform random intersection graph,10.1016/j.disc.2011.05.029,Discrete Mathematics,Katarzyna Rybarc

Edit
Diameter, connectivity, and phase transition of the uniform random intersection graph   (Citations: 7)
BibTex | RIS | RefWorks Download
We study properties of the uniform random intersection graph model G(n,m,d). We find asymptotic estimates on the diameter of the largest connected component of the graph near the phase transition and connectivity thresholds. Moreover we manage to prove an asymptotically tight bound for the connectivity and phase transition thresholds for all possible ranges of d, which has not been obtained before. The main motivation of our research is the usage of the random intersection graph model in the studies of wireless sensor networks.
Journal: Discrete Mathematics - DM , vol. 311, no. 17, pp. 1998-2019, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...To date, most of the efforts along these lines have been carried out under the assumption of full visibility according to which sensor nodes are all within communication range of each other; more on this later: Under this assumption, the EG scheme gives rise to a class of random graphs known as random key graphs; relevant results can be found in the references [2, 7, 8, 12, 14]...

    Osman Yagan, et al. Designing Securely Connected Wireless Sensor Networks in the Presence ...

    • ...The modeling and performance of the EG scheme, as we refer to it hereafter, has been extensively investigated [1], [4], [6], [10], [12], with most of the focus being on the full visibility case where nodes are all within communication range of each other...
    • ...connected. It is worth pointing out that the simulation results in Section IV suggest the existence of a full zero-one law for �� �� (�� ; �� �� ) with a threshold resembling �� (�� ). This would not be surprising since in many known classes of random graphs, the absence of isolated nodes and graph connectivity are asymptotically equivalent properties, e.g., Erd˝ os-R´ enyi graphs [2], geometric random graphs [8] and random key graphs ...

    Osman Yagan, et al. On the gradual deployment of random pairwise key distribution schemes

    • ...This approach, which was initiated by Eschenauer and Gligor in their original analysis [4], has now been validated rigorously; see the papers [1, 2, 12, 14, 15] for recent developments...
    • ...Furthermore, Rybarczyk [12] has shown that this transfer from Erdý os-R´ enyi graphs also works when dealing with a number of issues related to the giant component and its diameter...
    • ...Random key graphs and Erdý os-R´ enyi graphs have been shown to behave similarly regarding graph connectivity when the models parameters are suitably scaled [1, 2, 12, 14, 15], To discuss this similarity, we refer to any mapping p : N0 → [0,1] as a scaling for Erdý os-R´ enyi graphs...
    • ...1 if 1 < c. Analogous results are available for random key graphs; see the recent papers [1, 2, 12, 15]...

    O. Yagan, et al. On the existence of triangles in random key graphs

    • ...This approach has served as a point of departure for conjecturing various zero-one laws for connectivity in random key graphs [1], [15]; see the papers [1], [4], [13], [16], [17] for recent developments...
    • ...Analogous results are available for random key graphs; see the recent papers [1], [4], [13], [17]...
    • ...Recently Rybarczyk [13] has shown under (27) that diam[K(n; θn)] ∼ log n loglog n...

    Osman Yagan, et al. Random Key Graphs

    • ...properties of uniform random intersection graphs are studied, see for example [1,2,8,23])...
    • ...Moreover in the proofs of Lemmas 2 and 3 instead of results on connectivity and the diameter stated in [3,4,7,10,11] we should use results from [23]...

    K. Krzywdziński, et al. Geometric Graphs with Randomly Deleted Edges - Connectivity and Routin...

Sort by:

Citations (7)

Share this on