Permanental Graphs
From MaRDI portal
Abstract: The two components for infinite exchangeability of a sequence of distributions are (i) consistency, and (ii) finite exchangeability for each . A consequence of the Aldous-Hoover theorem is that any node-exchangeable, subselection-consistent sequence of distributions that describes a randomly evolving network yields a sequence of random graphs whose expected number of edges grows quadratically in the number of nodes. In this note, another notion of consistency is considered, namely, delete-and-repair consistency; it is motivated by the sense in which infinitely exchangeable permutations defined by the Chinese restaurant process (CRP) are consistent. A goal is to exploit delete-and-repair consistency to obtain a nontrivial sequence of distributions on graphs that is sparse, exchangeable, and consistent with respect to delete-and-repair, a well known example being the Ewens permutations cite{tavare}. A generalization of the CRP as a distribution on a directed graph using the -weighted permanent is presented along with the corresponding normalization constant and degree distribution; it is dubbed the Permanental Graph Model (PGM). A negative result is obtained: no setting of parameters in the PGM allows for a consistent sequence in the sense of either subselection or delete-and-repair.
This page was built for publication: Permanental Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349676)
