Presenters:  Michalis Vazirgiannis, École Polytechnique, France & AUEB, Greece.
Christos Giatsidis,  École Polytechnique, France.
Fragkiskos D. Malliaros,  École Polytechnique, France

Graphs (or networks) constitute a dominant data structure and appear essentially in all forms of information. Examples include the Web graph, numerous social networks, collaborations networks, term dependency graphs and citation networks. The main features of these graphs are their huge volume and rate of change. Presumably, there is important hidden knowledge in the macroscopic topology and features of these graphs. A cornerstone issue here is the detection and evaluation of communities – bearing multiple and diverse semantics. Typically, the communities correspond to groups of nodes, where nodes within the same community (or clusters) tend to be highly similar sharing common features, while on the other hand, nodes of different communities show low similarity. ?Detecting and evaluating the community structure of real-world graphs constitutes an essential task in the areas of web and 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 proposed tutorial is to present community detection and evaluation techniques as mining tools for the Web and social networks. The tutorial commences by demonstrating the importance of graph mining and social network analysis tools, as well as the significance of community detection and evaluation as tasks that lie in the core of graph and web mining. Afterwards, we present fundamental graph concepts and models for undirected, directed and signed graphs along with their properties. The tutorial continues with a thorough review of graph clustering and community detection methods, demonstrating their basic methodological principles. Then, we present how the community detection task can be treated in directed graphs, where the presence of directed edges conveys essential semantics. Furthermore, some topics on community evaluation measures are presented for both individual nodes, as well as aggregate metrics. Special mention is made to the degeneracy (k-cores and extensions) approach for community evaluation in directed and signed graphs, presenting also several case studies on real-world networks, such as co-authorship networks, citation networks, trust networks and the Web graph. Moreover, we present some alternative methods for community detection and evaluation based on recent observations about the structural properties of large scale real graphs, and we also discuss on some interesting research directions in the area.

Link to material: http://www.lix.polytechnique.fr/~mvazirg/WWW2013_tutorial/Tutorial_Slides_WWW_2013.pdf