Distributed Analysis of Large-Scale Graphs

The real world is full of gra­phs. There are gra­phs hid­den in the friend­ship rela­tion­ships bet­ween peo­ple, in eco­no­mic tran­sac­tions, bet­ween stran­gers encoun­te­ring each other in the stree­ts, in the way gos­sip spreads throu­gh the peo­ple, and so on. Few years ago we know they were the­re, but we were not able to ana­ly­ze them becau­se the lack of data. Nowadays, howe­ver, most of the human acti­vi­ties are media­ted by some elec­tro­nic devi­ce, so lar­ge data­se­ts descri­bing the­se gra­phs have star­ted to beco­me available.

Analyzing the­se data­se­ts could be dif­fi­cult. Sometimes they are too lar­ge, some­ti­mes they are distri­bu­ted by natu­re. We have publi­shed seve­ral papers about this sub­ject, that can be cate­go­ri­zed in the fol­lo­wing areas:

• Distributed algo­ri­thms for com­pu­ting pro­per­ties of gra­phs [TPDS13] [DEBS16] [DBSDA16]
• Evaluation of big data fra­meworks [BigData13]
• Distributed fra­meworks for distri­bu­ted gra­ph ana­ly­sis [EuroPar15] [HPGP16] [CBDCom16] [IDEAS16]

---

[TPDS13]   Alberto Montresor, Francesco de Pellegrini, and Daniele Miorandi. Distributed k-core decom­po­si­tion. IEEE Trans. Parallel Distrib. Syst., 24 (2):288–300, 2013. [PDF], [Bibtex].

[BigData13]   Benedikt Elser and Alberto Montresor. An eva­lua­tion stu­dy of BigData fra­meworks for gra­ph pro­ces­sing. In Proc. of the 2013 IEEE International Conference on Big Data, BigData’13, pages 60–67. IEEE, Santa Clara, CA, USA, October 2013. ISBN 978–1‑4799–1292‑6. [PDF], [Bibtex].

[EuroPar15]   Alessio Guerrieri and Alberto Montresor. DFEP: Distributed fun­ding-based edge par­ti­tio­ning. In Proc. of the 21th International Conference on Parallel Processing, EuroPar’15. Springer, 2015. [PDF], [Bibtex].

[HPGP16]   Sabeur Aridhi, Alberto Montresor, and Yannis Velegrakis. BLADYG: A novel block-cen­tric fra­mework for the ana­ly­sis of lar­ge dyna­mic gra­phs. In Proceedings of the ACM Workshop on High Performance Graph Processing, HPGP@HPDC 2016, pages 39–42. ACM, Kyoto, Japan, May 2016. [PDF], [Bibtex].

[DEBS16]   Sabeur Aridhi, Martin Brugnara, Yannis Velegrakis, and Alberto Montresor. Distributed k-core decom­po­si­tion and main­te­nan­ce in lar­ge dyna­mic gra­phs. In Proc. of the 10th ACM International Conference on Distributed and Event-Based Systems, DEBS’16. ACM, Irvine, CA, June 2016. [PDF], [Bibtex].

[CBDCom16]   Alessio Guerrieri, Alberto Montresor, and Simone Centellegher. ETSCH: Partition-cen­tric gra­ph pro­ces­sing. In Proc. of the 1st International Conference on Cloud and Big Data Computing, CBDCom’16. IEEE, Toulouse, France, July 2016. [PDF], [Bibtex].

[IDEAS16]   Chayma Sakouhi, Sabeur Aridhi, Alessio Guerrieri, Salma Sassi, and Alberto Montresor1. DynamicDFEP: A distri­bu­ted edge par­ti­tio­ning approach for lar­ge dyna­mic gra­phs. In Procedings of the 20th International Database Engineering & Applications Symposium, IDEAS’16. ACM, Montreal, Canada, July 2016. [PDF], [Bibtex].

[DBSDA16]   Alessio Guerrieri, Fatemeh Rahimian, Sarunas Girdzijauskas, and Alberto Montresor. Tovel: Distributed gra­ph clu­ste­ring for word sen­se disam­bi­gua­tion. In Procedings of the 4th ICDM Workshop on Data Science and Big Data Analytics, DSBDA’16. IEEE, Barcelona, Spain, December 2016. [PDF], [Bibtex].