Generating constrained random graphs using multiple edge switches

Details Generating constrained random graphs using multiple edge switches Generating constrained random graphs using multiple edge switches

2010-12-14

arxiv.org/abs/1012.3023v2

Computer Science

Social and Information Networks

15 pages

Scientific paper

The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints, e.g. degree distributions. However, in general, it is not necessarily possible to access all graphs obeying some given con- straints through a classical switching procedure calling on pairs of edges. We therefore propose to get round this issue by generalizing this classical approach through the use of higher-order edge switches. This method, which we denote by "k-edge switching", makes it possible to progres- sively improve the covered portion of a set of constrained graphs, thereby providing an increasing, asymptotically certain confidence on the statistical representativeness of the obtained sample.

Affiliated with

Also associated with

No associations

Rating

Generating constrained random graphs using multiple edge switches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generating constrained random graphs using multiple edge switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating constrained random graphs using multiple edge switches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179635