Analysis of large sparse graphs using regular decomposition of graph distance matrices

Abstract

Statistical analysis of large and sparse graphs is a challenging problem in data science due to the high dimensionality and nonlinearity of the problem. This paper presents a fast and scalable algorithm for partitioning such graphs into disjoint groups based on observed graph distances from a set of reference nodes. The resulting partition provides a low-dimensional approximation of the full distance matrix which helps to reveal global structural properties of the graph using only small samples of the distance matrix. The presented algorithm is inspired by the information-theoretic minimum description principle. We investigate the performance of this algorithm for selected real data sets and for synthetic graph data sets generated using stochastic block models and power-law random graphs, together with analytical considerations for sparse stochastic block models with bounded average degrees.

arXiv commentIEEE BigData 2018 Conference Workshop, Advances in High Dimensional Big Data, 10.-13.12. 2018, Seattle USA

References in corpus (8)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Sparse graphs using exchangeable random measures
• Generalized communities in networks
• Community Detection in Networks using Graph Distance
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• Diclique clustering in a directed random graph
• Moment-based parameter estimation in binomial random intersection graph models