{"title":"The Giant Component in a Random Subgraph of a Weak Expander","authors":"Yilun Shang","volume":52,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":698,"pagesEnd":703,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/8522","abstract":"
In this paper, we investigate the appearance of the giant component in random subgraphs G(p) of a given large finite graph family Gn = (Vn, En) in which each edge is present independently with probability p. We show that if the graph Gn satisfies a weak isoperimetric inequality and has bounded degree, then the probability p under which G(p) has a giant component of linear order with some constant probability is bounded away from zero and one. In addition, we prove the probability of abnormally large order of the giant component decays exponentially. When a contact graph is modeled as Gn, our result is of special interest in the study of the spread of infectious diseases or the identification of community in various social networks.<\/p>\r\n","references":"[1] N. Alon, I. Benjamini and A. Stacey, Percolation on finite graphs and \r\nisoperimetric inequalities. Ann. Probab., 32(2004) 1727-1745.\r\n[2] N. Alon, J. Bruck, \tJ. Naor, M. Naor and R. M. Roth, Construcction\r\nof asymptotically good low-rate error-correcting codes through pseudo-\r\nrandom graphs. IEEE TransactionS ON \u0131NFORMAT\u0130ON tHEORY, 38(1992) 509-\r\n516.\r\n[3] I. Benjamini, S. Boucheron, G. Lugosi and R. Rossignol, Sharp treshold\r\nfor percolation on expanders. arXiv:0906.3657.\r\n[4] I. Benjamini and O. Schramm, Percolation beyond Zd, many questions\r\nand a few answers. Electron. Comm. Probab., 1(1996) 71-82.\r\n[5] S. Ben-Shimon and M. Krivelevich, Vertex percolation on expander\r\ngraphs. European J. Combin., 30(2009) 339-350.\r\n[6] B. Bollob\u00e1s, Random Graphs. Cmabridge University Press, Cmabridge,\r\n2001.\r\n[7] F. Chung, P. Horn and L. Lu, Percolation in general graphs. Internet\r\nMath., 6(2009) 331-347.\r\n[8] F. Chung and L. Lu, Complex Graphs and Networks. AMS Publications,\r\n2006.\r\n[9] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge Uni-\r\nversity Press, Cambridge, 2009. \r\n[10] C. Greenhill, F. B. Holt and N. Wormald, Expansion properties of a \r\nrandom regular graph after random vertex deletions. European J. Combin.,\r\n29(2008) 1139-1150.\r\n[11] S. Janson, Large deviations for sums of partly dependent random\r\nvariales. Random Struct. Alg., 24(2004) 234-248.\r\n[12] S. Janson, T. \u0141uczak and A. Rucinski, Random Graphs. Wiley, New \r\nYork, 2000.\r\n[13] R. Lyons, Phase transtions on nonamenable graphs, J. Math. Phys.,\r\n41(2000) 1099-1126.\r\n[14] R. Lyons and Y. Peres, Probability on Trees and Networks. Cam-\r\nbridge University Press, in preparation, current version available at\r\nhttp:\/\/mypage.iu.edu\/~rdlyons\/.\r\n[15] A. Nachmias and Y. Peres, Critical percolation on random regular \r\ngraphs. Random Struct. Alg., 36(2000) 111-148.\r\n[16] B. Pittel, Edge percolation on a random regular graph of low degree. \r\nAnn. Probab., 36(2008) 1359-1389.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 52, 2011"}