random_graph stochastic block model produces unreasonably interconnected blocks

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

random_graph stochastic block model produces unreasonably interconnected blocks

G. B.
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.
Reply | Threaded
Open this post in threaded view
|

Re: random_graph stochastic block model produces unreasonably interconnected blocks

Tiago Peixoto
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 <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: random_graph stochastic block model produces unreasonably interconnected blocks

G. B.
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")
Reply | Threaded
Open this post in threaded view
|

Re: random_graph stochastic block model produces unreasonably interconnected blocks

Tiago Peixoto
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<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 <[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 <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: random_graph stochastic block model produces unreasonably interconnected blocks

G. B.
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)


Reply | Threaded
Open this post in threaded view
|

Re: random_graph stochastic block model produces unreasonably interconnected blocks

Tiago Peixoto
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 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 <[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 <tiago@skewed.de>