I originally left off a description because NetworkX is the library for doing graph things in Python and I kind of assumed people would know. While it's not the most performant or cutting edge, it's so well-established that everyone else aims for interface compatibility with it, much like pandas and tabular data.
It's pretty neat that they've decided to leverage this by opening up the backend, allowing more performant/application specific offerings like SNAP or CUgraph to do the heavy lifting.
This is not the same thing. Hacker News as a website is catered to an audience that is mostly familiar with programming. I would say it's safe to assume for any given visitor that they are probably aware of basic computing and programming terminology, but not that they would know what "NetworkX" means.
The new title is fitting (it specifies what it's a Python library now).
Igraph and graph tool might have something to retort to that. Up until this update, they were far far faster too (and still likely are if you ignore the ability in this update to specify different backends)
Yes. I noted that it's not the most performant, indeed it's famous for being slow. But it's so popular, has such extensive code coverage, and such a simple API that it's gained default status, not unlike how Python is the default language for data science despite its limitations.
I always used IGraph because there are both R and Python versions, and I learned R first. I never had any complaints about it for the baby-scale problems I used it for, so I never bothered to try NetworkX.
It was my go-to package in python, when I had to build graphs and ascertain acyclicity, single source, shortest path. They weren't huge graphs (at most 100s of elements), so networkx certainly did the work fast enough.
Good memories of this library when the professor for the course complex networks said you were allowed to use any existing libraries. That labwork, needless to say, was a walk in the park.
By the way if you want to explore network science but don't really know where to start, consider Gephi (currently being refactored, and just updated a few days ago) or Cytoscape (if you're more drawn to bioinformatics).
Both make it easy to load/generate standard datasets, import tabular data, and have a good selection of plugins. It's easy to kick stuff out to either from NetworkX using /gefx or graphml, and you'll be able to experiment with a wide variety of layout algorithms and metrics. If you don't find the toy/benchmark networks intuitive, considering hitting the HN API for your source material; it's a lot easier to grasp the topic by studying relationships that are already familiar.
I've had a lot of luck with Gephi for fairly complex graphs (~10000 nodes and edges), in particular it has some very powerful layout algorithms. It can be very helpful to have immediate visual feedback when untangling something like that. Nice to see that development is ongoing, the GUI used to feel a bit clunky but 0.10 seems a lot better!
Seconding this. Get Gephi, install as many plugins as possible, and dig into the plugin pages to find the underlying papers. Also true for Cytoscape, but that tool focuses a little more on connectivity to bio databases and extremely specific stuff like proteomics.
Do you have any advice/ideas about ways to learn about graph layout algorithms themselves, including dynamic/real-time algorithms (which allow for user interaction)? I have been skimming through various papers and the first book on this page [0], in particular the chapter on force directed algorithms, because they seem to be the earliest and most general graph drawing methods.
You mean algos related only to NetworkX or in general? If you are looking for NetworkX related stuff besides the official docs, NetworkX Guide [1] is a good starting point.
Maybe this will be interesting to you. An open source graph visualization library called Orb.[1] There is a series of blog post that talk about the development and reasoning behind this library. [2]
It's kind of a mysterious art, and I too mostly rely on scientific papers. It's a surprisingly small field and you need to get into the habit of chasing down citations in papers, because many important ideas got laid out long before the computer power existed to realize them at scale. Sometimes a 20-30 year old paper of only a few pages has the actual algorithm, and it's so well known in the field that it no longer stands out in more recent papers.
A gallery of large graphs - horrid user interface, but you can click through and find an absolute wealth of resources. Curated by Yifan Hu, who developed one of the popular layout algorithms: http://yifanhu.net/GALLERY/GRAPHS/
Graphviz is a very well-documented library with a lot of the 'classic' layouts.
Astronomy, physics, and bio people have a lot of useful visualization tools and techniques for huge datasets, but you will have to go looking for them - not because they don't like to share, but because they mostly write to each other so you won't just land on stuff by browsing Github. Absolute must-have literature review: https://arxiv.org/abs/2110.01866
A lot of large graph visualization techniques are about using simple graph visualization techniques but first combing out the hairballs through the application of dimensionality reduction, motif extraction, backbone identification and so on. This is an important paper whose techniques have yet to be fully explored: https://jgaa.info/accepted/2015/NocajOrtmannBrandes2015.19.2...
For a combination of theoretical and practical reasons, most visualization zeroes in on rendering smallish graphs in 2 dimensions. Large graphs are either so densely connected as to be be intractable (the brain being the ultimate hairball) or so sparse as be like digital planetariums - gorgeous, impressive, and looking much the same in every direction.
I could go on at length but as you can maybe guess I'm a consumer of other people's research rather than an expert in implementing the fundamentals. Also I don't have any academic background whatsoever so I apologize for the haphazard infodump. I've been studying/applying stuff from this field for ~15 years but it's too out there for most people. Feel free to email though.
I'm not an innovator in this space. I'm interested in swarm dynamics as manifested in structures of information exchange (like conversations) and the extent to which these have inherent structures that could be described by Lindenmeyer systems.
In 30 years this is truly the first time anyone said "well-documented". "Very well documented." Yes. Actually a lot of credit goes to the inheritors of this project (Magnus Jacobsson, Matthew Fernandez, Mark Hansen, and a boost from Steve Roush and Costa Shulyupin) for bringing some sense of order and self-respect.
It's thrilling someone else noticed the Nocaj et al. Simmelian backbone paper. There is a directory somewhere on this computer of an implementation in graphviz that Emden Gansner wrote a couple of years ago. (It should at least be uploaded to graphviz gitlab so we don't ever lose it.) All we need now is a summer intern to finish the job. Sometimes it's natural to miss Bell Labs and even AT&T Labs a whole lot.
wow, great to see that networkx keeps evolving. the graphblas backend is particularly intriguing. does networkx expose the graphblas API at the python level or is it working behind the scenes for computation?
NetworkX is my go-to library for helping people get started with open source (like mentoring new devs that want git practice, practice working in a large codebase, etc.). I feel it is laid out in an easy to understand way and all the main parts do one clear thing that can be understood even with only a basic knowledge of graph theory. It also hits the sweet spot of being an obviously useful and widely used package, but without the army of devs working on it, so there is still a lot of low-hanging fruit for tangible contributions.
I compare it to something like Django or scikit-learn, which seem insanely dense and difficult to understand even as an experienced dev, and there are so many people working on them that it's hard to find easy but non-trivial contributions for a beginner to make.
Do you have any recommendations on how to get started? I have been using open source for around 10 years and always wanted to contribute. I am a confident python scripter and have used NetworkX in the past for various academic projects, however I have no idea how to get started as a beginner dev and contribute to open issues and bugs. Heck, I don't even know how large codebases are structured! Any hints or recommendation are welcome! :D
If projects have a "good first issue" tag, they can sometimes be a good place to start. The problem is they are mostly "add tests" or "expand docs", which are important but not very exciting.
Imo the best thing is to have a mentor who hopefully can find a reasonable thing to improve/add/fix and can help calm your nerves (submitting a pull request can be kinda scary haha). With NetworkX, in the past there were a lot of minor inefficiencies (things like materializing a list comprehension when you don't need to, etc) that are 1) easy to understand 2) don't require in depth knowledge of graph theory 3) are generally applicable to all python code and 4) easy to measure the results. They aren't the flashiest contributions, but the people I've done it with (6 or 7 at this point) have all seemed to enjoy it.
To be clear, I'm _not_ affiliated with NetworkX, but if you are interested in trying it out, my contact info is in my profile. Feel free to reach out.
I use NetworkX rather unusually to parse Graphviz dot specification files in my devops pipeline tool, mazzle.
They allow me to define infrastructure build instructions as a dot file that looks similar to this. It's similar to an advanced makefile.
This segment of the infrastructure specification sets a dependency on the bastion box, the vault AMI (Amazon Machine Image) and web server provisioned by terraform on the source AMI. Then it sets a dependency of uploading nodejs to the repository server and a dependency on dpkg scan packages. It also tells machines to join themselves to a Kubernetes cluster.
Nice I like the concept of turning around Graphviz dot files and turning them from an intermediate representation of visualization into the actual source of truth for the system. Cool idea.
For my telco job, I whipped up a shortest path routing proof of concept using NetworkX in a couple hours, right after stumbling on it, with my rudimentary Python scripting skills. The sort of extremely productive library that makes one feel heroic !
Can someone comment on the user experience of NetworkX vs comparable packages like igraph? I've used Graphs.jl (formerly LightGraphs.jl) and I was unimpressed as it felt quite cumbersome and unintuitive.
I just started using NetworkX a few days ago and was trying to figure out a way to find all paths in a DAG from a source node to a destination node, with the requirement that no path is a superpath of any other path.
I ended up writing my own approach that iterates through all pairs of paths but have been bothered since then that I couldn’t find a function in NetworkX to do this; I’m sure it probably exists but I don’t know the right terminology to search for it. Anyone know what this function might be called?
I am trying to imagine how it is even possible for this to happen in a DAG. One path from A to B cannot be a strict subset of another (because this implies a cycle) - I unless you mean something else by "superpath".
If you have paths [A-B-C-Z, A-B-Z, A-D-Z], path A-B-C-Z would be eliminated from that set since it is a superpath of A-B-Z. Is my terminology incorrect?
Is it now finally faster than GraphLab? Couple years ago when I last used them, there were some operations like PageRank that was magnitudes faster with GraphLab. Hope they have caught up now. GraphLab has been deprecated for a long while now. Curious did or will they ever make it open-source.
NetworkX(pure python with dict as the data structure) itself will never be faster than any C++ based library (I think GraphLab doesn't even exist now?) but with the new experimental backend plugins, you should be able to use NetworkX API and dispatch the computation to more efficient backends like GraphBLAS, and hopefully CuGraph in the future (if you have GPUs). A bit more info: https://twitter.com/networkx_team/status/1612478129649459202
Taking a broad view of the area, it's interesting that tables and networks are both fundamental ways of representing data in many situation, and often complementary, but the technology for working with tables is far more mature. This spans the low end of representation (CSV files, data frames in pandas) to database systems that provide essential capabilities like query languages and consistency checking, to entire application platforms like Oracle. The equivalent systems for networks aren't as mature. There's still a big opportunity to meet this need, and you can see a lot of progress in technology like NetworkX and Neo4J.
A great service that network programming systems provide, as highlighted in some of the comments here, is simply to provide a framework for integrating useful functions for operating or computing on networks so they can be delivered to a broad audience. To illustrate, in the land of tables, if I need to join two tables, and count rows or sort and show the top-N, I know what software on my computer does that. If I have a network and want to find a shortest path or do some other simple pattern matching on paths, and maybe show the result graphically, what am I supposed to use? It's really not clear.
And, in 2023, why not both? Applications need both tabular and network views of data, and in some ways they are not that different. That the popular relational data platforms have not already rushed in to fill this need give some reason to pause and consider the situation further or maybe is an argument that tables and networks should have similar importance.
From real life, maybe one issue is that the technology for computing on tables is pretty well understood and manageable, but there are a lot of sharp edges around combinatorial structures like networks. From a recent real-life example, say I just want to make an attributed network representing employees in a company, and match them for an internal project. Is this as easy as sorting rows in a table? Hardly. Can you even find a textbook pseudocode algorithm and code it in a graph query language that is recognizable as that algorithm? These look like tough problems. At least NetworkX and systems like it provide a framework to integrate those implementation for a developer audience.
I've used networkx as an intermediate graph layer in web apps before talking to a db, which seemed redundant, except being able to reason about my data as a graph was everything I needed.
NetworkX documentation is the source of one of my favourite surreal sentences: A lobster is a tree that reduces to a caterpillar when pruning all leaves. [0, with a tiny alteration]
57 comments
[ 0.23 ms ] story [ 111 ms ] threadAt some point it might really start to be more efficient to have tags for the posts
I originally left off a description because NetworkX is the library for doing graph things in Python and I kind of assumed people would know. While it's not the most performant or cutting edge, it's so well-established that everyone else aims for interface compatibility with it, much like pandas and tabular data.
It's pretty neat that they've decided to leverage this by opening up the backend, allowing more performant/application specific offerings like SNAP or CUgraph to do the heavy lifting.
Not everyone writes Python, and not all Python programmers have heard of this particular library.
The new title is fitting (it specifies what it's a Python library now).
Igraph and graph tool might have something to retort to that. Up until this update, they were far far faster too (and still likely are if you ignore the ability in this update to specify different backends)
Both make it easy to load/generate standard datasets, import tabular data, and have a good selection of plugins. It's easy to kick stuff out to either from NetworkX using /gefx or graphml, and you'll be able to experiment with a wide variety of layout algorithms and metrics. If you don't find the toy/benchmark networks intuitive, considering hitting the HN API for your source material; it's a lot easier to grasp the topic by studying relationships that are already familiar.
[0] http://graphdrawing.org/books.html
[1] https://networkx.guide/
[1] https://github.com/memgraph/orb
[2] https://memgraph.com/blog?topics=Orb#list
Here's a few useful references:
Good overview on big graphs: https://towardsdatascience.com/large-graph-visualization-too...
A gallery of large graphs - horrid user interface, but you can click through and find an absolute wealth of resources. Curated by Yifan Hu, who developed one of the popular layout algorithms: http://yifanhu.net/GALLERY/GRAPHS/
Graphviz is a very well-documented library with a lot of the 'classic' layouts.
Astronomy, physics, and bio people have a lot of useful visualization tools and techniques for huge datasets, but you will have to go looking for them - not because they don't like to share, but because they mostly write to each other so you won't just land on stuff by browsing Github. Absolute must-have literature review: https://arxiv.org/abs/2110.01866
A lot of large graph visualization techniques are about using simple graph visualization techniques but first combing out the hairballs through the application of dimensionality reduction, motif extraction, backbone identification and so on. This is an important paper whose techniques have yet to be fully explored: https://jgaa.info/accepted/2015/NocajOrtmannBrandes2015.19.2...
For a combination of theoretical and practical reasons, most visualization zeroes in on rendering smallish graphs in 2 dimensions. Large graphs are either so densely connected as to be be intractable (the brain being the ultimate hairball) or so sparse as be like digital planetariums - gorgeous, impressive, and looking much the same in every direction.
I could go on at length but as you can maybe guess I'm a consumer of other people's research rather than an expert in implementing the fundamentals. Also I don't have any academic background whatsoever so I apologize for the haphazard infodump. I've been studying/applying stuff from this field for ~15 years but it's too out there for most people. Feel free to email though.
Would you mind elaborating on the work you do with graph visualisation?
Thank you for the offer, I'll certainly contact you after I familiarise myself with some more classic research material.
It's thrilling someone else noticed the Nocaj et al. Simmelian backbone paper. There is a directory somewhere on this computer of an implementation in graphviz that Emden Gansner wrote a couple of years ago. (It should at least be uploaded to graphviz gitlab so we don't ever lose it.) All we need now is a summer intern to finish the job. Sometimes it's natural to miss Bell Labs and even AT&T Labs a whole lot.
If you want the graphblas API in python, https://github.com/python-graphblas/python-graphblas/ is the right place :)
[0] https://adventofcode.com
I compare it to something like Django or scikit-learn, which seem insanely dense and difficult to understand even as an experienced dev, and there are so many people working on them that it's hard to find easy but non-trivial contributions for a beginner to make.
Imo the best thing is to have a mentor who hopefully can find a reasonable thing to improve/add/fix and can help calm your nerves (submitting a pull request can be kinda scary haha). With NetworkX, in the past there were a lot of minor inefficiencies (things like materializing a list comprehension when you don't need to, etc) that are 1) easy to understand 2) don't require in depth knowledge of graph theory 3) are generally applicable to all python code and 4) easy to measure the results. They aren't the flashiest contributions, but the people I've done it with (6 or 7 at this point) have all seemed to enjoy it.
To be clear, I'm _not_ affiliated with NetworkX, but if you are interested in trying it out, my contact info is in my profile. Feel free to reach out.
We also have some structured projects https://networkx.org/documentation/latest/developer/projects... but they are usually for programs like GSoC/Outreachy.
Feel free to start a discussion https://github.com/networkx/networkx/discussions if you are looking for something specific :)
[I am one of the NetworkX devs]
https://github.com/networkx/networkx/pull/6000
They allow me to define infrastructure build instructions as a dot file that looks similar to this. It's similar to an advanced makefile.
This segment of the infrastructure specification sets a dependency on the bastion box, the vault AMI (Amazon Machine Image) and web server provisioned by terraform on the source AMI. Then it sets a dependency of uploading nodejs to the repository server and a dependency on dpkg scan packages. It also tells machines to join themselves to a Kubernetes cluster.
Graph formats are really flexible and compact and I would like to see them used for more things.A topological search solves many problems.
https://devops-pipeline.com/
So if there's two packer builds that do not depend on eachother, they can run in parallel since they are slow.
https://github.com/samsquire/devops-schedule https://github.com/samsquire/parallel-workers
I ended up writing my own approach that iterates through all pairs of paths but have been bothered since then that I couldn’t find a function in NetworkX to do this; I’m sure it probably exists but I don’t know the right terminology to search for it. Anyone know what this function might be called?
If there is another method I'd like to hear about it.
NetworkX(pure python with dict as the data structure) itself will never be faster than any C++ based library (I think GraphLab doesn't even exist now?) but with the new experimental backend plugins, you should be able to use NetworkX API and dispatch the computation to more efficient backends like GraphBLAS, and hopefully CuGraph in the future (if you have GPUs). A bit more info: https://twitter.com/networkx_team/status/1612478129649459202
A great service that network programming systems provide, as highlighted in some of the comments here, is simply to provide a framework for integrating useful functions for operating or computing on networks so they can be delivered to a broad audience. To illustrate, in the land of tables, if I need to join two tables, and count rows or sort and show the top-N, I know what software on my computer does that. If I have a network and want to find a shortest path or do some other simple pattern matching on paths, and maybe show the result graphically, what am I supposed to use? It's really not clear.
And, in 2023, why not both? Applications need both tabular and network views of data, and in some ways they are not that different. That the popular relational data platforms have not already rushed in to fill this need give some reason to pause and consider the situation further or maybe is an argument that tables and networks should have similar importance.
From real life, maybe one issue is that the technology for computing on tables is pretty well understood and manageable, but there are a lot of sharp edges around combinatorial structures like networks. From a recent real-life example, say I just want to make an attributed network representing employees in a company, and match them for an internal project. Is this as easy as sorting rows in a table? Hardly. Can you even find a textbook pseudocode algorithm and code it in a graph query language that is recognizable as that algorithm? These look like tough problems. At least NetworkX and systems like it provide a framework to integrate those implementation for a developer audience.
It shows how to use the feature, some benchmarks, and how other graph libraries can become plugins to the NetworkX dispatching mechanism.
This slide shows some speedups when using the GraphBLAS [1] backend [2]:
https://i.postimg.cc/mr3mkKtx/100x-Faster-Network-X.png
[1] https://github.com/python-graphblas/python-graphblas
[2] https://github.com/python-graphblas/graphblas-algorithms
[0] https://networkx.org/documentation/stable/reference/generate...