What graph theoretic methods which can identify groups? Given a social graph, for instance, from Twitter, I want to identify groups.  Here I define groups as any highly connected (although not necessarily complete) subgraph.  What algorithms or methods exist that could help me here?

I recommend that you take a look at the paper Fast Unfolding of Communities in Large Networks. It gives a natural definition of what you mean by a group (a subgraph where the members are highly connected to each other, and non-members are not strongly connected to members) and then gives a fast algorithm for detecting such groups.
As a bonus, the algorithm produces as its output a graph of groups, with edges indicating the strength of connection between different groups. You can then apply the algorithm again to the new graph, and so forth, generating a hierarchical community structure for your network.
