A great deal of attention has recently been paid to determining sub-communities on the basis of relations, corresponding to edges, between individuals, corresponding to vertices of an unlabelled graph (Newman SIAM Review 2003; Airoldi et al. JMLR 2008; Leskovec & Kleinberg et al. SIGKDD 2005). We develop a nonparametric framework for probabilistic ergodic models of infinite unlabelled graphs and make some connections with modularities arising in the physics literature. We derive consistency properties of the Newman–Girvan modularity, and develop an index with better consistency properties and better performance on simulated data sets.
This is joint work with Aiyou Chen.