On the Connectivity and Giant Component Size of Random K-out Graphs Under Randomly Deleted Nodes.
作者： Osman Yagan , Mansi Sood , Eray Can Elumar
DOI:
关键词:
摘要: Random K-out graphs, denoted $\mathbb{H}(n;K)$, are generated by each of the $n$ nodes drawing $K$ out-edges towards distinct selected uniformly at random, and then ignoring orientation arcs. Recently, random graphs have been used in applications as diverse (pairwise) key predistribution ad-hoc networks, anonymous message routing crypto-currency differentially-private federated averaging. In many applications, connectivity graph when some its dishonest, failed, or captured is practical interest. We provide a comprehensive set results on giant component size $\mathbb{H}(n;K_n,\gamma_n)$, i.e., $\gamma_n$ nodes, deleted. First, we derive conditions for $K_n$ that ensure, with high probability (whp), remaining number deleted $\gamma_n=\Omega(n)$ $\gamma_n=o(n)$, respectively. Next, $\mathbb{H}(n;K_n,\gamma_n)$ to component, connected subgraph $\Omega(n)$ whp. This also done different scalings upper bounds provided outside component. Simulation presented validate usefulness finite node regime.
arxiv.org参考文章(18)
Faruk Yavuz, Jun Zhao, Osman Yagan, Virgil Gligor, Designing secure and reliable wireless sensor networks under a pairwise key predistribution scheme 2015 IEEE International Conference on Communications (ICC). pp. 6277- 6283 ,(2015) , 10.1109/ICC.2015.7249324
Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Unassailable sensor networks Proceedings of the 4th international conference on Security and privacy in communication netowrks - SecureComm '08. pp. 26- ,(2008) , 10.1145/1460877.1460911
Anna Goldenberg, A Survey of Statistical Network Models Foundations and Trends® in Machine Learning archive. ,vol. 2, pp. 129- 233 ,(2010) , 10.1561/2200000005
Osman Yagan, Armand M. Makowski, On the Connectivity of Sensor Networks Under Random Pairwise Key Predistribution IEEE Transactions on Information Theory. ,vol. 59, pp. 5754- 5762 ,(2013) , 10.1109/TIT.2013.2265694
M. E. J. Newman, D. J. Watts, S. H. Strogatz, Random graph models of social networks Proceedings of the National Academy of Sciences of the United States of America. ,vol. 99, pp. 2566- 2572 ,(2002) , 10.1073/PNAS.012582999
Haowen Chan, A. Perrig, D. Song, Random key predistribution schemes for sensor networks ieee symposium on security and privacy. pp. 197- 213 ,(2003) , 10.1109/SECPRI.2003.1199337
Osman Yagan, Armand M. Makowski, Modeling the Pairwise Key Predistribution Scheme in the Presence of Unreliable Links IEEE Transactions on Information Theory. ,vol. 59, pp. 1740- 1760 ,(2013) , 10.1109/TIT.2012.2219578
Osman Yağan, Armand M. Makowski, On the scalability of the random pairwise key predistribution scheme: Gradual deployment and key ring sizes Performance Evaluation. ,vol. 70, pp. 493- 512 ,(2013) , 10.1016/J.PEVA.2013.03.001
Sham M Kakade, Robin Pemantle, Siddharth Suri, Michael Kearns, Luis E Ortiz, Economic Properties of Social Networks neural information processing systems. ,vol. 17, pp. 633- 640 ,(2004)
Osman Yagan, Armand M. Makowski, Wireless Sensor Networks Under the Random Pairwise Key Predistribution Scheme: Can Resiliency Be Achieved With Small Key Rings? IEEE ACM Transactions on Networking. ,vol. 24, pp. 3383- 3396 ,(2016) , 10.1109/TNET.2016.2527742