Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[FEA] MNMG K-core #1909

Closed
seunghwak opened this issue Oct 27, 2021 · 0 comments · Fixed by #1933
Closed

[FEA] MNMG K-core #1909

seunghwak opened this issue Oct 27, 2021 · 0 comments · Fixed by #1933
Assignees
@seunghwak
Labels
? - Needs Triage Need team to review and classify

Comments

@seunghwak
Copy link
Contributor

seunghwak commented Oct 27, 2021 •
edited
Loading

Is your feature request related to a problem? Please describe.
It is common to first remove degree 0 & 1 vertices (in a recursive manner as removing a degree 1 vertex can create another degree 1 vertex) to efficiently enumerate triangles. MNMG K-core is a pre-requisite to implement efficient MNMG triangle counting.

Describe the solution you'd like
I think K-core can be implemented using the update_frontier_v_push_if_out_nbr graph primitive (https://github.com/rapidsai/cugraph/blob/branch-21.12/cpp/include/cugraph/prims/update_frontier_v_push_if_out_nbr.cuh#L801).

Starting with the vertices with their degrees [1, K) as the initial frontier, decrement degrees for the vertices in the next level, and push the vertices in the queue for the iteration in the next step if vertex degrees become smaller than K.
@seunghwak seunghwak added the ? - Needs Triage Need team to review and classify label Oct 27, 2021
This was referenced Oct 27, 2021
Closed
Merged
@seunghwak seunghwak self-assigned this Nov 3, 2021
This was referenced Nov 8, 2021
Merged
Merged
rapids-bot bot pushed a commit that referenced this issue Nov 9, 2021
@seunghwak
K-core decomposition API update (#1924)
7bffab8 
Partially addresses #1909.

- [x] Add a K-core  function declaration.

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Rick Ratzel (https://github.com/rlratzel)

URL: #1924
rapids-bot bot pushed a commit that referenced this issue Nov 11, 2021
@seunghwak
Add options to drop self-loops & multi_edges in C++ test graph genera…
0730fea 
…tion (#1934)

Necessary for #1909 

Add options to filter out self-loops & multi-edges after edge generation and before graph creation in C++ test graph generation API.

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)

Approvers:
  - Chuck Hastings (https://github.com/ChuckHastings)

URL: #1934
rapids-bot bot pushed a commit that referenced this issue Nov 12, 2021
@seunghwak
K-core implementation for undirected graphs (#1933)
5db6636 
Close #1909.

This PR aims to implement K-core only for undirected graphs.

- [x] Implement K-core implementation
- [x] Test/debug on SG
- [x] Test/debug on MG

Authors:
  - Seunghwa Kang (https://github.com/seunghwak)
  - Kumar Aatish (https://github.com/kaatish)
  - Divye Gala (https://github.com/divyegala)

Approvers:
  - Chuck Hastings (https://github.com/ChuckHastings)
  - Kumar Aatish (https://github.com/kaatish)

URL: #1933
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@seunghwak seunghwak

Labels
? - Needs Triage Need team to review and classify
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

K-core implementation for undirected graphs seunghwak/cugraph
1 participant
@seunghwak