[graph-tool] Effect of hubs in WSBM

Dominik Schlechtweg dominik.schlechtweg at gmx.de
Thu Jul 16 00:49:52 CEST 2020


Hi Tiago,

we noticed that with certain weighted graphs minimize_blockmodel_dl() tends to put hubs (vertices with many edges) into the same cluster. Please find a minimal example below, which produces the clustered graph in the attached plot. This happens even if edge weights are distributed uniformly over edges. Is this intended behavior?

We wonder if a possible explanation could be that the WSBM is fit to predict edge weights *as well as edge probabilities*. (Compare to formulas (1) and (4) in [1].) Hence, vertices with similar degrees tend to end up in the same cluster, if the edge weights do not contradict this. Is this correct?

In case the above makes any sense, is there a way to suppress the likelihood of the edge probabilities as in [2] where the alpha-parameter can be used to fit "only to the weight information"? (Compare to formula (4) in [2].)

This is also related to the question we asked here:

https://git.skewed.de/count0/graph-tool/-/issues/664

Best,
Dominik (and Enrique)

[1] Tiago Peixoto. 2017. Nonparametric weighted stochastic block models. Physical Review E, 97.
[2] C. Aicher, A. Z. Jacobs, and A. Clauset. 2014.  Learning  latent  block  structure  in  weighted  networks. Journal of Complex Networks, 3(2):221–248.

-----
import graph_tool.all as gt

h = gt.Graph(directed=False)

h.add_edge(0,3)
h.add_edge(1,3)
h.add_edge(2,3)
h.add_edge(8,3)
h.add_edge(9,3)
h.add_edge(12,3)
h.add_edge(13,3)
h.add_edge(14,3)
h.add_edge(15,3)

h.add_edge(3,4)
h.add_edge(5,4)
h.add_edge(6,4)
h.add_edge(7,4)
h.add_edge(10,4)
h.add_edge(11,4)
h.add_edge(16,4)
h.add_edge(17,4)
h.add_edge(18,4)
h.add_edge(19,4)
h.add_edge(20,4)

h.add_edge(22,21)
h.add_edge(23,21)
h.add_edge(24,21)
h.add_edge(25,21)
h.add_edge(26,21)
h.add_edge(27,21)
h.add_edge(28,21)
h.add_edge(29,21)
h.add_edge(30,21)
h.add_edge(31,21)
h.add_edge(32,21)

h.add_edge(5, 21)

ew = h.new_edge_property("double")
ew.a = [4] * len(h.get_edges())
h.ep['weight'] = ew


state = gt.minimize_blockmodel_dl(
    h,
    state_args=dict(recs=[h.ep.weight],rec_types=["discrete-binomial"])
)

b = state.get_blocks()
b = gt.perfect_prop_hash([b])[0]


gt.graph_draw(
  h,
  edge_text=h.ep.weight,
  vertex_size=20,
  vertex_fill_color=b,
  ink_scale=0.9,
  bg_color=[1,1,1,1]
)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hub_wsbm_1.png
Type: image/png
Size: 107105 bytes
Desc: not available
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20200716/6db40701/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0x67336E43281F46CA.asc
Type: application/pgp-keys
Size: 677 bytes
Desc: not available
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20200716/6db40701/attachment-0001.bin>


More information about the graph-tool mailing list