Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks

Chan, Jeffrey; Lam, Samantha; Hayes, Conor

doi:10.5591/978-1-57735-516-8/IJCAI11-207

Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks

Jeffrey Chan, Samantha Lam, Conor Hayes

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1218-1223.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-207

Abstract

In recent years, the summarisation and decomposition of social networks has become increasingly popular, from community finding to role equivalence. However, these approaches concentrate on one type of model only. Generalised block modelling decomposes a network into independent, interpretable, labeled blocks, where the block labels summarise the relationship between two sets of users. Existing algorithms for fitting generalised block models do not scale beyond networks of 100 vertices. In this paper, we introduce two new algorithms, one based on genetic algorithms and the other on simulated annealing, that is at least two orders of magnitude faster than existing algorithms and obtaining similar accuracy. Using synthetic and real datasets, we demonstrate their efficiency and accuracy and show how generalised block modelling and our new approaches enable tractable network summarisation and modelling of medium sized networks.

Jeffrey Chan, Samantha Lam, and Conor Hayes. 2011. Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1218–1223. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-207

@inproceedings{ijcai2011p207,
  title     = {Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks},
  author    = {Chan, Jeffrey and Lam, Samantha and Hayes, Conor},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1218--1223},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-207},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-207},
}

TY  - CPAPER
TI  - Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks
AU  - Chan, Jeffrey
AU  - Lam, Samantha
AU  - Hayes, Conor
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1218
EP  - 1223
DO  - 10.5591/978-1-57735-516-8/IJCAI11-207
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-207
ER  -