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.

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

[FEA] MNMG triangle counting. #1912

Closed
seunghwak opened this issue Oct 27, 2021 · 2 comments
Closed

[FEA] MNMG triangle counting. #1912

seunghwak opened this issue Oct 27, 2021 · 2 comments
Assignees
Labels
improvement Improvement / enhancement to an existing function
Milestone

Comments

@seunghwak
Copy link
Contributor

seunghwak commented Oct 27, 2021

Is your feature request related to a problem? Please describe.
We need a triangle enumeration/counting mechanism.

We should be able to count triangles for every vertex (e.g. to implement clustering coefficient) AND/OR edge (e.g. to implement K-truss) AND/OR enumerate triangles (requiring memory large enough to store the entire set of triangles only if a caller requests to enumerate triangles as well).

Describe the solution you'd like
#1909 & #1911 will be a pre-requisite for this.

  1. We first keep the edges that are only in 2-core & from the lower degree vertex to the higher degree vertex. We can do this using [FEA] MNMG K-core #1909 & [FEA] MNMG edge filtering by source & destination properties. #1911

  2. After 1), there are two competing approaches. One is to find intersection on the source & destination vertices' neighbors, and the second is to iterate over wedges created by picking a vertex and a pair of vertices from the vertex's neighbor list and querying the existence of the edge between the pair. Need to evaluate their pros & cons in the context of cuGraph.

@seunghwak seunghwak added the ? - Needs Triage Need team to review and classify label Oct 27, 2021
@BradReesWork BradReesWork added this to the 22.04 milestone Nov 17, 2021
@BradReesWork BradReesWork added improvement Improvement / enhancement to an existing function and removed ? - Needs Triage Need team to review and classify labels Nov 17, 2021
@BradReesWork BradReesWork modified the milestones: 22.04, 22.06 Mar 22, 2022
@rapidsai rapidsai deleted a comment from github-actions bot Mar 22, 2022
@rapidsai rapidsai deleted a comment from github-actions bot Mar 22, 2022
@rlratzel rlratzel added the python label Apr 7, 2022
@ChuckHastings
Copy link
Collaborator

C++ definition and implementation addressed by #2233 and #2253
C API definition addressed by #2271

C API implementation TBD

@ChuckHastings
Copy link
Collaborator

C API implementation in #2302

@BradReesWork BradReesWork modified the milestones: 22.06, 22.08 Jun 1, 2022
@rlratzel rlratzel closed this as completed Jun 3, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
improvement Improvement / enhancement to an existing function
Projects
None yet
Development

No branches or pull requests

5 participants