Random graph generation using multiple switches of edges

National audienceGenerating random graphs which verify a set of predefined properties is a major issue for the analysis of interaction networks. However, there is no general method available for practical cases, where the set of desired properties is complex. We propose a generation method which theoretically allows to obtain a uniform sample of any set of graphs, as long as we have an element of this set and the degree distribution is one of the required properties. This method, called k-edge switching, is a generalization of Monte-Carlo Markov Chain methods of the literature which rely on iterating exchanges of edges ends. We describe its conception and implementation, as well as the technical difficulties encountered and how to overcome them. This method is applied on scientific collaboration networks, and we show that we can point out a small set of properties which can explain typical characteristics of the network