On Connectivity and Robustness in Random Intersection Graphs

DOI10.1109/TAC.2016.2601564MaRDI QIDQ5280399zbMATH OpenFDO

Authors Jun Zhao, Osman Yaǧan, Virgil Gligor

Publication date 27 July 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.01822

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Random intersection graphs have received much attention recently and been used in a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. For these graphs, each node is equipped with a set of objects in a random manner, and two nodes have an undirected edge in between if they have at least one object in common. In this paper, we investigate connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for k-connectivity and k-robustness, as well as the asymptotically exact probability of k-connectivity, for any positive integer k. The k-connectivity property quantifies how resilient is the connectivity of a graph against node or edge failures, while k-robustness measures the effectiveness of local-information-based consensus algorithms (that do not use global graph topology information) in the presence of adversarial nodes. In addition to presenting the results under the general random intersection graph model, we consider two special cases of the general model, a binomial random intersection graph and a uniform random intersection graph, which both have numerous applications as well. For these two specialized graphs, our results on asymptotically exact probabilities of k-connectivity and asymptotic zero-one laws for k-robustness are also novel in the literature.

Recommendations

• On Connectivity in a General Random Intersection Graph
• On the isolated vertices and connectivity in random intersection graphs
• On connectivity and robustness of random graphs with inhomogeneity
• On the connectivity of a random interval graph
• Connectivity of the uniform random intersection graph
• scientific article; zbMATH DE number 1759469
• On the robustness of interconnections in random graphs: a symbolic approach.
• On the connectedness of a random graph
• Publication:4729111
• On the strength of connectedness of a random graph

Cited in

(7)

• Asymptotic connectedness of random interval graphs in a one dimensional data delivery problem
• Percolation theories for multipartite networked systems under random failures
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Determining \(r\)- and \((r,s)\)-robustness of digraphs using mixed integer linear programming
• Isoperimetric numbers of randomly perturbed intersection graphs
• The coupling method for inhomogeneous random intersection graphs.
• Characterization of expansion-related properties of modular graphs

This page was built for publication: On Connectivity and Robustness in Random Intersection Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280399)