4
$\begingroup$

I have some social network data in which I'd like to identify people who belong to a group of 5 friends. These are users who are friends with 4 other people who all are also friends with each other.

In the graph sense, this task involves identifying components of the graph where each node has an edge between every other node in the component and where the component contains at least 5 nodes.

Is there a well known algorithm to do this? I was looking at measures like centrality, clustering coefficients, and strongly connected components but none of those are quite what I want.

Thanks!

$\endgroup$
5
$\begingroup$

Community Detection and Clique Percolation:

This is a community detection problem. Here is a very detailed review article surveying the state of the art.

The Clique Percolation Method is also useful to explore as it pretty much solves what you may need to know. You can also go through what Matching is, and link the concept with Blossom Algorithm. Though, this finds the maximum matching, you may slightly modify the algorithm to get the minimum matchings of 5 at least.

| improve this answer | |
$\endgroup$
  • $\begingroup$ How exactly is matching relevant here? $\endgroup$ – Valentas May 9 '16 at 11:11
1
$\begingroup$

Not so much an 'algorithm' but Neo4j allows you to query a graph network, and this type of question features quite heavily in their demos. Here is an example of the Cypher language syntax you might have to use in your social network case:

MATCH (a:Person)-[:FRIENDS_WITH]->(b:Person), (b)-[:FRIENDS_WITH]->(c:Person) 
WITH b.name AS Friends, count(c) as MutualFriends    
WHERE a.name = "Ollie" AND NOT (a)-[:FRIENDS_WITH]->(c) AND MutualFriends > 5
RETURN Friends, MutualFriends

The code might not be perfect, but it's for show. This kind of query returns results very quickly with medium to large graphs, and especially so if you can load your data and use indexes to search by name. Depends if you want to start from scratch!

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.