Welcome to the mini-website on the tutorial titled Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms, which will take place at WWW'16 in Montreal, Canada.

Abstract

Centrality measures allow to measure the relative importance of a node or an edge in a graph w.r.t. other nodes or edges. Many measures of centrality have been developed in the literature to capture different aspects of the informal concept of importance, and algorithms for different measures have been proposed.

In this tutorial, we survey the different definitions of centrality measures and the algorithms to compute them. We start from the most common measures (e.g., closeness centrality, betweenness centrality) and move to more complex ones, like spanning-edge centrality. In our presentation, we begin from exact algorithms and then move to approximation algorithms, including sampling-based ones, and to highly-scalable MapReduce algorithms for huge graphs, both for exact computation and for keeping the measures up-to-date on dynamic graphs where edges are inserted or deleted over time.

Our goal is to show how advanced algorithmic techniques and scalable systems can be used to obtain efficient algorithms for important graph mining tasks, and to encourage research in the area by highlighting open problems and possible directions.

More details on the material we will cover are available in the 4-pages outline.

Slides

Here are our slides (updated: Dec 30 2018).

Instructors

Francesco Bonchi

Francesco is Research Leader at the ISI Foundation, Turin, Italy, where he leads the "Algorithmic Data Analytics" group. Before he was Director of Research at Yahoo Labs in Barcelona, Spain, leading the Web Mining Research group. His recent research interests include mining query-logs, social networks, and social media, as well as the privacy issues related to mining these kinds of sensible data.

He will be PC Chair of the 16th IEEE International Conference on Data Mining (ICDM 2016) to be held in Barcelona in December 2016. He is member of the ECML PKDD Steering Committee, Associate Editor of the newly created IEEE Transactions on Big Data (TBD), of the IEEE Transactions on Knowledge and Data Engineering (TKDE), the ACM Transactions on Intelligent Systems and Technology (TIST), Knowledge and Information Systems (KAIS), and member of the Editorial Board of Data Mining and Knowledge Discovery (DMKD). He earned his Ph.D. in computer science from the University of Pisa in December 2003.

Twitter: @FrancescoBonchi

Gianmarco De Francisci Morales

Gianmarco De Francisci Morales is a Scientist at QCRI. Previously he worked as a Visiting Scientist at Aalto University in Helsinki, as a Research Scientist at Yahoo Labs in Barcelona, and as a Research Associate at ISTI-CNR in Pisa. He received his Ph.D. in Computer Science and Engineering from the IMT Institute for Advanced Studies of Lucca in 2012. His research focuses on scalable data mining, with an emphasis on Web mining and data-intensive scalable computing systems. He is an active member of the open source community of the Apache Software Foundation, working on the Hadoop ecosystem, and a committer for the Apache Pig project. He is one of the lead developers of Apache SAMOA, an open-source platform for mining big data streams. He co-organizes the workshop series on Social News on the Web (SNOW), co-located with the WWW conference.

Twitter: @gdfm7

Matteo Riondato

Matteo is a Research Scientist in the Labs group at Two Sigma Investments and a Visiting Assistant Professor at Brown University. His dissertation on sampling-based randomized algorithms for data and graph mining received the Best Student Poster Award at SIAM SDM'14. His research focuses on exploiting advanced theory to develop practical algorithms for time series analysis, pattern mining, and social network analysis.

Twitter: @teorionda

Bibliography

A commented BibTeX bibliography with the most relevant references: centrality.bib (updated on Dec 30 2018)