کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651529 1632578 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Uniform Sampling of Directed and Undirected Graphs Conditional on Vertex Connectivity
ترجمه فارسی عنوان
نمونه برداری یکنواخت از نمودار های جهت دار و غیرجهت دار مشروط بر اتصال پذیری ورتکس
کلمات کلیدی
فضای نمودار نمونه برداری ؛ مونت کارلوی زنجیره مارکوف ؛ شبکه های بیزی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Many applications in graph analysis require a space of graphs or networks to be sampled uniformly at random. For example, one may need to efficiently draw a small representative sample of graphs from a particular large target space. We assume that a uniform distribution f(N,E)=1/|X|f(N,E)=1/|X| has been defined, where N is a set of nodes, E is a set of edges, (N, E  ) is a graph in the target space XX and |X||X| is the (finite) total number of graphs in the target space. We propose a new approach to sample graphs at random from such a distribution. The new approach uses a Markov chain Monte Carlo method called the Neighbourhood Sampler. We validate the new sampling technique by simulating from feasible spaces of directed or undirected graphs, and compare its computational efficiency with the conventional Metropolis-Hastings Sampler. The simulation results indicate efficient uniform sampling of the target spaces, and more rapid rate of convergence than Metropolis-Hastings Sampler.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 53, September 2016, Pages 43–55
نویسندگان
, , ,