OBJECTIVE/DESCRIPTION:

The field of social network analysis is currently held back by an inability to quantitatively or qualitatively evaluate the results of community mining algorithms. Yet, in the meantime much progress has been made in evaluating results in the analogous field of clustering. A study of the existing clustering methods may provide valuable insights into the evaluation of communities.

This course will provide students with (1) an overview of the existing clustering algorithms, (2) an examination of the existing methods used when evaluating clusters, (3) a discussion of frameworks used to determine the correctness of the evaluation methods, (4) an introduction to the existing community mining algorithms, (5) and a survey of possible evaluation methods that can be drawn from clustering and used in community mining.

The course will consist of a series of discussions on the topics listed below from both a clustering and social network analysis view. In addition, recent relevant research papers will also be read and discussed.

The ultimate objective of the course is to write a paper about community mining evaluation to be submitted for peer review. The paper will be generated out of the individual final term papers, which may be covering different aspects of the material covered in class.

TOPICS:

• Definition of a cluster
• Types of clustering algorithms
• Metrics to qualitatively evaluate clustering
• Metrics to quantitatively evaluate clusters
• Existing and proposed frameworks to evaluate clusters
• Definition of a community
• Types of community mining algorithms
• Similarities between cluster and community discovery validation
Meaning of ethics

GRADING:

Students will have to make presentations and will be individually marked for their individual presentation and for their participation in the discussions. While the final outcome targeted in this course is a compilation of the students final reports, the individual student final reports, including the annotated bibliography, will be marked separately.

TEXTBOOK and REFERENCES:

A minimum of 10 research papers will be selected from a variety of journals, conference proceedings and other sources. Some examples seed papers:

• L. Vendramin, R. Campello, E. Hruschka, On the comparison of relative clustering validity criteria, Siam Data Mining conference (SDM) 2009, pp 733-744.
• R. Campello, Generalized external indexes for comparing data partitionins with overlapping categories, Pattern Recognition Letters, 31(9):966-975, 2010