search

bitwalker / libgraph

A graph data structure library for Elixir projects
MIT License
524 stars 75 forks source link

RFC: Implement k-core identification #1

Closed yonkeltron closed 7 years ago

yonkeltron commented 7 years ago

I love this library and have used it for graph analysis and manipulation at work! I was hoping to request k-core detection for graphs. I'd love to be able to do something like Graph.k_cores(some_graph, 5) for finding 5-cores. I was considering a signature like the following:

@spec k_cores(Graph.t(), integer()) :: [Graph.t()]
def k_cores(g, k) do
  ...
end

Can I provide additional information or clarification? Thanks again for making such a wonderful library!

bairdstar commented 7 years ago

Certainly interested in network techniques primarily from R ... not sure if the the R reference helps frame similar capability as example: http://svitsrv25.epfl.ch/R-doc/library/RBGL/html/kCores.html

bitwalker commented 7 years ago

@bairdstar Thanks for the additional reference, it is helpful :)

@yonkeltron I'm really glad to hear the library has been working great for you! This request definitely seems like something worth implementing! I will take a more in-depth look this weekend and see if I can't get something put together. Consider it on my TODO list :)

bitwalker commented 7 years ago

@yonkeltron I've pushed the initial implementation of k-core detection (plus some related API functions) to master. Could you give it a try and let me know? I've also added some tests against real-world graphs which check against their known k-degeneracy, so the implementation should be correct for any value of k, and I do have some tests against a smaller example graph which verifies the different k-cores - but it would be nice to have confirmation if you have some known data to test against which isn't arbitrarily fabricated :)

In short, the following was added:

Any feedback is appreciated!

bitwalker commented 7 years ago

Just FYI I've published this initial implementation in 0.10.0 - so docs are up on hexdocs.pm and it's a little easier to just upgrade and play with.

yonkeltron commented 7 years ago

This is outstanding, the turn around is incredible. Can I buy you a beer while I test this out?

bitwalker commented 7 years ago

@yonkeltron If you and I are ever at a conference together, I'd gladly take you up on that, especially since I'd get to hear about what you're building with libgraph - but your response is gift enough :). It's an unfortunate aspect of open source that despite the amount of time I spend working on my projects, I don't hear the positive feedback too often, if something works people are happy and just silently go about their day, most of the time you only hear if something is wrong :P

bairdstar commented 7 years ago

@bitwalker Fast work! Looks like I might need to add a language to my skills, and start with this capability set for network analysis experiments.

@yonkeltron Thanks for getting this on my radar and requesting the feature/capability.

yonkeltron commented 7 years ago

This looks amazing and seems to work great for our test graphs! We can close this whenever you're comfortable and we'll file bug issues if we ever run into any problems. Unfortunately we won't have heavier duty test data for a few weeks yet, but when we do...

In any case, if you'd like to hear about what we're working on, please don't hesitate to reach out on Twitter and we can set something up. I wouldn't mind a pointer to your Amazon wishlist, actually.

bitwalker commented 7 years ago

@yonkeltron That's great to hear! I'll go ahead and close this for now then. I'll be looking forward to hearing back on how things work out, particularly performance-wise! I have one improvement I'm planning on making tonight actually, and I'll try to set up some benchmarks too so that we can experiment should you find things unacceptable with your heavier datasets.

What's your Twitter handle? I'll shoot you a DM!

yonkeltron commented 7 years ago

@yonkeltron is me everywhere!

On Tue, Jul 18, 2017, 11:42 PM Paul Schoenfelder notifications@github.com wrote:

Closed #1 https://github.com/bitwalker/libgraph/issues/1.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/bitwalker/libgraph/issues/1#event-1169507377, or mute the thread https://github.com/notifications/unsubscribe-auth/AADoO6UDBArRWh8wXh5WSg3wfoiaPsPrks5sPXsogaJpZM4OYjGA .

-- +Jonathan