An Evaluation of the use of Clustering Coefficient as a Heuristic for the Visualisation of Small World Graphs

Simple item page
dc.contributor.authorMcGee, Fintanen_US
dc.contributor.authorDingliana, Johnen_US
dc.contributor.editorJohn Collomosse and Ian Grimsteaden_US
dc.date.accessioned2014-01-31T20:11:59Z
dc.date.available2014-01-31T20:11:59Z
dc.date.issued2010en_US
dc.description.abstractMany graphs modelling 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. In order to make the graph more understandable, we suggest dividing it into clusters built around nodes of interest to the user. This paper describes a graph clustering using the average clustering coefficient as a heuristic for determining which node a vertex should be assigned to. We propose that the use of clustering coefficient as a heuristic aids in the formation of high quality clusters that consist of nodes that are conceptually related to each other. We evaluate the impact of using the clustering coefficient heuristic against other approaches. Once the clustering is performed we lay out the graph using a force directed approach for each clustering individually.en_US
dc.description.seriesinformationTheory and Practice of Computer Graphicsen_US
dc.identifier.isbn978-3-905673-75-3en_US
dc.identifier.urihttps://doi.org/10.2312/LocalChapterEvents/TPCG/TPCG10/167-174en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectCategories and Subject Descriptors (according to ACM CCS): G.2.2 [Graph Theory]: Graph AlgorithmsI.5.3 [Clustering]: AlgorithmsF.2.2 [ Nonnumerical Algorithms and Problems]: Routing and layouten_US
dc.titleAn Evaluation of the use of Clustering Coefficient as a Heuristic for the Visualisation of Small World Graphsen_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
167-174.pdf
Size:
617.53 KB
Format:
Adobe Portable Document Format
Download
Collections
EG UK Theory and Practice of Computer Graphics 2010