Abstrakt. Vi anser att en slumpmässig delgraf Gp i en värdgraf G bildas genom att behålla varje kant av G med sannolikhet p. Vi tar upp frågan om att bestämma det kritiska värdet p (som en funktion av G) för vilken en jättekomponent uppstår. Antag att G uppfyller några (mild) villkor beroende på dess spektral gap och högre ögonblick av dess grad sekvens. Vi definierar den andra ordningen genomsnitt graderas till säng = där dv betecknar graden av v. Vi bevisar att för alla > 0, om p > (1 + ) / d sedan nästan säkert den perkolerade delgraf Gp har en gigantisk komponent. I den andra riktningen, om p < (1 − ) / d sedan nästan säkert den perkolerade subgrafen Gp innehåller ingen jättekomponent.
Med d i anger graden av vertex i, det visas i REF att asymptotiskt nästan säkert en jätte komponent överlever (eller inte) om p > ð1  på P
The giant component in a random subgraph of a given graph
{'venue': 'IN WAW ’09: PROCEEDINGS OF THE 6TH INTERNATIONAL WORKSHOP ON ALGORITHMS AND MODELS FOR THE WEB-GRAPH', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}