Unconnected Nodes within block in SBM

[whock]

In the (Goldenberg et al., 2009) review, the section on SBM makes an interesting point (Fig 3.2): You can have the nodes within a block of an SBM not connect with one another. By defining blocks according to which neurons are structurally equivalent with one another you can have a block with unconnected nodes. The nodes within a block are grouped together because they have the same "targets" despite not being connected to one another.

What clustering algorithms are there to take this kind of situation into account? What real-world examples are there of this?

[mblohr]

Perhaps the Bock paper problem is one example of this, where the excitatory neurons and inhibitory neurons can form two separate blocks. The connections within the blocks are not of interest, but the connections between the blocks are.

[whock]

That's a great point. So I wonder how you'd cluster these types of graphs? Seems like the clustering algorithm would need to tell the difference between edges that "should" define a cluster (i.e. within-block connections) and edges that should be "collapsed" across structurally equivalent nodes (i.e. block membership based on where you target, like the Bock paper as mblohr mentions).

[jtmatterer]

One clustering technique that is provably good (provided a SBM with some assumptions) is to essentially perform a SVD on the adjacency matrix and then use k-means on the singular value-scaled eigenvectors. This is detailed in Sussman et al's 2012 JASA paper and the result strengthened in Vince's 2015 Perfect Clustering paper. (Both these papers are on the syllabus)

[mblohr]

Perhaps line (i.e., edge) graphs would be another way to represent the connectivity.