VISUALISING SMALL WORLD GRAPHS - Agglomerative Clustering of Small World Graphs around Nodes of Interest

Fintan McGee, John Dingliana

2012

Abstract

Many graphs which model real-world systems are characterised by a high edge density and the small world properties of a low diameter and a high clustering coefficient. In the ”small world” class of graphs, the connectivity of nodes follows a power-law distribution with some nodes of high degree acting as hubs. While current layout algorithms are capable of displaying two dimensional node-link visualisations of large data sets, the results for dense small world graphs can be aesthetically unpleasant and difficult to read, due to the high level of clutter caused by graph edges. We propose an agglomerative clustering which allows the user to select nodes of interest to form the basis of clusters, using a heuristic to determine which cluster each node belongs to. We have tested three heuristics, based on existing graph metrics, on small world graphs of varying size and density. Our results indicate that maximising the average cluster clustering coefficient produces clusters that score well on modularity while consisting of a set of strongly related nodes. We also provide a comparison between our clustering coefficient heuristic agglomerative approach and Newman and Girvan’s top-down Edge Betweenness Centrality clustering algorithm.

Paper Citation

in Harvard Style

McGee F. and Dingliana J. (2012). VISUALISING SMALL WORLD GRAPHS - Agglomerative Clustering of Small World Graphs around Nodes of Interest . In Proceedings of the International Conference on Computer Graphics Theory and Applications and International Conference on Information Visualization Theory and Applications - Volume 1: IVAPP, (VISIGRAPP 2012) ISBN 978-989-8565-02-0, pages 678-689. DOI: 10.5220/0003864306780689

in Bibtex Style

@conference{ivapp12,
author={Fintan McGee and John Dingliana},
title={VISUALISING SMALL WORLD GRAPHS - Agglomerative Clustering of Small World Graphs around Nodes of Interest},
booktitle={Proceedings of the International Conference on Computer Graphics Theory and Applications and International Conference on Information Visualization Theory and Applications - Volume 1: IVAPP, (VISIGRAPP 2012)},
year={2012},
pages={678-689},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003864306780689},
isbn={978-989-8565-02-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Computer Graphics Theory and Applications and International Conference on Information Visualization Theory and Applications - Volume 1: IVAPP, (VISIGRAPP 2012)
TI - VISUALISING SMALL WORLD GRAPHS - Agglomerative Clustering of Small World Graphs around Nodes of Interest
SN - 978-989-8565-02-0
AU - McGee F.
AU - Dingliana J.
PY - 2012
SP - 678
EP - 689
DO - 10.5220/0003864306780689