igraph-help
[Top][All Lists]
Advanced

[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 10:06:48 -0400

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]