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.
DownloadPaper 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