igraph-help
[Top][All Lists]

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

 From: Yi Cao Subject: Re: [igraph] how to generate a bipartite graph with specified degree distributions Date: Fri, 13 May 2011 12:00:18 -0400

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 wrote:
Yi,

you're right, degree_sequence_game is fine, if you use it this way. I

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
>> >> > this?  Thank you in advanced.
>> >> >
>> >> > Best regards,
>> >> > Yi Cao
>> >> >
>> >> > _______________________________________________
>> >> > igraph-help mailing list
>> >> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>> >> >
>> >> >
>> >>
>> >>
>> >>
>> >> --
>> >> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>> >>
>> >> _______________________________________________
>> >> igraph-help mailing list
>> >> https://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>> >
>> > _______________________________________________
>> > igraph-help mailing list
>> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>> >
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>>
>> _______________________________________________
>> igraph-help mailing list
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
> _______________________________________________
> igraph-help mailing list
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>

--
Gabor Csardi <address@hidden>     MTA KFKI RMKI

_______________________________________________
igraph-help mailing list