Blockmodelling Algorithm

A Blockmodelling Algorithm is a graph clustering algorithm that uses a structural relatedness measure.

• See: Stochastic Blockmodel, Stochastic Blockmodelling.

---

---

References

2013

• (Chan, Liu et al., 2013) ⇒ Jeffrey Chan, Wei Liu, Andrey Kan, Christopher Leckie, James Bailey, and Kotagiri Ramamohanarao. “Discovering latent blockmodels in sparse and noisy graphs using non-negative matrix factorisation.” In: Proceedings of the 22nd ACM International Conference on Conference on information & knowledge management, pp. 811-816. ACM, 2013.
  • http://dl.acm.org/citation.cfm?id=2505595
  • QUOTE: Blockmodelling is a powerful approach to decomposing graphs, and has been well studied in the social sciences [13]. Vertices are in the same position (group) if they have similar patterns of interactions to vertices of other positions. … Blockmodelling is an NP-Hard problem [5], hence blockmodelling algorithms only seek to find good local optima. Wang et al. [12] and Long et al. [9] have formulated the blockmodelling problem as non-negative matrix tri-factor- isation. The problem becomes one of finding the optimal positions and image matrices that simultaneously minimise the difference between the original graph and the graph approximated by the blockmodel. Similarly, Reichardt et al. [11] have shown the similarity between the blockmodelling problem and finding optimal spin configurations in material physics. While promising results were reported, there are three important, unresolved challenges. …

    … For this graph, the two factorisation algorithms preferred one position (although we initialise the algorithms to find two, see Figure 1c). As this example shows, it is important for blockmodelling algorithms to be able to handle unexpected structure and be insensitive to noise. The third challenge is the scalability of the algorithms.

2008

• Elena Zheleva, and Galileo Namata. (2008). “Stochastic Blockmodels: A Survey." ** http://www.cs.umd.edu/class/spring2008/cmsc828g/Slides/block-models.pdf

2008

• J. Fiala and D. Paulusma. The computational complexity of the role assignment problem. Technical report, 2003.

---