Vertex clustering in random graphs via reversihle jump Markov chain Monte Carlo

Networks are a natural and effective tool to study relational data, in which observations are collected on pairs of units. The units are represented by nodes and their relations by edges. In biology, for example, proteins and their interactions may be the nodes and the edges of the network; in social science, the nodes and edges may be people and interpersonal relations. In this article we address the question of clustering vertices in networks as a way to uncover homogeneity patterns in data that enjoy a network representation. We use a mixture model for random graphs and propose a reversible jump Markov chain Monte Carlo algorithm to infer its parameters. Applications of the algorithm to one simulated dataset and three real datasets, which describe friendships among members of a university karate club, social interactions of dolphins, and gap junctions in the C. Elegans, are given.