Re: [igraph] how to generate a bipartite graph with specified degree distributions

[Gábor Csárdi]

Yi Cao,

you'll need to give us some small (but complete!) example program that
breaks, otherwise we have no chance to guess what you're doing wrong.

Best,,
Gabor

On Fri, May 13, 2011 at 12:00 PM, Yi Cao <address@hidden> wrote:
> Hello Gabor,
>
>       Sorry for trouble you again and thank you for your time and help.
>       I used a simple input file  "test.dat" like this:        0   1
>
> 0   2
>
> 0   3
>
> 4   5
>
> 4   6
>
> 4   7
>      I use this file as an input edge-list file for creating a bipartite
> graph. The resulted graph has 8 vertices and 6 edges, and two components.
>      Let me state just part of what I was doing in my program:
>
>       First,  I use    igraph_degree(&g1,&out_deg,vids1,IGRAPH_ALL,0)
> where vids1 stores the vertices in first column in the edge-list file.
>                      igraph_degree(&g1,&in_deg,vids1,IGRAPH_ALL,0)
> where vids2 stores the vertices in second column in the edge-list file.
>
>      Second, I use "&out_deg" and "&in_deg" as two argument values for the
> function  igraph_degree_sequence_game(&g2,&out_deg,&in_deg,
> IGRAPH_DEGSEQ_SIMPLE);
>                and then I got the error information : Error at games.c
> :142:Length of 'out_seq' and 'in_seq' differ for directed graph, Invalid
> value. Aborted.
> I think the out_deg and in_deg should be equal in this case, and we can also
> tell from the input that it should be ok. But why did the error occur? I am
> confused about this. Can you give me some ideas? Thank you very much.
>
> Best regards,
> Yi Cao
>
> On Thu, May 12, 2011 at 10:06 AM, Gábor Csárdi <address@hidden> wrote:
>>
>> Yi,
>>
>> you're right, degree_sequence_game is fine, if you use it this way. I
>> didn't read your mail carefully enough, sorry about that.
>>
>> In this case, you'll be creating a directed graph, so you can only use
>> the 'simple' method. This picks edge-stubs uniformly randomly, in
>> other words the probability of picking a node is proportional to its
>> remaining in- or out-degree.
>>
>> I believe that this method creates all possible labeled graphs with
>> equal probability, but I haven't proved it formally. Note that the
>> generated graphs will not necessarily be connected.
>>
>> Best,
>> Gabor
>>
>> On Thu, May 12, 2011 at 9:55 AM, Yi Cao <address@hidden> wrote:
>> > Hello Babor,
>> >
>> > 1. Thank you very much for pointing out my misusage of
>> > igraph_degree_sequence_game().  But I don't understand where the problem
>> > is
>> > in the method I proposed. Because the vertices in the same bag can not
>> > be
>> > connected and edges only appear between the two bags, therefore I think
>> > the
>> > graph produced this way should be (directed) bipartite graph. I would be
>> > appreciated if you point out why igraph_degree_sequence_game() can not
>> > produce bipartite graph.
>> > 2. How can I produce bipartite graph supposed I know the degree
>> > sequences of
>> > the two vertices sets? I prefer to use functions in igraph C library.
>> > Thank
>> > you so much.
>> >
>> > Best regards,
>> > Yi Cao
>> >
>> > On Thu, May 12, 2011 at 9:27 AM, Gábor Csárdi <address@hidden>
>> > wrote:
>> >>
>> >> 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-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-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