Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees. | Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees Hamed Amini Ecole Normale Superieure - INRIA Rocquencourt Paris France hamed. amini@ Submitted Jul 31 2009 Accepted Jan 26 2010 Published Feb 8 2010 Mathematics Subject Classifications 05C80 Abstract We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process assume that each node can be in one of the two possible states inactive or active. The parameters of the model are two given functions 0 N N and a N 0 1 . At the beginning of the process each node v of degree dv becomes active with probability a dv independently of the other vertices. Presence of the active vertices triggers a percolation process if a node v is active it remains active forever. And if it is inactive it will become active when at least 0 dv of its neighbors are active. In the case where a d a and 0 d 0 for each d E N our diffusion model is equivalent to what is called bootstrap percolation. The main result of this paper is a theorem which enables us to find the final proportion of the active vertices in the asymptotic case . when n TO. This is done via analysis of the process on the multigraph counterpart of the graph model. 1 Introduction The diffusion model we consider in this paper is a generalization of bootstrap percolation in an arbitrary graph modeling a given network . Let G V E be a connected graph. Given two vertices i and j we write i j if i j E E. The threshold associated to a node i is ớ di where di is the degree of i and ớ N N is given fixed function. Assume that each node can be in one of the two possible states inactive or active. Let a N 0 1 be a fixed given function. At time 0 each node i becomes active with probability a di independently of all the other vertices. At time t E N the state of each node i will be updated according to a deterministic process if a node i was active at time t 1 it will .
