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

Hannu Reittu; Lasse Leskelä; Tomi Räty; Marco Fiorucci

doi:10.1109/BigData.2018.8622118

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

Hannu Reittu
, Lasse Leskelä
, Tomi Räty
, Marco Fiorucci

VTT Technical Research Centre of Finland Ltd.
Ca' Foscari University of Venice

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

8 Sitaatiot (Scopus)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
Toimittajat	Yang Song, Bing Liu, Kisung Lee, Naoki Abe, Calton Pu, Mu Qiao, Nesreen Ahmed, Donald Kossmann, Jeffrey Saltz, Jiliang Tang, Jingrui He, Huan Liu, Xiaohua Hu
Kustantaja	IEEE
Sivut	3784-3792
Sivumäärä	9
ISBN (elektroninen)	978-1-5386-5035-6
ISBN (painettu)	978-1-5386-5036-3
DOI - pysyväislinkit	https://doi.org/10.1109/BigData.2018.8622118
Tila	Julkaistu - 22 tammik. 2019
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	IEEE International Conference on Big Data - Seattle, Yhdysvallat Kesto: 10 jouluk. 2018 → 13 jouluk. 2018 http://cci.drexel.edu/bigdata/bigdata2018/index.html

Conference

Conference	IEEE International Conference on Big Data
Lyhennettä	Big Data
Maa/Alue	Yhdysvallat
Kaupunki	Seattle
Ajanjakso	10/12/2018 → 13/12/2018
www-osoite	http://cci.drexel.edu/bigdata/bigdata2018/index.html

Pääsy asiakirjaan

10.1109/BigData.2018.8622118

https://arxiv.org/abs/1811.10470

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

Reittu, H., Leskelä, L., Räty, T., & Fiorucci, M. (2019). Analysis of large sparse graphs using regular decomposition of graph distance matrices. teoksessa 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 (Toimittajat), Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018 (Sivut 3784-3792). Artikkeli 8622118 IEEE. https://doi.org/10.1109/BigData.2018.8622118

Reittu, Hannu ; Leskelä, Lasse ; Räty, Tomi et al. / Analysis of large sparse graphs using regular decomposition of graph distance matrices. Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018. Toimittaja / Yang Song ; Bing Liu ; Kisung Lee ; Naoki Abe ; Calton Pu ; Mu Qiao ; Nesreen Ahmed ; Donald Kossmann ; Jeffrey Saltz ; Jiliang Tang ; Jingrui He ; Huan Liu ; Xiaohua Hu. IEEE, 2019. Sivut 3784-3792

@inproceedings{9dee2047147143d7bdb8e21bea1c703e,

title = "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.",

author = "Hannu Reittu and Lasse Leskel{\"a} and Tomi R{\"a}ty and Marco Fiorucci",

year = "2019",

month = jan,

day = "22",

doi = "10.1109/BigData.2018.8622118",

language = "English",

isbn = "978-1-5386-5036-3",

pages = "3784--3792",

editor = "Yang Song and Bing Liu and Kisung Lee and Naoki Abe and Calton Pu and Mu Qiao and Nesreen Ahmed and Donald Kossmann and Jeffrey Saltz and Jiliang Tang and Jingrui He and Huan Liu and Xiaohua Hu",

booktitle = "Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018",

publisher = "IEEE",

address = "United States",

note = "IEEE International Conference on Big Data, Big Data ; Conference date: 10-12-2018 Through 13-12-2018",

url = "http://cci.drexel.edu/bigdata/bigdata2018/index.html",

}

Reittu, H, Leskelä, L, Räty, T & Fiorucci, M 2019, Analysis of large sparse graphs using regular decomposition of graph distance matrices. julkaisussa 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 (toim), Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018., 8622118, IEEE, Sivut 3784-3792, IEEE International Conference on Big Data, Seattle, Washington, Yhdysvallat, 10/12/2018. https://doi.org/10.1109/BigData.2018.8622118

Analysis of large sparse graphs using regular decomposition of graph distance matrices. / Reittu, Hannu; Leskelä, Lasse; Räty, Tomi et al.
Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018. toim. / Yang Song; Bing Liu; Kisung Lee; Naoki Abe; Calton Pu; Mu Qiao; Nesreen Ahmed; Donald Kossmann; Jeffrey Saltz; Jiliang Tang; Jingrui He; Huan Liu; Xiaohua Hu. IEEE, 2019. s. 3784-3792 8622118.

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

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

AU - Reittu, Hannu

AU - Leskelä, Lasse

AU - Räty, Tomi

AU - Fiorucci, Marco

PY - 2019/1/22

Y1 - 2019/1/22

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85062642513

U2 - 10.1109/BigData.2018.8622118

DO - 10.1109/BigData.2018.8622118

M3 - Conference article in proceedings

SN - 978-1-5386-5036-3

SP - 3784

EP - 3792

BT - Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018

A2 - Song, Yang

A2 - Liu, Bing

A2 - Lee, Kisung

A2 - Abe, Naoki

A2 - Pu, Calton

A2 - Qiao, Mu

A2 - Ahmed, Nesreen

A2 - Kossmann, Donald

A2 - Saltz, Jeffrey

A2 - Tang, Jiliang

A2 - He, Jingrui

A2 - Liu, Huan

A2 - Hu, Xiaohua

PB - IEEE

T2 - IEEE International Conference on Big Data

Y2 - 10 December 2018 through 13 December 2018

ER -

Reittu H, Leskelä L, Räty T, Fiorucci M. Analysis of large sparse graphs using regular decomposition of graph distance matrices. julkaisussa Song Y, Liu B, Lee K, Abe N, Pu C, Qiao M, Ahmed N, Kossmann D, Saltz J, Tang J, He J, Liu H, Hu X, toimittajat, Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018. IEEE. 2019. s. 3784-3792. 8622118 doi: 10.1109/BigData.2018.8622118

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

Abstrakti

Conference

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä