tailieunhanh - Báo cáo toán học: "Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degree"

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 .