I'm currently building twotype 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. 
Administrator

On 24.10.2016 19:28, G. B. wrote:
> I'm currently building twotype 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. 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]> _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool signature.asc (817 bytes) Download Attachment

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 68 edges in the total network connecting minority block members to each other (and 235237 edges in the total network connecting majority block members to each other). Instead, the minority block features a higherthanexpected 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="blockmodeltraditional", block_membership= blockMaker, vertex_corr=corr,n_iter=100,persist=True) graph_draw(g, vertex_fill_color=sT, edge_color="black", output="figure.pdf") 
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 68 edges in the > total network connecting minority block members to each other (and 235237 > edges in the total network connecting majority block members to each other). > Instead, the minority block features a higherthanexpected 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="blockmodeltraditional", > 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="blockmodeltraditional" 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]> _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool signature.asc (817 bytes) Download Attachment

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 twotype random graphs with an intype linking probability between any two vertices of the same type and an acrosstype 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(nr) 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="blockmodeltraditional", block_membership= blockMaker, vertex_corr=corr,n_iter=100,persist=True) 
Administrator

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 twotype > random graphs with an intype linking probability between any > two vertices of the same type and an acrosstype 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(nr) > > 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="blockmodeltraditional", > block_membership= blockMaker, > vertex_corr=corr,n_iter=100,persist=True) > 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="blockmodeltraditional", block_membership= blockMaker, vertex_corr=corr, n_iter=1000, persist=True, parallel_edges=False, self_loops=False)  Tiago de Paula Peixoto <[hidden email]> _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool signature.asc (817 bytes) Download Attachment

Tiago de Paula Peixoto <tiago@skewed.de> 
Free forum by Nabble  Edit this page 