Similar Communities: Find and Rank Related Communities by Member Overlap

Question

## Problem

Given a dataset of communities and their member sets, implement a function that returns the top `k` communities most similar to a given community, ranked by **Jaccard similarity** of member sets.

```python
def similar_communities(
    target: str,
    community_members: dict[str, set[str]],  # community_id -> set of user_ids
    k: int
) -> list[tuple[str, float]]:  # [(community_id, jaccard_score)], descending
    pass
```

## Example

```
community_members = {
  "python": {"alice", "bob", "carol", "dave"},
  "django": {"alice", "bob", "eve"},
  "flask":  {"bob", "carol", "frank"},
  "java":   {"dave", "george"}
}

similar_communities("python", community_members, k=2)
# jaccard(python, django) = |{alice,bob}| / |{alice,bob,carol,dave,eve}| = 2/5 = 0.4
# jaccard(python, flask)  = |{bob,carol}| / |{alice,bob,carol,dave,frank}| = 2/5 = 0.4
# jaccard(python, java)   = |{dave}| / |{alice,bob,carol,dave,george}| = 1/5 = 0.2
Output: [("django", 0.4), ("flask", 0.4)]  # ties broken arbitrarily
```

## Follow-ups

1. With millions of communities, computing pairwise Jaccard is infeasible. How does MinHash/LSH help?
2. How would you update similarities incrementally as users join and leave communities?
3. Should you exclude very large communities (>10M members) from similarity? Why?

Similar Communities: Find and Rank Related Communities by Member Overlap

Question Details

Full Details

Topics

More from Reddit