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

Add a function to find densest subgraph #570

Open
mtreinish opened this issue Mar 10, 2022 · 2 comments · May be fixed by #635
Open

Add a function to find densest subgraph #570

mtreinish opened this issue Mar 10, 2022 · 2 comments · May be fixed by #635
Assignees
@mtreinish
Labels
enhancement New feature or request

Comments

@mtreinish
Copy link
Member

What is the expected enhancement?

Something that came up in the review on Qiskit/qiskit#7740 is that it would be good for retworkx to have a function to find the densest subgraph in a graph. To start we can just reuse the algorithm from the DenseLayout pass which just performs a BFS list from every node in the graph (in parallel) and takes the first n nodes from that and applies the weights and picks the most connected one with the best score from the weights. I'm not familiar with the literature on this problem space, but if there is a better algorithm that offers a faster or more complete solution we can look at implementing that too.
@mtreinish mtreinish added the enhancement New feature or request label Mar 10, 2022
@mtreinish mtreinish added this to the 0.12.0 milestone Mar 10, 2022
@mtreinish mtreinish self-assigned this Mar 27, 2022
mtreinish added a commit to mtreinish/retworkx that referenced this issue Mar 27, 2022
@mtreinish
Add function to find densest subgraph
944df0f 
Fixes Qiskit#570
@szhorvat
Copy link

What is a "densest subgraph"? Take any graphs with at least one edge. Take that edgs, along with its endpoints, as a subgraph: it has density 1, the highest possible.

mtreinish added a commit to mtreinish/retworkx that referenced this issue Apr 18, 2022
@mtreinish
Add function to find densest subgraph
be31e23 
Fixes Qiskit#570
@mtreinish
Copy link
Member Author

mtreinish commented Apr 18, 2022 •
edited

That's my bad it should be something like find_densest_subgraph_of_size or something like that. Specifically the function is given a graph of M nodes we want to find subgraph of size N that has the highest degree of connectivity between the nodes. I agree if N = 2 then this is any pair of nodes with an edge but for N > 2 it's not as simple.

mtreinish added a commit to mtreinish/retworkx that referenced this issue Jun 27, 2022
@mtreinish
Add function to find densest subgraph
1822fc3 
This commit adds a new function find_densest_subgraph_of_size() to
retworkx. This function is used to find a subgraph in a given graph of a
specified size that has the highest degree of connectivity of nodes.

Fixes Qiskit#570
@mtreinish mtreinish linked a pull request Jun 27, 2022 that will close this issue
Open
2 tasks
@mtreinish mtreinish removed this from the 0.12.0 milestone Oct 4, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mtreinish mtreinish

Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add function to find densest subgraph mtreinish/retworkx
2 participants
@szhorvat @mtreinish