WSDM 2013 Tutorial

February 4-8, 2013 | Rome, Italy

Advanced Graph Mining for Community Evaluation in Social Networks and the Web

Christos Giatsidis, École Polytechnique, France

Fragkiskos D. Malliaros, École Polytechnique, France

Michalis Vazirgiannis, AUEB, Greece and École Polytechnique, France

Tutorial Description

Graphs (or networks) appear in several diverse domains, including sociology, biology, neuroscience and information management. An interesting feature of real networks is the clustering or community structure property, i.e., the structure is based into a modular organization; nodes within the same module (cluster or community) tend to be highly similar sharing common features, while on the other hand, nodes of different modules show low similarity. Typically, the communities correspond to densely connected groups of nodes, where the number of edges within a community is much higher than the number of edges across different communities.

Detecting and evaluating the community structure of real-world graphs constitutes an essential task in the area of graph mining and social network analysis. For example, in the link structure of the Web, communities correspond to groups of web pages that share common topics, and therefore, revealing the underlying community structure is a crucial application from a web search engine perspective. Similarly, communities in a social network (e.g., Facebook, Twitter) correspond to individuals with increased social ties (e.g., friendship relationships, common interests). Broadly speaking, community discovery and evaluation can contribute in our understanding of a social system, summarizing the interactions within the system in a concise manner.

The goal of the tutorial is to present community detection and evaluation techniques as mining tools for social networks and the Web. More precisely, the following key topics are covered by the tutorial: (i) Introduction and preliminaries on graphs and graph mining - social network analysis; (ii) topics in graph clustering and community detection; (iii) clustering and community detection in directed graphs; (iv) alternative methods for community evaluation.


Tutorial Outline

Target Audience

The target audience includes:

No special prerequisites apart from a standard background in algorithms and computer science.

About the Instructors

Christos Giatsidis is currently a Ph.D. candidate in the Computer Science Laboratory at École Polytechnique in France, working under the supervision of Prof. Michalis Vazirgiannis. He received his Diploma from the Athens Univ. of Economics & Business, Greece in 2009. He has published five referred articles in international journals and in proceedings of international conferences in the areas of data/web mining and social network analysis venues. His research interests include data/graph mining and algorithms for data management.

Fragkiskos D. Malliaros is currently a Ph.D. candidate in the Computer Science Laboratory at École Polytechnique in France, working under the supervision of Prof. Michalis Vazirgiannis. He received his Diploma and his M.Sc. degree from the Computer Engineering and Informatics Department of the University of Patras, Greece in 2009 and 2011 respectively. He is the recipient of the 2012 Google European Doctoral Fellowship in Graph Mining. Moreover, he has published two referred articles in international data mining and social network analysis venues. His research interests span the broad areas of data mining, algorithmic data analysis and data management, with focus on mining and analysis of large, time-evolving graphs.

Michalis Vazirgiannis is a Professor in the area of "Databases & Information Systems" at Athens University of Economics and Business with a part time affiliation at LIX/École Polytechnique, France. He has also been a visiting professor in Deusto Univ (Spain) (2006-2009), and in LIX at École Polytechnique, France where he is teaching the data base course. He has worked as a researcher in the different places: in the Knowledge & DB Lab (group, N.T.U. Athens), in GMD-IPSI (currently Frauhofer - IPSI), Germany, in Fern-Universitaet Hagen, in project VERSO (later GEMO) in INRIA/Paris, in IBM India Research Laboratory and in Max Planck Instistut fur Informatik (Saarbruecken, Germany). M. Vazirgiannis held a Marie Curie Intra-European fellow (2006-2007)in area of "P2P Web Search", hosted by INRIA FUTURS in Orsay, Paris. His current research interests are on a. Web/Social graphs analysis & evolution monitoring b. Computational Advertising c. Web Personalization d. Web Archiving (entity recognition, entity based retrieval) and e. data integration and data cleaning. His industrial experience and expertise lie in the areas of data mining and machine learning for large scale data repositories (i.e. the Web graph, social networks, medical data etc.). He has contributed chapters in books and encyclopedias, published two international books and more than a hundred twenty papers in international refereed journals and conferences. He is also co-author of two patents filed in the Greek patent office and one in the European Patent office. He has supervised ten completed PhD theses while currently he supervises five more PhD Students. Dr Vazirgiannis has founded the DB-NET Research group (in AUEB/Athens) focusing in the area of data and web mining. DB-NET participated in international research projects. Dr. Vazirgiannis has participated in more than forty programme committees of international conferences in the areas: Data Bases, Data/Web Mining and Machine learning and. Recently he served as - the Data Mining Track chair of the IEEE-ICDE 2011 conference. Programme co-Chair of the ECML/PKDD 2011 Conference in Athens, Greece. He participates in the editorial board of the Intelligent Data Analysis Journal (IOS press) and as Guest editor for the ECML PKDD 2011 special issue for the "Machine Learning" and "DMKD" journals.