igraph-help
[Top][All Lists]

## 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: Fri, 13 May 2011 15:50:15 -0400

```Yes, this makes sense, of course.

You'll need to add all the vertices to the same graph, i.e. to the
same degree vectors. In out_deg, the first n1 values should be the
degrees of the vertices in the first bucket, the next n2 values will
be zero. In in_deg, the first n1 values will be zero, the next n2
values will be the degrees of the vertices in the second bucket.

Gabor

On Fri, May 13, 2011 at 3:14 PM, Yi Cao <address@hidden> wrote:
> Hello Gabor,
>
> The following is the short program.
>
> #include<stdio.h>
> #include<iostream>
> #include<fstream>
> #include<igraph.h>
> using namespace std;
> main()
> {
> igraph_t g2;
> igraph_vector_t out_deg;
> igraph_vector_t in_deg;
> igraph_vector_init(&out_deg,6);
> igraph_vector_init(&in_deg,6);
> VECTOR(out_deg)[0]=1;
> VECTOR(out_deg)[1]=1;
> VECTOR(out_deg)[2]=1;
> VECTOR(out_deg)[3]=1;
> VECTOR(out_deg)[4]=1;
> VECTOR(out_deg)[5]=1;
> VECTOR(in_deg)[1]=1;
> VECTOR(in_deg)[2]=1;
> VECTOR(in_deg)[3]=1;
> VECTOR(in_deg)[4]=1;
> VECTOR(in_deg)[5]=1;
> VECTOR(in_deg)[0]=1;
> FILE *outstream;
> outstream=fopen("g2output.txt","a");
> igraph_degree_sequence_game(&g2,&out_deg,&in_deg,IGRAPH_DEGSEQ_SIMPLE);
> igraph_write_graph_edgelist(&g2,outstream);
> igraph_vector_destroy(&out_deg);
> igraph_vector_destroy(&in_deg);
> return 0;
> }
>
> This program works well. But when I made some little changes as:
> .............
> igraph_vector_init(&out_deg,3);
> igraph_vector_init(&in_deg,6);
> VECTOR(out_deg)[0]=3;
> VECTOR(out_deg)[1]=3;
> .............
> then it reports error: the length of out_deg and in_deg are not equal. So,
> the function igraph_degree_sequence_game() requires that the length of
> out_deg and in_deg are the same. For each vertex, its out degree is stored
> in vector out_deg and its in degree is stored in vector in_deg. The length
> of vector out_deg and in_deg are the same and equal to the number of
> vertices. Therefore, I think you are right, we can not create bipartite
> graphs with function igraph_degree_sequence_game().
>
> Now I really want to know how I can produce a bipartite graph with the given
> degree histogram (or degree sequence) for each side of a bipartite graph?
>
> Thank you so much for your time. I really appreciate it.
>
> Best regards,
> Yi Cao
>
>
> On Fri, May 13, 2011 at 9:15 AM, Gábor Csárdi <address@hidden> wrote:
>>
>> 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
>> >> 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

```

reply via email to