Clustered graph, visualization, hierarchical visualization
- 1. Clustered graph, visualization, hierarchical visualization Nathalie Villa-Vialaneix http://www.nathalievilla.org SAMM (Universit辿 Paris 1) 2012/02/21 - Dagstuhl seminar 12081 Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 1 / 4
- 2. Full vs simpli鍖ed visualization Framework: Static graph visualization. Standard (FDP) approach: visualize the whole graph aims at being aesthetic tends to place the hubs in the center of the 鍖gure (edges with uniform length); does not emphasize dense groups Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 2 / 4
- 3. Full vs simpli鍖ed visualization Framework: Static graph visualization. Simpli鍖ed approach: 鍖nd communities and represent each one by a glyph Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 2 / 4
- 4. Full vs simpli鍖ed visualization Framework: Static graph visualization. Simpli鍖ed approach: 鍖nd communities and represent each one by a glyph and investigate sub-structure by a hierarchical clustering Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 2 / 4
- 5. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 6. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) Is the clustering relevant / signi鍖cant? Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 7. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) Is the clustering relevant / signi鍖cant? Possible answer: generate N random graphs with the same degree distribution and compare the observed optimal modularity to the optimal modularity distribution among the N random graphs Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 8. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) 2 Iterate the clustering in each class in a hierarchical way. When to stop the process? Is the clustering relevant / signi鍖cant? Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 9. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) 2 Iterate the clustering in each class in a hierarchical way. 3 Visualize the graph (in a simpli鍖ed way) at various levels of the clustering hierarchy. Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 10. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) 2 Iterate the clustering in each class in a hierarchical way. 3 Visualize the graph (in a simpli鍖ed way) at various levels of the clustering hierarchy. How to have consistent representations? (a cluster and its subclusters are approximately displayed at the same place) How to take into account the space needed for a cluster of the last level of the hierarchy in any representation (at any level)? Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 11. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) 2 Iterate the clustering in each class in a hierarchical way. 3 Visualize the graph (in a simpli鍖ed way) at various levels of the clustering hierarchy. How to have consistent representations? (a cluster and its subclusters are approximately displayed at the same place) How to take into account the space needed for a cluster of the last level of the hierarchy in any representation (at any level)? Possible solution: Recursively estimate the place needed for each cluster in the hierarchy (by a circle encompassing the visualization of all sub-clusters) over-estimation Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 12. Basic description 1 Search for communities: node clustering (e.g., modularity optimization) 2 Iterate the clustering in each class in a hierarchical way. 3 Visualize the graph (in a simpli鍖ed way) at various levels of the clustering hierarchy. Include information about the quality of the clustering in the representation? (user warning) Example: Color and weight edges between clusters according to their contribution to the modularity Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 3 / 4
- 13. Open issues Clustering: what is a meaningful clustering? When to stop the hierarchy? Clustering hierarchy representation: how to anticipate, at a given level, the place needed for the representation of the 鍖nest levels? Including estimation about the clustering quality in the representation: at the node level (quality of the clustering for the cluster? What does that mean?) or at the edge level (contribution to the modularity between clusters?) Dagstuhl Seminar 12081 (2012/02/21) Graph visualization & clustering Nathalie Villa-Vialaneix 4 / 4