1
$\begingroup$

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?

  • 0
    Maybe 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 2

4

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.

  • 0
    This looks very close to what I want. Thanks.2011-07-13
0

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

  • 0
    Nope, not really what I'm looking for. Cluster analysis takes into account similarity, but not connection.2011-07-11