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. -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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 <tiago@skewed.de>
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<N*P: 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") -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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<N*P: 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 <tiago@skewed.de>
Thanks for the response. Unfortunately, I have tried to derive how I should set corr(a,b) to produce the graphs I would like, but the results of my code indicate that I have not successfully done so. Hopefully you can shed some light on why my derivation does not work/where my misunderstanding persists. The graphs I would like to build are simple, undirected two-type random graphs with an in-type linking probability between any two vertices of the same type and an across-type linking probability between any two vertices of different types. Based on your last response, I take the following to be true (my sample of code is below the derivation). Let E = total number of edges in the graph (a constant). Let n_A = number of vertices in block A. Let n_B = number of vertices in block B. Let E_Across = total number of edges between block A and block B. Let E_inA = total number of edges within block A. Let E_inB = total number of edges within block B. Note that: E_Across = (n_A*n_B)*P_out E_inA = (n_A choose 2)*P_inA E_inB = (n_B choose 2)*P_inB where P_out is the linking probability between any two vertices of the different types, P_inA is the linking probability between any two vertices of type A, and P_inB is the linking probability between any two vertices of type B. Then it follows from your comment ("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)") that for vertex a in block A and vertex b in block B, corr(a,b) = k*(E_Across/E) = (k/E) * (n_A*n_B*P_out) where k is some constant of proportionality. Similarly, for vertices a_1 and a_2 in block A, corr(a_1,a_2) = k*(E_inA/E) = (k/E) * ((n_A choose 2)*P_inA) and for vertices b_1 and b_2 in block B, corr(b_1,b_2) = k*(E_inB/E) = (k/E) * ((n_B choose 2)*P_inB). If I want P_inA = P_inB, I rearrange the last two expressions and see that: corr(a_1,a_2) = corr(b_1,b_2) *((n_A choose 2)/(n_B choose 2)) Finally, since I want in my model that *P_inA=P_inB=f*P_out* where f is some scaling factor, I do similar algebra and see that: *corr(a_1,a_2) = f*corr(a,b)*((n_A choose 2)/(n_A*n_B))*. and *corr(b_1,b_2) = f*corr(a,b)*((n_B choose 2)/(n_A*n_B))*. ~~~~~~~~~ Based on this math, I wrote the following code: N = 100 n_A = 15 n_B = 85 def combinations(n, r): return factorial(n) // factorial(r) // factorial(n-r) def blockMaker(v): if v<n_A: return 1 else: return 0 def corr(a,b): BASE=1 f=5 if a==b: if a==1: return f*BASE*(combinations(n_A,2)/(n_A*n_B)) else: return f*BASE*(combinations(n_B,2)/(n_A*n_B)) else: return BASE g, sT = random_graph(N, lambda: poisson(5), directed=False, model="blockmodel-traditional", block_membership= blockMaker, vertex_corr=corr,n_iter=100,persist=True) -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 28.10.2016 19:40, G. B. wrote:
Thanks for the response. Unfortunately, I have tried to derive how I should set corr(a,b) to produce the graphs I would like, but the results of my code indicate that I have not successfully done so. Hopefully you can shed some light on why my derivation does not work/where my misunderstanding persists.
The graphs I would like to build are simple, undirected two-type random graphs with an in-type linking probability between any two vertices of the same type and an across-type linking probability between any two vertices of different types. Based on your last response, I take the following to be true (my sample of code is below the derivation).
Let E = total number of edges in the graph (a constant). Let n_A = number of vertices in block A. Let n_B = number of vertices in block B.
Let E_Across = total number of edges between block A and block B. Let E_inA = total number of edges within block A. Let E_inB = total number of edges within block B.
Note that:
E_Across = (n_A*n_B)*P_out E_inA = (n_A choose 2)*P_inA E_inB = (n_B choose 2)*P_inB
where P_out is the linking probability between any two vertices of the different types, P_inA is the linking probability between any two vertices of type A, and P_inB is the linking probability between any two vertices of type B.
Then it follows from your comment ("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)") that for vertex a in block A and vertex b in block B,
corr(a,b) = k*(E_Across/E) = (k/E) * (n_A*n_B*P_out)
where k is some constant of proportionality.
Similarly, for vertices a_1 and a_2 in block A,
corr(a_1,a_2) = k*(E_inA/E) = (k/E) * ((n_A choose 2)*P_inA)
and for vertices b_1 and b_2 in block B,
corr(b_1,b_2) = k*(E_inB/E) = (k/E) * ((n_B choose 2)*P_inB).
If I want P_inA = P_inB, I rearrange the last two expressions and see that:
corr(a_1,a_2) = corr(b_1,b_2) *((n_A choose 2)/(n_B choose 2))
Finally, since I want in my model that *P_inA=P_inB=f*P_out* where f is some scaling factor, I do similar algebra and see that:
*corr(a_1,a_2) = f*corr(a,b)*((n_A choose 2)/(n_A*n_B))*. and *corr(b_1,b_2) = f*corr(a,b)*((n_B choose 2)/(n_A*n_B))*.
~~~~~~~~~
Based on this math, I wrote the following code:
N = 100 n_A = 15 n_B = 85
def combinations(n, r): return factorial(n) // factorial(r) // factorial(n-r)
def blockMaker(v): if v<n_A: return 1 else: return 0
def corr(a,b): BASE=1 f=5 if a==b: if a==1: return f*BASE*(combinations(n_A,2)/(n_A*n_B)) else: return f*BASE*(combinations(n_B,2)/(n_A*n_B)) else: return BASE
g, sT = random_graph(N, lambda: poisson(5), directed=False, model="blockmodel-traditional", block_membership= blockMaker, vertex_corr=corr,n_iter=100,persist=True)
This is overly complicated. I believe this will do what you want: # These are your parameters, use whatever you want N = 100 n = [15, 85] p_in = [.1, .03] p_out = .003 # Total number of edges, conditioned on the parameters E = 0 for a in range(2): E += p_in[a] * (n[a] * (n[a] - 1)) / 2 E += p_out * n[0] * n[1] # Avg degree ak = 2 * E / N def blockMaker(v): if v < n[0]: return 0 else: return 1 def corr(a, b): if a == b: return p_in[a] * (n[a] * (n[a] - 1)) / 2 else: return p_out * n[a] * n[b] g, b = random_graph(N, lambda: poisson(ak), directed=False, model="blockmodel-traditional", block_membership= blockMaker, vertex_corr=corr, n_iter=1000, persist=True, parallel_edges=False, self_loops=False) -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
G. B. -
Tiago de Paula Peixoto