Finding communities in social networks

Lately, I’ve been interested in how social networks may help software to identify common user traits so the application adapts to users’ need.

Software should be able to apply per user customization properties between common members of users’ groups. These communities should be discovered by the application using existing relationships among the users. The relationship should be an integral part of the application, set by the users (via internal application messaging, internal address book, subscription to mailing lists/interest groups…) or the application administrators (hierarchical definitions, ACLs…). From the set of communities the application should extract  customization properties and recommend the common ones to the rest of the community.

Two documents have been useful:

1. Social networks that matter: Twitter under the microscope
   is an introductory paper about choosing the right metric for identifying communities in Twitter, but easily applicable to other social networks.  Conclusion for Twitter: Number of followers is not a good metric, @friends are.

2. Discovering Communities in Linear Time: a Physics Approach is a much more interesting paper. It proposes using Kirchhoff’s laws to find communities in linear time (without the need of edge cutting). The algorithm has some drawbacks (Usha Nandini Raghavan, Reka Albert, Soundar Kumara propose an alternative), but the approach is interesting because allows to identify communities without identifying hierarchical structures.

For more social network papers, HP Labs has an interesting set of them.

Oh! I also work for an HP company, but I have no relationship to the HP Labs papers.