1

I have an adjacency matrix, and I can't seem to find a quick way to combine multiple nodes to know what the final number of "super-nodes" are. I thought an easy solution was to essentially compute the sum of the upper triangular part of the adjacency matrix, and subtracting the total amount of nodes minus the previous sum would give me the answer, but it looks a bit more tricky.

Suppose:

I have 6 nodes from 1 to 6: Nodes 1,2,3 are connected all to each other. Nodes 4 and 6 are connected to each other, Node 5 is not connected to anything.

At this point it seems trivial that of the 6 initial nodes I will only have 3 remaining super nodes. Now the problem by using my method before is that suppose the first super-node is connected like this: 1 to 2 2 to 3, but not 1 to 3 directly. (even though they merge).

Here sum(upptriangle(Adj))=3 works, but for the first case I am adding a "dummy node" (the connection 1-3) outputs: sum(upptriangle(Adj))=4, and this type of connection should not affect the final result.

Is there a standard algorithm I am missing, to solve this problem (and compensate for overcomplete of non fully connected sub-graphs?), instead of iteratively going over every node to see if it's been merged?

In other words, is there a fast computation of node merging that I can get only from the adjacency matrix?

Arturo
  • 3,679
  • 6
  • 34
  • 43
  • When you say "connected," do you mean "there's an edge between them?" As in, is the goal to determine how many different connected components there are? – templatetypedef Nov 25 '15 at 23:14
  • @templatetypedef yes essentially. – Arturo Nov 25 '15 at 23:15
  • Please see [here](http://stackoverflow.com/questions/8124626/finding-connected-components-of-adjacency-matrix-graph) and [here](http://stackoverflow.com/questions/8124626/finding-connected-components-of-adjacency-matrix-graph) – Imran Nov 25 '15 at 23:18

1 Answers1

1

When your problem is not dynamic you can use BFS or DFS to find the components. Using BFS or DFS to determine the connectivity in a non connected graph?

But if your problem is dynamic you should use union find data-structure.
Union-find data structure

Community
  • 1
  • 1
Saeid
  • 4,147
  • 7
  • 27
  • 43
  • Another option I found that seems doable is to create the graph G with the sparse data structure in MATLAB, and then use the graphconncomp(G), to find the number of independent connected components. – Arturo Nov 27 '15 at 23:51