February 4-8, 2013 | Rome, Italy
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.
Slides.pdf (~ 17MB)
Introduction
Graph fundamentals
Community evaluation measures
Graph clustering algorithms
Taxonomy
Spectral clustering
Modularity-based methods
Clustering and community detection in directed graphs
Challenges
Notions - Intuitive definitions of communities in directed graphs
Approaches for identifying communities in directed graphs
Alternative methods for community evaluation
Overlapping community detection
Global vs. local methods for community detection
Community detection from seed nodes
Observations on structural properties of large graphs
Degeneracy-based community evaluation
New directions for research in the area of graph mining for community evaluation
Researchers in the area of graph mining with applications to community detection/evaluation
Practitioners and members of industrial partners relevant to social networks and other disciplines that involve graph clusters detection and evaluation
No special prerequisites apart from a standard background in algorithms and computer science.
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.