random_graph stochastic block model produces unreasonably interconnected blocks

graph-tool
1

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.

2

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

3

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")

4

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

5

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))*.

6

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)