Understanding the move proposals & the agglomerative initialization in fitting a SBM

Hi Tiago,

I am trying to understand the optional argument *d* in the
graph_tool.inference.blockmodel.BlockState.mcmc_sweep() function. Reading
from its documentation, it seems to me that *d* directly controls the
probability to move to a new group, whereas the remaining move proposals
take the probability of "εB/[e_t + εB]" (where we should use B instead of
B+1). If I am understanding correctly, what is the proposal probability for
its reverse move (of the forward move to an unoccupied group)? Does it only
apply to the case where the to-be-moved node is the last one in its current
group?

My second question is about the agglomerative merge that was presented in
PRE 89, 012804 (2014). Specifically, I am trying to understand the right
column of its page 4. To initialize a partition for group numbers B, the
approach instructs us to start from B' > B, and do one and only one
"agglomerative sweep" to reach B. To do so, we had to enumerate n_m * N
possible merges for each node starting from B'. I can see that choosing a
minimal entropic change pair greedily and heuristically selects the best
block merge, but since the merge candidates are not adaptive, how does a
single enumeration of n_m * N possibilities provides sufficient candidates
that lead to B, where B'-B > 1?

Thanks,
Tzu-Chi

Hi Tiago,

I am trying to understand the optional argument *d* in the
graph_tool.inference.blockmodel.BlockState.mcmc_sweep() function. Reading
from its documentation, it seems to me that *d* directly controls the
probability to move to a new group, whereas the remaining move proposals
take the probability of "εB/[e_t + εB]" (where we should use B instead of
B+1). If I am understanding correctly, what is the proposal probability for
its reverse move (of the forward move to an unoccupied group)? Does it only
apply to the case where the to-be-moved node is the last one in its current
group?

Correct. The reverse move of putting a node in a new group is vacating the
last remaining node from a group of a single node. The move proposal
probability is computed in the same way.

My second question is about the agglomerative merge that was presented in
PRE 89, 012804 (2014). Specifically, I am trying to understand the right
column of its page 4. To initialize a partition for group numbers B, the
approach instructs us to start from B' > B, and do one and only one
"agglomerative sweep" to reach B. To do so, we had to enumerate n_m * N
possible merges for each node starting from B'. I can see that choosing a
minimal entropic change pair greedily and heuristically selects the best
block merge, but since the merge candidates are not adaptive, how does a
single enumeration of n_m * N possibilities provides sufficient candidates
that lead to B, where B'-B > 1?

This approach does not guarantee that the best merge proposals are found! To
do so would require O(B^2) comparisons, and at the initial phases where B~N
would be too slow, and probably quite wasteful.

But the point of the heuristic is to avoid this exhaustive comparison, by
trying only random merges according to the "smart" move proposals based on
inspecting neighbors. In the end, this works quite well, and is much faster
than doing an exhaustive search.

Best,
Tiago