ADAPTATION AND ENHANCEMENT OF EVALUATION MEASURES TO OVERLAPPING GRAPH CLUSTERINGS

Tatiana Gossen, Michael Kotzyba, Andreas Nürnberger

2012

Abstract

Quality measures are important to evaluate graph clustering algorithms by providing a means to assess the quality of a derived cluster structure. In this paper, we focus on overlapping graph structures, as many realworld networks have a structure of highly overlapping cohesive groups. We propose three methods to adapt existing crisp quality measures such that they can handle graph overlaps correctly, but also ensure that their properties for the evaluation of crisp graph clusterings are preserved when assessing a crisp cluster structure. We demonstrate our methods on such measures as Density, Newman’s modularity and Conductance. We also propose an enhancement of an existing modularity measure for networks with overlapping structure. The newly proposed measures are analysed using experiments on artificial graphs that possess overlapping structure. For this evaluation, we apply a graph generation model that creates clustered graphs with overlaps that are similar to real-world networks i.e. their node degree and cluster size distribution follow a power law.

Download


Paper Citation


in Harvard Style

Gossen T., Kotzyba M. and Nürnberger A. (2012). ADAPTATION AND ENHANCEMENT OF EVALUATION MEASURES TO OVERLAPPING GRAPH CLUSTERINGS . In Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-8425-98-0, pages 5-14. DOI: 10.5220/0003706400050014

in Bibtex Style

@conference{icpram12,
author={Tatiana Gossen and Michael Kotzyba and Andreas Nürnberger},
title={ADAPTATION AND ENHANCEMENT OF EVALUATION MEASURES TO OVERLAPPING GRAPH CLUSTERINGS},
booktitle={Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2012},
pages={5-14},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003706400050014},
isbn={978-989-8425-98-0},
}


in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - ADAPTATION AND ENHANCEMENT OF EVALUATION MEASURES TO OVERLAPPING GRAPH CLUSTERINGS
SN - 978-989-8425-98-0
AU - Gossen T.
AU - Kotzyba M.
AU - Nürnberger A.
PY - 2012
SP - 5
EP - 14
DO - 10.5220/0003706400050014