Graphon Mixtures
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning
Real-world graph datasets often arise from mixtures of populations, where graphs are generated by multiple distinct underlying distributions. In this work, we propose a unified framework that explicitly models graph data…
Contrastive LearningData AugmentationGraphon Signal Processing
Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs as their number of nodes goes to infinity. This paper derives a theory of graphon signal processing centered on the not…
Modularity maximisation for graphons
Networks are a widely-used tool to investigate the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite size limit of dense networks. The detection of communities or other …
Community DetectionOpen-Ended Question AnsweringPrivacy PreservingGraphon games and an idealized limit of large network games
Graphon games are a class of games with a continuum of agents, introduced to approximate the strategic interactions in large network games. The first result of this study is an equilibrium existence theorem in graphon ga…
Graph and graphon neural network stability
Graph neural networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of large-scale network data. GNN stability is thus important as in real-world s…
Movie Recommendation