Does anyone know a fast method to decompose a biconnected graph, into probably overlapping clusters?, as you may know, a biconnected graph is a graph without any articulation nodes. any suggestions are very much appreciated.
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with . The illustration above shows some bipartite graphs, with vertices in each graph colored based on to which of the two disjoint sets they belong.
Bipartite graphs are equivalent to two-colorable graphs. All acyclic graphs are bipartite. A cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).
is the definition I found on http://mathworld.wolfram.com/BipartiteGraph.html
Decomposing apparently needs a supplement, like decomposing into what?
See http://www.sciencedirect.com/science/article/pii/S0166218X0600357X, for instance.
I am not so sure about what you mean by overlapping clusters either. Perhaps if you explained your question better...
Thank you very much for your answer; But, I think there is some kind of misunderstanding here, I meant "biconnected" (https://en.wikipedia.org/wiki/Biconnected_graph) not "bipartite".
What do you mean by overlapping clusters? If you cut a biconnected into two pieces you will just obtain two non-overlapping graphs. Biconnected just means that you need to remove at least two vertices, one is guaranteed to be not enough.
If you wish that your cuts respect some properties, like density, you might want to check some algorithms such as DBSCAN or OPTICS. Although they won't give you overlapping clusters.
Thank you @Damien_Aubert, I was wondering what is to partition a k-connected graph, and a simple case of such graph is a biconnected (2-connected) graph.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs