Computing Sections of a Graph Which Can Be Removed By Removing Two Edges

In summary: Yes, I think that's a reasonable approach.In summary, the algorithm to remove vertices and edges from a graph is easy to code in Matlab, but it may be slow depending on the size of the graph.
  • #1
325
51
TL;DR Summary
I would like to write an algorithm to do this in MATLAB to analyze a network of atomic bonds.
Hi. I have graph which I am analyzing in MATLAB. I would like to determine sections of the graph which could be removed from the rest of the graph by removing only 2 edges. (The graph represents the network of atomic bonds from a simulation of silica, and I am attempting to locate strands of atoms). Is there an efficient algorithm for computing this? Here is a sketch of what I mean:
graph.jpg

Thank you!
 
Physics news on Phys.org
  • #2
How large is your graph?

Convert edges to vertices and vertices to edges (connecting all associated new vertices with each other) and test if the new graph is 3-vertex-connected:

https://mathworld.wolfram.com/BiconnectedGraph.html
https://reference.wolfram.com/language/ref/KVertexConnectedGraphQ.html

No idea about the runtime of that algorithm, and no idea if Matlab has one on its own.

That's only telling you if such a structure exists, but presumably somewhere in the code it also identifies these structures.

Looking for "2-edge connected" as keyword might show something as well.
 
Last edited:
  • #3
The graph has (approximately) 2500 vertices and 6500 edges. The graph changes over time, so it should be done iteratively for each step (125 in my case). I plan on having larger graphs in the future however, maybe on the order of 10s or even 100s of thousands of vertices. (I may have to use my university's computing cluster for this).

I can't find any tools in MATLAB for either switching vertices and edges or determining k-vertex-connectedness though.

I think an easier alternative might be to determine sections which can be removed from the graph by removing two vertices which each only have two edges. This is of course a different problem, but I think if I had strands of atoms, there would be atoms on either side of the strand only bonded to two other atoms. Here's a sketch:
graph.jpg


For this problem, I think I could iterate through all pairs of vertices which have two edges (there shouldn't be many vertices with only two edges) and see if their removal leads to separate graphs.

The smaller subgraph (the one which is the strand of atoms) would like have multiple vertices with only two edges (it might actually be the only place where there's vertices with two edges). Because of that, I think I could remove all vertices with two edges which are within the smaller subgraph from the iteration process to improve efficiency. (They would just find strands which are part of a larger strand). Here is a sketch:
graph dont check.jpg


I think this is something I could code easily (removing vertices and finding separate graphs is built into MATLAB).

Does the approach seem reasonable?
 
  • #4
Chains of atoms certainly help. Start with atoms with only two connections, extend them to mark the full chain (this is trivial as you can just keep following the connections), then check pairs of chains.

It should also be possible to make a meta-graph out of densely connected regions as vertices with these chains as edges between them.
 
  • #5
mfb said:
extend them to mark the full chain (this is trivial as you can just keep following the connections)
I'm a bit confused about this step. How would it know when to stop? I'm not assuming these are chains of single atoms. It could be a cluster of atoms like shown:
20210111_205729.jpg
My idea was to say the chain is bounded by atoms with only to bonds, but there could be atoms with more than two bonds within the chain.

(I imagine this would be easier if I showed pictures of the simulations, but it's unpublished research and I'm not sure what the rules are on what I can show).
 
  • #6
Smaller clusters are still reasonably easy to identify I think. Make a list of connected atoms, check all their connections recursively. You either run into a dead end before you reached N atoms (end of the chain), you reach a single open connection (cluster) or you reach N atoms (bulk). If your whole chain can look like a ladder things get more complicated.
 
  • Like
Likes person123
  • #7
I found that it's okay to show it, so this is what one of them looks like:
chain.jpg

Is N the maximum number of atoms in the chain?
 
  • #8
The N in my post would be the maximum number of atoms in small clusters as part of a larger chain. If you find more atoms that are densely connected then you are not in a chain any more.
 

1. What is meant by "computing sections of a graph"?

"Computing sections of a graph" refers to the process of identifying and analyzing different parts or subgraphs of a larger graph. This can involve determining the number of vertices and edges in a section, finding the shortest path between two vertices, or identifying which edges can be removed without disconnecting the graph.

2. Why is it important to be able to remove two edges from a graph?

Removing two edges from a graph can help simplify and clarify the structure of the graph. It can also be a useful tool in finding patterns and relationships within the graph, as well as identifying potential vulnerabilities or weak points.

3. How do you determine which edges can be removed from a graph without disconnecting it?

To determine which edges can be removed without disconnecting a graph, you can use the concept of vertex connectivity. If the removal of an edge does not change the minimum number of vertices needed to disconnect the graph, then that edge can be removed without disconnecting the graph.

4. Are there any limitations to being able to remove two edges from a graph?

Yes, there are limitations to being able to remove two edges from a graph. The graph must be connected to begin with, and removing the two edges should not result in a disconnected graph. Additionally, the removal of the two edges should not create any new cycles or multiple edges between the same pair of vertices.

5. What are some real-world applications of computing sections of a graph by removing two edges?

There are many real-world applications of computing sections of a graph by removing two edges, such as network analysis, transportation planning, and social network analysis. It can also be used in fields like biology, chemistry, and computer science to model and analyze complex systems and relationships.

Suggested for: Computing Sections of a Graph Which Can Be Removed By Removing Two Edges

Replies
3
Views
1K
Replies
1
Views
575
Replies
1
Views
624
Replies
2
Views
687
Replies
4
Views
3K
  • Poll
Replies
11
Views
2K
Replies
8
Views
1K
Replies
3
Views
2K
Replies
23
Views
4K
Back
Top