[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] how to generate a bipartite graph with specified degree dis
From: |
Gábor Csárdi |
Subject: |
Re: [igraph] how to generate a bipartite graph with specified degree distributions |
Date: |
Thu, 12 May 2011 09:27:54 -0400 |
Hi Yi,
you cannot use igraph_degree_sequence_game() to generate bipartite graphs.
Otherwise, yes, the 'vl' method generates connected, undirected graphs
with equal probability. But not only bipartite graphs. See its
detailed description in the cited paper.
Best,
Gabor
On Thu, May 12, 2011 at 9:03 AM, Yi Cao <address@hidden> wrote:
> Hello Gabor,
>
> Now I get the degree sequence for each side vertice set of the
> bipartite graph. I want to use the function igraph_degree_sequence_game to
> generate the bipartite graph.
> First I store one degree sequence in the argument igraph_vector_t *out_deg
> and the other in igraph_vector_t *in_deg. In the description for argument
> "method", it says that the graph is created by drawing pairs of vertices
> from two boxes till it is empty. My question is that are these pairs of
> vertices picked randomly? (or in other ways, like preferentially?)
> Does this method generate all possible graphs with equal probility ?
>
> Thank you so much.
> Best regards,
> Yi Cao
>
> On Mon, May 9, 2011 at 10:25 PM, Gábor Csárdi <address@hidden> wrote:
>>
>> Hi,
>>
>> I think the simple naive method works in this case. You generate the
>> degrees from the desired distributions, and make sure that they are
>> plausible, i.e. the total degrees in both groups are the same.
>>
>> Then you give "stubs" for each vertex, as many as their degree, and
>> simply connect the stubs uniformly randomly. This can be done by
>> simply permuting the stubs once.
>>
>> I think this can be implemented in Python or R, very quickly, in a
>> couple of lines. I am fairly, (but not completely) sure that this
>> method generates all possible graphs, with equal probability, assuming
>> that the vertices are labeled.
>>
>> Best,
>> Gabor
>>
>> On Mon, May 9, 2011 at 4:00 PM, Yi Cao <address@hidden> wrote:
>> > Hello all,
>> >
>> > Now I am trying to generate a bipartite graph with specified degree
>> > distribution. The degree distribution of one vertices set is function
>> > f(x)
>> > which is linear, the degree distribution of the other vertices set is
>> > function g(x) which is a piecewise function, including 3 parts. Now I
>> > want
>> > to create a graph with known number of vertices, edges between two
>> > vertices
>> > sets as well as the specified degree distribution as mentioned above.
>> > How
>> > can I implement this by using igraph library(preferred), or by using
>> > other
>> > package like NetworkX or else? Can anyone give me some suggestions about
>> > this? Thank you in advanced.
>> >
>> > Best regards,
>> > Yi Cao
>> >
>> > _______________________________________________
>> > igraph-help mailing list
>> > address@hidden
>> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>> >
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden> MTA KFKI RMKI
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
--
Gabor Csardi <address@hidden> MTA KFKI RMKI
- [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/09
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Gábor Csárdi, 2011/05/09
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/12
- Re: [igraph] how to generate a bipartite graph with specified degree distributions,
Gábor Csárdi <=
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/12
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Gábor Csárdi, 2011/05/12
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/13
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Gábor Csárdi, 2011/05/13
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/13
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Gábor Csárdi, 2011/05/13
- Re: [igraph] how to generate a bipartite graph with specified degree distributions, Yi Cao, 2011/05/13