[HN Gopher] Handbook of Graph Drawing and Visualization (2013)
___________________________________________________________________
Handbook of Graph Drawing and Visualization (2013)
Author : mindcrime
Score : 252 points
Date : 2021-12-30 05:50 UTC (17 hours ago)
(HTM) web link (cs.brown.edu)
(TXT) w3m dump (cs.brown.edu)
| dexwiz wrote:
| I have gone through this book, and it's the best primer I have
| found for graph drawing. It covers a wide range of topics, but it
| is written for an audience with a working knowledge of graph
| theory. The book is more of a collection of academic papers than
| a singular How To guide. The problems are discussed in abstract,
| and concrete implementations aren't provided. You may need to go
| read other referenced papers at points.
|
| Unfortunately the most ubiquitous graph type, hierarchical
| graphs, are an NP hard problem. The chapter outlines the Sugiyama
| framework for breaking down the problem, but each step is still
| difficult. Expect to sit down with the chapter over several
| sessions before you will be able grok how to draw a useful graph.
| dmkolobov wrote:
| Oh man, spent way too long staring at the resources on this page
| once upon a time, when implementing a level-based algorithm for
| drawing trees:
|
| https://dmkolobov.github.io/tidy-trees-demo/
|
| Good stuff on this page, and the references are an invaluable
| collection of prior art.
| yesenadam wrote:
| Or get all chapters in one PDF from LibGen:
|
| https://libgen.rs/search.php?req=Handbook+of+Graph+Drawing+a...
| captn3m0 wrote:
| Or stitch one using pystitcher: wget
| https://www.toptal.com/developers/hastebin/raw/norurilawu &&
| pipx install pystitcher && pystitcher norurilawu output.pdf
| CelticBard wrote:
| Thanks, didn't even know stuff like this existed
| lelanthran wrote:
| Thanks.
| nsajko wrote:
| Graphia is nice for interactive 3D visualizations of even large
| graphs.
|
| https://github.com/graphia-app/graphia
|
| https://graphia.app
| syntaxfree wrote:
| If you have extra information about vertices you can use it to
| generate coordinates. Also: you can always augment coordinate
| proposals with something like the Louvain community detection
| algorithms at different resolutions and then MDS or UMAP etc.
| happylion0801 wrote:
| > If you have extra information about vertices you can use it
| to generate coordinates
|
| Could you expand on this with an example. Or is there a
| reference or algo that I could look at. What do you mean by
| having extra info to generate coordinates. I am currently
| looking into graph drawing algorithms for a network viz problem
| and part of it involves placing nodes in certain places and I
| am interested to see if what you are saying is something I
| could use
| lmeyerov wrote:
| See the above example notebook
|
| If node or edge attribute information is useful for
| clustering, such as not just account IDs but say entity or
| event sizes & time, you may want to see sub-cluster
| separation based on that. A naive initial UMAP approach (I
| think the OP's intuition) is to ignore your graph structure
| and run UMAP (or t-SNE, PCA, k-means, ...) on your
| independent entities. No graph data involved (initially).
| Then you will get a scatterplot of entities where those with
| similar values across their features are near each other. The
| notebook I linked shows how to compute the UMAP on such a
| table. Then, instead of showing a scatter plot, you can then
| draw edges between neighboring entities and play with it:
| it's an entity similarity graph! That's the more interesting
| part of the notebook, and a big step up over how we see most
| UMAP workflows go.
|
| However, it sounds like you already have a graph, which is
| more structure for clustering than out-of-the-box UMAP (PCA,
| ...) leverages. When you also have a graph of edges between
| those entities, such as causal events, and maybe even
| weights, you can also combine the similarity graph + yours,
| and run the graph clustering on the combined result. The
| clustering would then use both the node feature similarity
| and your existing graph knowledge. The UMAP similarity edges
| are likely more correlative & speculative than your physical
| graph's edges, so when running graph clustering, it often
| helps to assign different edge weights based on your
| confidence in each edge.
|
| There are more tricks you can play here. A big one for
| property graphs is propagating node/edge features to nearby
| nodes (ex: "total connected bytes/events/$/etc.") so that the
| UMAP has surrounding graph information available. This starts
| to generalize to graph neural nets (b/c you're doing label
| propagation), and something we're actively looking into and
| are happy to chat w/ folks about: feel free to email or swing
| by our Slack :)
| lmeyerov wrote:
| This! We do it all the time in fraud, genomics, social media,
| security, etc data tables, it is one of our favorite
| techniques.
|
| We do one more step for UMAP and other dimensionality reducers
| in practice: connect the nearest neighbors to turn any data
| table into an explorable similarity graph. Users, devices,
| proteins, accounts, events, etc link together and cluster when
| similar, and this reveals fascinating structural relationships
| when there is a reason they vary.
|
| Takes just a few lines once you have a feature table, and
| there's a recent GH issue to automate that step too:
| https://github.com/graphistry/pygraphistry/blob/master/demos...
| ng55QPSK wrote:
| any plotting library that implements this?
| alok-g wrote:
| Check out Gephi and Cytoscape.
|
| https://gephi.org
|
| https://cytoscape.org
| tunesmith wrote:
| Cytoscapejs works pretty well for me as a react component, I
| use it to draw elk graphs, which is apparently a step up from
| sugiyama (graphviz).
|
| There's also dagre-d3 which uses sugiyama. I have a different
| react project that uses that. I think I like cytoscapejs
| better, although the animated transitions from graph state to
| graph state are a bit clunkier.
|
| I'm not aware of anything better for open source web that
| allows you to edit/animate, but I haven't tried
| gephi/graphology/sigma.js.
| sanxiyn wrote:
| MSAGL has a good implementation.
| ng55QPSK wrote:
| Microsoft Automatic Graph Layout?
| sanxiyn wrote:
| Yes.
| le-mark wrote:
| Venerable Graphviz has the main ones.
| ygra wrote:
| yFiles as well. In fact, parts of the book have been written by
| people involved in the early development of yFiles. I'm sure
| the dead tree variant of that book sits somewhere in a shelf in
| the office.
| pbowyer wrote:
| I remember yEd from university 2 decades ago so got excited
| by the idea of yFiles. Until I calculated [1] the license
| price - for a single developer on a single project it'd be
| $14000+$4200 maintenance. Wow.
|
| 1. https://www.yworks.com/products/yfiles-for-
| html/pricing/#/co...
| lmeyerov wrote:
| Graphistry has a free tier, GPU stuff included :)
| scoopertrooper wrote:
| It was a different time...
|
| _Page 807 (social networks)_
|
| Key to sociograms:
|
| Girl, Boy
|
| Colored Girl, Colored Boy
|
| Housemother or instructor, Male instructor
| shanamendez wrote:
| lmeyerov wrote:
| Roberto is fun! I didn't appreciate his work until way later =/
|
| Funny enough, if someone is into modern versions of these graph
| techniques, we have been building out an end-to-end GPU visual
| graph intelligence platform used by all sorts of
| security/fraud/misinfo/genomics/supply chain teams, and have 2
| data viz openings precisely on this: fullstack data viz + WebGL
| engine. Info over at https://www.graphistry.com/careers .
|
| Once you load in say 100K-1B fraud events or cancer proteins and
| try to make the experience fully interactive, GPUs are letting us
| tackle all sorts of challenges that were unrealistic back then.
| With all graph neural net stuff happening in the last ~2 years,
| our assumptions of what tools can enable analysts to tease out
| are changing yet again. Exciting days!
| kowlo wrote:
| I wouldn't call this Roberto's work... unless you're referring
| to something else?
| lmeyerov wrote:
| He is the editor (see line 2). For his direct research here,
| he wrote many papers on computational geometry / graphs - his
| dblp is quite long!
| meimo wrote:
| Great stuff, well done.
| babbledabbler wrote:
| Thank you for sharing. What an amazing time to be alive and have
| access to all the world's information.
___________________________________________________________________
(page generated 2021-12-30 23:01 UTC)