Knowledge graphs are so under-utilised for practical things despite the fact that there is significant amount of useful research out there. Their problem is that they are expensive. I hope further research in ML would help elevate their relevance significantly. I am particularly fond of using knowledge graphs and graph theory for security related work.
A new algorithm for graph crossings, hiding in plain sight (2020)
11–20 of 44 posts
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#12Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of improved graph algorithms.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#13Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
I work with the researchers, and I think they'll be interested in knowing which version of the problem practitioners like yourself are most interested in. Do you ever add/remove edges, perhaps in bulk? Or do are you mostly interested in finding "best possible" layouts for static datasets?
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#14I like graph theory. You draw some shapes, you draw some lines. It's like the kind of things you can do with your crayons. I reckon kids could be introduced to it earlier in friendlier language.
I'm pretty sure this is also what draws in a lot of researchers. We're lucky that the theory is also so often useful.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#15I like graph theory. You draw some shapes, you draw some lines. It's like the kind of things you can do with your crayons. I reckon kids could be introduced to it earlier in friendlier language.
Wholeheartedly agree. Graph theory is probably one of the most relatable, accessible theories available. It is a fantastic tool to discover algorithmics, as you can visually apply your thinking. FWIW, I personally wrote my master thesis on small world graphs, (_ie_ Kevin Bacon, 6 degrees, that kind of graphs), building structures to add properties to such graphs, and it is, without a doubt, the best memory of my curs…
Can imagine Logo programming lang for graphs.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#16[deleted]
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#17Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
n=nodes>0; n^0.5=(log n)^3, n~24128091.7 , which is millions not billions?
https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28log+n...
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#18Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
n=nodes>0; n^0.5=(log n)^3, n~24128091.7 , which is millions not billions? https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28log+n...
You're using natural log, for my quick-and-dirty I used log2, which gives a slightly higher crossover point. The exact crossover depends on the size of the constant term, of course.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#19Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
I work with the researchers, and I think they'll be interested in knowing which version of the problem practitioners like yourself are most interested in. Do you ever add/remove edges, perhaps in bulk? Or do are you mostly interested in finding "best possible" layouts for static datasets?
I don't work on placement problems, though part of my work provides input for the placement problem (produce an optimized logic netlist that then has to be placed and routed). But if I can suggest something in the same ballpark: imagine that you have a large graph and you want to partition it into a small number of partitions (say, 4 to 10) of similar size. You want each partition to be a planar graph, and you want the number of interconnects between these graphs to be minimal. The graphs would correspond to metal layers on an ASIC. There's a lot of fuzziness in the way I stated it; to make it more rigorous a suitable cost function would need to be defined.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#20Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
n=nodes>0; n^0.5=(log n)^3, n~24128091.7 , which is millions not billions? https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28log+n...
[deleted]