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?
What graph theoretic methods which can identify groups?
-
0Maybe a good definition of group would be your first step; are groups disjoint (then you are looking for an equivalence relation)? If not, maybe you have a definition like "a group is a collection of people, such that any person knows at least k other people in the group" or similar... – 2011-07-11
2 Answers
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.
-
0This looks very close to what I want. Thanks. – 2011-07-13
Maybe you're looking for what's called "cluster analysis." The Wikipedia article on the topic may be a good place to start. http://en.wikipedia.org/wiki/Cluster_analysis
-
0Nope, not really what I'm looking for. Cluster analysis takes into account similarity, but not connection. – 2011-07-11