Logistic-Tropical Decompositions and Nested Subgraphs
Sanjar Karaev, Saskia Metzler, Pauli Miettinen · MPG.PuRe (Max Planck Society) · 2018
Communities in graphs are usually modelled as (quasi-) cliques, but this is not the only -or even necessarily the best -model.Other models, such as stars, hyperbolic shapes, or core-periphery communities have been proposed as well.ese can be generalized to nested subgraphs, i.e. graphs whose adjacency matrix is nested.In this paper, we study the problem of summarizing a graph as a union of nested subgraphs.We approach the problem by applying a recent characterization of nested graphs using rounding rank.We extend this characterization to sets of overlapping nested matrices using tropical algebra. is allows us to model the problem as a thresholded tropical matrix factorization, and to design an algorithm for a maximum-likelihood version of the problem.Our experiments show that our algorithm is very scalable and can find good summarizations using structures that cannot be concisely expressed in terms of normal matrix factorizations.