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

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

1 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äiskieliEnglanti
OtsikkoProceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
ToimittajatYang 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
KustantajaIEEE
Sivut3784-3792
Sivumäärä9
ISBN (elektroninen)978-1-5386-5035-6
ISBN (painettu)978-1-5386-5036-3
DOI - pysyväislinkit
TilaJulkaistu - 22 tammikuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaIEEE International Conference on Big Data - Seattle, Yhdysvallat
Kesto: 10 joulukuuta 201813 joulukuuta 2018
http://cci.drexel.edu/bigdata/bigdata2018/index.html

Conference

ConferenceIEEE International Conference on Big Data
LyhennettäBig Data
MaaYhdysvallat
KaupunkiSeattle
Ajanjakso10/12/201813/12/2018
www-osoite

Sormenjälki Sukella tutkimusaiheisiin 'Analysis of large sparse graphs using regular decomposition of graph distance matrices'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • 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). [8622118] IEEE. https://doi.org/10.1109/BigData.2018.8622118