The Giant Component in a Random Subgraph of a Weak Expander
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.
[1] N. Alon, I. Benjamini and A. Stacey, Percolation on finite graphs and
isoperimetric inequalities. Ann. Probab., 32(2004) 1727-1745.
[2] N. Alon, J. Bruck, J. Naor, M. Naor and R. M. Roth, Construcction
of asymptotically good low-rate error-correcting codes through pseudo-
random graphs. IEEE TransactionS ON ıNFORMATİON tHEORY, 38(1992) 509-
516.
[3] I. Benjamini, S. Boucheron, G. Lugosi and R. Rossignol, Sharp treshold
for percolation on expanders. arXiv:0906.3657.
[4] I. Benjamini and O. Schramm, Percolation beyond Zd, many questions
and a few answers. Electron. Comm. Probab., 1(1996) 71-82.
[5] S. Ben-Shimon and M. Krivelevich, Vertex percolation on expander
graphs. European J. Combin., 30(2009) 339-350.
[6] B. Bollobás, Random Graphs. Cmabridge University Press, Cmabridge,
2001.
[7] F. Chung, P. Horn and L. Lu, Percolation in general graphs. Internet
Math., 6(2009) 331-347.
[8] F. Chung and L. Lu, Complex Graphs and Networks. AMS Publications,
2006.
[9] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge Uni-
versity Press, Cambridge, 2009.
[10] C. Greenhill, F. B. Holt and N. Wormald, Expansion properties of a
random regular graph after random vertex deletions. European J. Combin.,
29(2008) 1139-1150.
[11] S. Janson, Large deviations for sums of partly dependent random
variales. Random Struct. Alg., 24(2004) 234-248.
[12] S. Janson, T. Łuczak and A. Rucinski, Random Graphs. Wiley, New
York, 2000.
[13] R. Lyons, Phase transtions on nonamenable graphs, J. Math. Phys.,
41(2000) 1099-1126.
[14] R. Lyons and Y. Peres, Probability on Trees and Networks. Cam-
bridge University Press, in preparation, current version available at
http://mypage.iu.edu/~rdlyons/.
[15] A. Nachmias and Y. Peres, Critical percolation on random regular
graphs. Random Struct. Alg., 36(2000) 111-148.
[16] B. Pittel, Edge percolation on a random regular graph of low degree.
Ann. Probab., 36(2008) 1359-1389.
[1] N. Alon, I. Benjamini and A. Stacey, Percolation on finite graphs and
isoperimetric inequalities. Ann. Probab., 32(2004) 1727-1745.
[2] N. Alon, J. Bruck, J. Naor, M. Naor and R. M. Roth, Construcction
of asymptotically good low-rate error-correcting codes through pseudo-
random graphs. IEEE TransactionS ON ıNFORMATİON tHEORY, 38(1992) 509-
516.
[3] I. Benjamini, S. Boucheron, G. Lugosi and R. Rossignol, Sharp treshold
for percolation on expanders. arXiv:0906.3657.
[4] I. Benjamini and O. Schramm, Percolation beyond Zd, many questions
and a few answers. Electron. Comm. Probab., 1(1996) 71-82.
[5] S. Ben-Shimon and M. Krivelevich, Vertex percolation on expander
graphs. European J. Combin., 30(2009) 339-350.
[6] B. Bollobás, Random Graphs. Cmabridge University Press, Cmabridge,
2001.
[7] F. Chung, P. Horn and L. Lu, Percolation in general graphs. Internet
Math., 6(2009) 331-347.
[8] F. Chung and L. Lu, Complex Graphs and Networks. AMS Publications,
2006.
[9] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge Uni-
versity Press, Cambridge, 2009.
[10] C. Greenhill, F. B. Holt and N. Wormald, Expansion properties of a
random regular graph after random vertex deletions. European J. Combin.,
29(2008) 1139-1150.
[11] S. Janson, Large deviations for sums of partly dependent random
variales. Random Struct. Alg., 24(2004) 234-248.
[12] S. Janson, T. Łuczak and A. Rucinski, Random Graphs. Wiley, New
York, 2000.
[13] R. Lyons, Phase transtions on nonamenable graphs, J. Math. Phys.,
41(2000) 1099-1126.
[14] R. Lyons and Y. Peres, Probability on Trees and Networks. Cam-
bridge University Press, in preparation, current version available at
http://mypage.iu.edu/~rdlyons/.
[15] A. Nachmias and Y. Peres, Critical percolation on random regular
graphs. Random Struct. Alg., 36(2000) 111-148.
[16] B. Pittel, Edge percolation on a random regular graph of low degree.
Ann. Probab., 36(2008) 1359-1389.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:57599", author = "Yilun Shang", title = "The Giant Component in a Random Subgraph of a Weak Expander", 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.
", keywords = "subgraph, expander, random graph, giant component, percolation.", volume = "5", number = "4", pages = "608-5", }
