Model-based clustering in networks with Stochastic Community Finding
Aaron F. McDaid, University College Dublin, Ireland, aaronmcdaid@gmail.comThomas Brendan Murphy, University College Dublin, Ireland, brendan.murphy@ucd.ieNial Friel, University College Dublin, Ireland, nial.friel@ucd.ieNeil J. Hurley, University College Dublin, Ireland, neil.hurley@ucd.ieAbstract. In the model-based clustering of networks, blockmodelling may be used to identifyroles in the network. We identify a special case of the Stochastic Block Model (SBM) wherewe constrain the cluster-cluster interactions such that the density inside the clusters of nodesis expected to be greater than the density between clusters. This corresponds to the intuitionbehind community-ﬁnding methods, where nodes tend to clustered together if they link toeach other. We call this model Stochastic Community Finding (SCF) and present an eﬃcientMCMC algorithm which can cluster the nodes, given the network. The algorithm is evaluatedon synthetic data and is applied to a social network of interactions at a karate club and at amonastery, demonstrating how the SCF ﬁnds the ‘ground truth’ clustering where sometimesthe SBM does not. The SCF is only one possible form of constraint or specialization thatmay be applied to the SBM. In a more supervised context, it may be appropriate to use otherspecializations to guide the SBM.Keywords. Model-based clustering, MCMC, Social networks, Community ﬁnding, Blockmod-elling