Random intersection graphs and their applications in security, wireless communication, and social networks
Random intersection graphs and their applications in security, wireless communication, and social networks
复制标题
随机交叉图及其在安全、无线通信和社交网络中的应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
V. Gligor
中科院分区：
文献类型：
--
作者：
Jun Zhao;Osman Yağan;V. Gligor
随机交图受到了人们的广泛关注，并在许多领域得到了广泛应用。在随机密钥预分配方案下对安全传感器网络进行建模时，以及在对包括共同兴趣网络、协作网络和参与者网络在内的社交网络的拓扑进行建模时，它们自然会被诱导。简单地说，随机交叉图是通过以某种随机方式为每个节点分配一组项目，然后在共享一定数量项目的任意两个节点之间放置一条边来构建的。
广义地说，我们的工作是分析随机交图，以及由它与其他随机图模型组成的模型，这些模型包括随机几何图和ERDHo S-REnyi图。这些组成模型的引入是为了比文献中现有的模型更准确地捕捉各种复杂的自然或人造网络的特征。对于随机交图及其与其他随机图的合成，我们研究了($k$-)连通性、($k$-)稳健性、完全匹配的包含和哈密尔顿圈等性质。我们的结果通常以渐近精确概率或指定临界标度的零一定律的形式给出，并为各种真实世界网络的设计和分析提供了关键的见解。
Random intersection graphs have received much interest and been used in diverse applications. They are naturally induced in modeling secure sensor networks under random key predistribution schemes, as well as in modeling the topologies of social networks including common-interest networks, collaboration networks, and actor networks. Simply put, a random intersection graph is constructed by assigning each node a set of items in some random manner and then putting an edge between any two nodes that share a certain number of items.
Broadly speaking, our work is about analyzing random intersection graphs, and models generated by composing it with other random graph models including random geometric graphs and Erd\H{o}s-R\'enyi graphs. These compositional models are introduced to capture the characteristics of various complex natural or man-made networks more accurately than the existing models in the literature. For random intersection graphs and their compositions with other random graphs, we study properties such as ($k$-)connectivity, ($k$-)robustness, and containment of perfect matchings and Hamilton cycles. Our results are typically given in the form of asymptotically exact probabilities or zero-one laws specifying critical scalings, and provide key insights into the design and analysis of various real-world networks.
DOI：
10.1016/j.disc.2009.03.042
发表时间：
2008-05
期刊：
Discret. Math.
影响因子：
--
作者：
S. Blackburn;S. Gerke
通讯作者：
S. Blackburn;S. Gerke