What kind of methods are there to find natural groups or clusters within an undirected graph structure? I am new to graph theory, but the project seems to have confronted me with questions that could use it.
1) For one graph.
2) Over a set of independent graphs that may have the same nodes.
I've heard of e.g. Tarjan's strongly connected components algorithm that works for directed graphs. Are there similar ones for undirected graphs? The number of groups within the graph is unknown, and should depend strictly on the data (though an arbitrary threshold can be given), and there is no problem if some nodes end up as monads that fit nowhere.
For Question 2, I've cobbled together a method that tests for each edge in a set whether the nodes exist in other sets, and reports the ratio of sets that, if they contain one of these nodes, contain exactly the same edge. (R script here.) Any idea if there's an established method with more or less the same technique, or which methods I should use instead?