Completely random measures for modelling block-structured sparse networks
Statistical methods for network data often parameterize the edge-probability by attributing latent traits such as block structure to the vertices and assume exchangeability in the sense of the Aldous-Hoover representation theorem. These assumptions are however incompatible with traits found in real-world networks such as a power-law degree-distribution. Recently, Caron & Fox (2014) proposed the use of a different notion of exchangeability after Kallenberg (2005) and obtained a network model which permits edge-inhomogeneity, such as a power-law degree-distribution whilst retaining desirable statistical properties. However, this model does not capture latent vertex traits such as block-structure. In this work we re-introduce the use of block-structure for network models obeying Kallenberg's notion of exchangeability and thereby obtain a collapsed model which both admits the inference of block-structure and edge inhomogeneity. We derive a simple expression for the likelihood and an efficient sampling method. The obtained model is not significantly more difficult to implement than existing approaches to block-modelling and performs well on real network datasets.
Past research had introduced the concept of exchangeability in network models, whereby two isomorphic graphs have the same distribution. In particular, Caron & Fox (2014) incorporated power-law degree inhomogeneity to exchangeability of graph models. The present paper proposes a technique to model exchangeability and edge-inhomogeneity (power-law degree distribution) but, in this case, the model incorporates also block-structure in networks.
      While the idea of modeling exchangeability for block-structure is not new in itself (see for instance Nowicki and Snijders 2001 for statistical perspective of the same problem), the perspective the authors follow seems novel because they extend Kallenberg exchangeability to model block-structure. While this approach can help elucidate exchangeability in network models I have a few concerns about the empirical evidence shown in the paper and the presentation of sections 2.2-2.5.  Some drawbacks:  Technical:       The experiments state that the choice of parameters for the competing models is "similar" to the choice for the proposed model without providing the experimental setup for the alternative models. However, this should be explicitly explained for replicability purposes.         The results themselves seem not very convincing. For instance, in figure 4b the performance of the proposed model DCSBM seem not very much better than that of competing alternatives, except for the first 3 datasets. However, and more importantly, not much can be said of the advantage of DCSBM because the results are for a single run (with thousands of iterations of the algorithm). Hence, without an statistical assessment of the results it is hard to tell what is the advantage of the proposed model with respect to the other alternatives (for instance Nowicki and Snijders (2001)).         Lastly, the conclusion could be improved by explicitly stating how much reduction of the number of parameters (line 284) is attained with the proposed model.        Presentation:        In general Sections 2.2-2.5 specialy 2.4 and 2.5 are hard to follow. I would kindly recommend to review these sections. The reason for this is that some notational information is not explicitly explained, or has been omitted. For instance:              All symbols used in the paper must be explicitly defined including $\delta$ (Dirac measure?). This also applies to operations, e.g. $o$ or $\otimes$ in line 113 or $dw$ and $d\theta$.              Please, kindly explicitly state what basic properties of completely random measures (CRM) make the thinned measures in line 172 also CRM (Don't leave this to the reader).              The authors do not define what the equality in line 40 means (equality in distribution?, I assume).              The paper leaves many details (e.g paragraph 190-195) to outside sources which makes it not fully self-contained.              Some minor typos: The sentence 32-33 "will to refer to". Many openning/closing brackets are of the type [a,b [ (this may be a type unless the authors meant open intervals, which is not stated in the paper): e.g. line 126, line 180. Possible should replace possibly in line 110, and vertex should replace vertice in line 93