Analysis of large sparse graphs using regular decomposition of graph distance matrices
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2019-01-22
Major/Subject
Mcode
Degree programme
Language
en
Pages
9
3784-3792
3784-3792
Series
2018 IEEE International Conference on Big Data (Big Data)
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.Description
Keywords
Other note
Citation
Reittu , H , Leskelä , L , Räty , T & Fiorucci , M 2019 , Analysis of large sparse graphs using regular decomposition of graph distance matrices . in Y Song , B Liu , K Lee , N Abe , C Pu , M Qiao , N Ahmed , D Kossmann , J Saltz , J Tang , J He , H Liu & X Hu (eds) , Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018 . , 8622118 , IEEE , pp. 3784-3792 , IEEE International Conference on Big Data , Seattle , Washington , United States , 10/12/2018 . https://doi.org/10.1109/BigData.2018.8622118