Graphon Mixtures
This work addresses the challenge of accurately representing mixed sparse and dense structures in social networks, which is incremental as it builds on existing graphon theory.
The authors tackled the problem of modeling social networks with both hub and dense community structures by proposing a graphon mixture generative model, which theoretically enables estimation of hub degrees and sparse graphon components and demonstrates benefits on synthetic and real-world datasets.
Social networks have a small number of large hubs, and a large number of small dense communities. We propose a generative model that captures both hub and dense structures. Based on recent results about graphons on line graphs, our model is a graphon mixture, enabling us to generate sequences of graphs where each graph is a combination of sparse and dense graphs. We propose a new condition on sparse graphs (the max-degree), which enables us to identify hubs. We show theoretically that we can estimate the normalized degree of the hubs, as well as estimate the graphon corresponding to sparse components of graph mixtures. We illustrate our approach on synthetic data, citation graphs, and social networks, showing the benefits of explicitly modeling sparse graphs.