Hoeffding-type decomposition for U-statistics on bipartite networks

We consider a broad class of random bipartite networks, the distribution of which is invariant under permutation within each type of nodes. We are interested in U-statistics defined on the adjacency matrix of such a network, for which we define a new type of Hoeffding decomposition based on the Aldous-Hoover-Kallenberg representation of row-column exchangeable matrices. This decomposition enables us to characterize non-degenerate U-statistics – which are then asymptotically normal – and provides us with a natural and easy-to-implement estimator of their asymptotic variance. We illustrate the use of this general approach on some typical random graph models and use it to estimate or test some quantities characterizing the topology of the associated network. We also assess the accuracy and the power of the proposed estimates or tests, via a simulation study.