# random_graph stochastic block model produces unreasonably interconnected blocks

6 messages
Open this post in threaded view
|

## random_graph stochastic block model produces unreasonably interconnected blocks

 I'm currently building two-type random graphs of 100 vertices using the traditional_blockmodel feature of the random_graph/random_rewire functions. The degree_sampler I'm using is just lambda: poisson(5), which means that my graphs have about 250 edges. My blocks contain 15 vertices and 85 vertices respectively. When I tune the correlation function in the following way: def corr(a,b):      if a==b:         return 20      else:         return 1 I would expect, based on the documentation, that the following is approximately true: 250 edges = (15*85)*(1*p_baseline) + (15 choose 2)*(20*p_baseline)+(85 choose 2)*(20*p_baseline). Solving this equation gives an approximate value of p_baseline = .0033, given the degree_sampler I started with. If p_baseline = .0033, then p_acrossblocks = .0033*1 = .0033 as well. Since there are 85*15=1275 possible edges across the two blocks, I would expect an average of .0033*1275=4.2 edges across the blocks in the entire network. Despite this, I am continually seeing the minority block being, on average, highly centralized in the overall network, with many more edges reaching from it to the other block than would be predicted. What has gone wrong here? Have I misunderstood the vertex_corr feature? Any help would be greatly appreciated.
Open this post in threaded view
|

## Re: random_graph stochastic block model produces unreasonably interconnected blocks

 Administrator On 24.10.2016 19:28, G. B. wrote: > I'm currently building two-type random graphs of 100 vertices using the > traditional_blockmodel feature of the random_graph/random_rewire functions. > The degree_sampler I'm using is just lambda: poisson(5), which means that my > graphs have about 250 edges. My blocks contain 15 vertices and 85 vertices > respectively. > > When I tune the correlation function in the following way: > def corr(a,b): >      if a==b: > return 20 >      else: >         return 1 > > I would expect, based on the documentation, that the following is > approximately true: > 250 edges = (15*85)*(1*p_baseline) + (15 choose 2)*(20*p_baseline)+(85 > choose 2)*(20*p_baseline). Solving this equation gives an approximate value > of p_baseline = .0033, given the degree_sampler I started with. > > If p_baseline = .0033, then p_acrossblocks = .0033*1 = .0033 as well. Since > there are 85*15=1275 possible edges across the two blocks, I would expect an > average of .0033*1275=4.2 edges across the blocks in the entire network. > > Despite this, I am continually seeing the minority block being, on average, > highly centralized in the overall network, with many more edges reaching > from it to the other block than would be predicted. > > What has gone wrong here? Have I misunderstood the vertex_corr feature? Any > help would be greatly appreciated. Could you please post a complete, short, self-contained code example that shows the undesired behavior? Otherwise there is some crucial information that is left out, making it hard to troubleshoot. Best, Tiago -- Tiago de Paula Peixoto <[hidden email]> _______________________________________________ graph-tool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graph-tool signature.asc (817 bytes) Download Attachment -- Tiago de Paula Peixoto
Open this post in threaded view
|

## Re: random_graph stochastic block model produces unreasonably interconnected blocks

 Sure thing-- here's the example I was describing. Again, assuming my calculations in the previous message are correct (i.e. I'm understanding the documentation correctly), I should expect, on average, about 5 or so edges reaching from one block to the other block, with about 6-8 edges in the total network connecting minority block members to each other (and 235-237 edges in the total network connecting majority block members to each other). Instead, the minority block features a higher-than-expected connectivity, and all of the members of the minority block appear central in the overall network. Thanks in advance for any help. N = 100 P = .15 def blockMaker(v):                 if v
Open this post in threaded view
|

## Re: random_graph stochastic block model produces unreasonably interconnected blocks

 Administrator On 25.10.2016 17:42, G. B. wrote: > Sure thing-- here's the example I was describing. Again, assuming my > calculations in the previous message are correct (i.e. I'm understanding the > documentation correctly), I should expect, on average, about 5 or so edges > reaching from one block to the other block, with about 6-8 edges in the > total network connecting minority block members to each other (and 235-237 > edges in the total network connecting majority block members to each other). > Instead, the minority block features a higher-than-expected connectivity, > and all of the members of the minority block appear central in the overall > network. > > Thanks in advance for any help. > > > > N = 100 > P = .15 > > def blockMaker(v): > if v return 1 > else: > return 0 > > def corr(a,b): > if a==b: > return 20 > else: > return 1 > > g, sT = random_graph(N, lambda: poisson(5), directed=False, > model="blockmodel-traditional", > block_membership= blockMaker, > vertex_corr=corr,n_iter=100,persist=True) > > graph_draw(g, vertex_fill_color=sT, edge_color="black", output="figure.pdf") As it stands, the documentation for model="blockmodel-traditional" is imprecise. It should state that the value returned by corr(a,b) should be proportional to the probability of an edge existing between the two groups, not two nodes that belong to the two groups. In other words, the  expected total number of edges  between groups a and b will be proportional to corr(a, b). To get what you want, you need to multiply your probability by the product of the sizes, corr2(a, b) = corr(a, b) * n_a * n_b. Best, Tiago -- Tiago de Paula Peixoto <[hidden email]> _______________________________________________ graph-tool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graph-tool signature.asc (817 bytes) Download Attachment -- Tiago de Paula Peixoto