Sorting, walking, coloring: faster algorithms for motif counting in large graphs
2 ottobre 2019: Ore: 11:30
Luogo: Sala Riunioni 7 piano, via Celoria 18
Speaker: Marco Bressan, Dipartimento di Informatica, Università la Sapienza di Roma
Persona di riferimeno: Nicolò Cesa-Bianchi
Given a graph G and a small integer k, can we count the occurrences of each possible k-node subgraph (the star, the cycle, the clique, and so on) in G, quickly and accurately? This motif counting problem has received intense attention in the last decade, but, due to the combinatorial explosion, all known algorithms fell short of the goal, becoming useless already for medium-sized graphs. In this talk I will present recent results based on different algorithmic techniques: parameterized computation, random walks, and color coding. The latter allowed us to scale motif counting to massive graphs, with formal guarantees and unprecedented accuracy.
The seminar’s results have appeared at ACM WSDM 2017, IEEE TKDD 2018, IPL 2019, IPEC 2019, VLDB 2019. Joint work with M. Agostini, F. Chierichetti, R. Kumar, S. Haddadan, S. Leucci, A. Panconesi.
Marco Bressan is a researcher at the Department of Computer Science at Sapienza University of Rome.