그래프 알고리즘으로 친구 추천하기 Friend Recommendations with Graph Algorithms

Friend Recommendations with Graph Algorithms

Friend recommendations keep users engaged by suggesting relevant connections. Graph databases excel at this—the data structure naturally encodes the signals needed for recommendations: mutual friends, shared interests, and network proximity.

1. Recommendation Signals

Effective friend recommendations combine multiple signals:

• Mutual friends: More mutual connections = higher likelihood of knowing each other
• Friends of friends: 2nd-degree connections are natural candidates
• Shared interests: Common tags, groups, or activity patterns
• Network proximity: Closer in the graph = more relevant

Each signal can be weighted based on its predictive value.

2. Mutual Friends Algorithm

The simplest and most effective signal—people with mutual friends often know each other:

@Query("""
    MATCH (me:User {username: $username})-[:FRIENDS_WITH]-(friend:User)
          -[:FRIENDS_WITH]-(candidate:User)
    WHERE candidate <> me
      AND NOT (me)-[:FRIENDS_WITH]-(candidate)
      AND NOT (me)-[:BLOCKED]-(candidate)
    WITH candidate, count(DISTINCT friend) as mutualCount
    WHERE mutualCount >= $minMutual
    RETURN candidate, mutualCount
    ORDER BY mutualCount DESC
    LIMIT $limit
    """)
List<FriendRecommendation> recommendByMutualFriends(String username, int minMutual, int limit);

The count(DISTINCT friend) counts how many paths exist between me and candidate through friends—this equals the mutual friend count.

3. Weighted Multi-Signal Recommendations

Combine signals with weights for better recommendations:

@Query("""
    MATCH (me:User {username: $username})

    // Find candidates (friends of friends)
    OPTIONAL MATCH (me)-[:FRIENDS_WITH]-(friend)-[:FRIENDS_WITH]-(candidate)
    WHERE candidate <> me AND NOT (me)-[:FRIENDS_WITH]-(candidate)

    WITH me, candidate, count(DISTINCT friend) as mutualFriends
    WHERE candidate IS NOT NULL

    // Shared interests signal
    OPTIONAL MATCH (me)-[:INTERESTED_IN]->(interest)<-[:INTERESTED_IN]-(candidate)
    WITH me, candidate, mutualFriends, count(DISTINCT interest) as sharedInterests

    // Same location signal
    OPTIONAL MATCH (me)-[:LIVES_IN]->(loc)<-[:LIVES_IN]-(candidate)
    WITH candidate, mutualFriends, sharedInterests,
         CASE WHEN loc IS NOT NULL THEN 1 ELSE 0 END as sameLocation

    // Calculate weighted score
    WITH candidate,
         mutualFriends,
         sharedInterests,
         sameLocation,
         (mutualFriends * 3) + (sharedInterests * 2) + (sameLocation * 1) as score

    WHERE score > 0
    RETURN candidate.username as username,
           candidate.displayName as displayName,
           mutualFriends,
           sharedInterests,
           sameLocation,
           score
    ORDER BY score DESC
    LIMIT $limit
    """)
List<ScoredRecommendation> getRecommendationsWithScore(String username, int limit);

The weights (3, 2, 1) prioritize mutual friends over shared interests over location. Adjust based on what works for your user base.

4. Recommendation Service

@Service
public class RecommendationService {

    private final UserRepository userRepository;

    public RecommendationService(UserRepository userRepository) {
        this.userRepository = userRepository;
    }

    public List<ScoredRecommendation> getFriendRecommendations(String username, int limit) {
        // Get weighted recommendations
        List<ScoredRecommendation> recommendations =
            userRepository.getRecommendationsWithScore(username, limit * 2);

        // Filter out recently rejected suggestions (optional)
        Set<String> recentlyRejected = getRecentlyRejected(username);
        recommendations = recommendations.stream()
            .filter(r -> !recentlyRejected.contains(r.username()))
            .limit(limit)
            .toList();

        return recommendations;
    }

    public List<User> getPeopleYouMayKnow(String username, int limit) {
        // Simpler version for quick suggestions
        return userRepository.recommendByMutualFriends(username, 2, limit);
    }
}

5. Jaccard Similarity

For more sophisticated matching, calculate Jaccard similarity—the intersection over union of friend sets:

@Query("""
    MATCH (me:User {username: $username})-[:FRIENDS_WITH]-(myFriend:User)
    WITH me, collect(myFriend) as myFriends

    MATCH (candidate:User)-[:FRIENDS_WITH]-(theirFriend:User)
    WHERE candidate <> me
      AND NOT (me)-[:FRIENDS_WITH]-(candidate)
      AND NOT (me)-[:BLOCKED]-(candidate)
    WITH me, myFriends, candidate, collect(theirFriend) as theirFriends

    // Calculate intersection
    WITH candidate, myFriends, theirFriends,
         [f IN myFriends WHERE f IN theirFriends] as intersection

    // Calculate union (myFriends + theirFriends not in myFriends)
    WITH candidate,
         size(intersection) as intersectionSize,
         size(myFriends) + size([f IN theirFriends WHERE NOT f IN myFriends]) as unionSize

    WHERE unionSize > 0
    WITH candidate,
         intersectionSize,
         toFloat(intersectionSize) / unionSize as jaccardSimilarity

    WHERE jaccardSimilarity > $threshold
    RETURN candidate, jaccardSimilarity, intersectionSize as mutualFriends
    ORDER BY jaccardSimilarity DESC
    LIMIT $limit
    """)
List<SimilarityResult> findSimilarUsers(String username, double threshold, int limit);

Jaccard similarity ranges from 0 to 1. A threshold of 0.1-0.2 usually filters noise while keeping relevant suggestions.

6. Cold Start Problem

New users have no friends, so friend-based recommendations fail. Handle this with fallback strategies:

public List<User> getRecommendationsForNewUser(String username, int limit) {
    User user = userRepository.findByUsername(username)
        .orElseThrow(() -> new UserNotFoundException(username));

    // Strategy 1: Same location
    if (user.getLocation() != null) {
        List<User> localUsers = userRepository.findPopularUsersInLocation(
            user.getLocation().getId(), limit);
        if (!localUsers.isEmpty()) {
            return localUsers;
        }
    }

    // Strategy 2: Shared interests
    if (!user.getInterests().isEmpty()) {
        List<User> interestMatch = userRepository.findUsersBySharedInterests(
            username, limit);
        if (!interestMatch.isEmpty()) {
            return interestMatch;
        }
    }

    // Strategy 3: Popular/active users
    return userRepository.findMostActiveUsers(limit);
}

@Query("""
    MATCH (u:User)-[:LIVES_IN]->(:Location {id: $locationId})
    WHERE u.status = 'ACTIVE'
    OPTIONAL MATCH (u)<-[:FOLLOWS]-(follower)
    WITH u, count(follower) as followerCount
    ORDER BY followerCount DESC
    LIMIT $limit
    RETURN u
    """)
List<User> findPopularUsersInLocation(Long locationId, int limit);

@Query("""
    MATCH (me:User {username: $username})-[:INTERESTED_IN]->(interest)
          <-[:INTERESTED_IN]-(other:User)
    WHERE other <> me AND NOT (me)-[:FRIENDS_WITH]-(other)
    WITH other, count(interest) as sharedCount
    ORDER BY sharedCount DESC
    LIMIT $limit
    RETURN other
    """)
List<User> findUsersBySharedInterests(String username, int limit);

7. Neo4j Graph Data Science (Optional)

For large-scale recommendations, Neo4j’s Graph Data Science library provides optimized algorithms:

// First, project the graph
@Query("""
    CALL gds.graph.project(
        'social-network',
        'User',
        {
            FRIENDS_WITH: {orientation: 'UNDIRECTED'},
            FOLLOWS: {orientation: 'NATURAL'}
        }
    )
    """)
void projectGraph();

// Node similarity using GDS
@Query("""
    CALL gds.nodeSimilarity.stream('social-network', {
        topK: $topK,
        similarityCutoff: $cutoff
    })
    YIELD node1, node2, similarity
    WHERE gds.util.asNode(node1).username = $username
    RETURN gds.util.asNode(node2) as similarUser, similarity
    ORDER BY similarity DESC
    """)
List<SimilarityResult> findSimilarUsersGDS(String username, int topK, double cutoff);

GDS computes similarity more efficiently for large graphs by using optimized algorithms and parallel processing.

8. REST Controller

@RestController
@RequestMapping("/api/recommendations")
public class RecommendationController {

    private final RecommendationService recommendationService;

    @GetMapping("/friends")
    public ResponseEntity<List<ScoredRecommendation>> getFriendRecommendations(
            @AuthenticationPrincipal UserDetails user,
            @RequestParam(defaultValue = "10") int limit) {
        return ResponseEntity.ok(
            recommendationService.getFriendRecommendations(user.getUsername(), limit));
    }

    @GetMapping("/people-you-may-know")
    public ResponseEntity<List<UserDto>> getPeopleYouMayKnow(
            @AuthenticationPrincipal UserDetails user,
            @RequestParam(defaultValue = "5") int limit) {
        List<User> suggestions = recommendationService.getPeopleYouMayKnow(
            user.getUsername(), limit);
        return ResponseEntity.ok(suggestions.stream().map(UserDto::from).toList());
    }

    @PostMapping("/dismiss/{username}")
    public ResponseEntity<Void> dismissRecommendation(
            @AuthenticationPrincipal UserDetails user,
            @PathVariable String username) {
        recommendationService.dismissRecommendation(user.getUsername(), username);
        return ResponseEntity.ok().build();
    }
}

9. Caching Recommendations

Recommendations are expensive to compute. Cache them:

@Service
public class CachedRecommendationService {

    private final RecommendationService recommendationService;
    private final Cache<String, List<ScoredRecommendation>> cache;

    public CachedRecommendationService(RecommendationService recommendationService) {
        this.recommendationService = recommendationService;
        this.cache = Caffeine.newBuilder()
            .expireAfterWrite(Duration.ofHours(1))
            .maximumSize(10_000)
            .build();
    }

    public List<ScoredRecommendation> getRecommendations(String username, int limit) {
        return cache.get(username, key ->
            recommendationService.getFriendRecommendations(key, limit));
    }

    public void invalidate(String username) {
        cache.invalidate(username);
    }
}

Invalidate the cache when a user adds friends, updates interests, or changes location.

10. Conclusion

Graph-based friend recommendations leverage the network structure that already encodes social signals. Mutual friends remain the strongest predictor, but combining multiple signals improves relevance. For new users, fall back to location, interests, or popularity. At scale, Neo4j’s Graph Data Science library provides optimized similarity algorithms. This concludes the social network series—from basic setup through schema design, relationships, feeds, and recommendations.

그래프 알고리즘으로 친구 추천하기

친구 추천은 관련성 있는 연결을 제안하여 사용자 참여를 유지한다. 그래프 데이터베이스가 이 작업에 뛰어난 이유는 데이터 구조가 추천에 필요한 신호를 자연스럽게 인코딩하기 때문이다: 상호 친구, 공유 관심사, 네트워크 근접성.

1. 추천 신호

효과적인 친구 추천은 여러 신호를 결합한다:

• 상호 친구: 더 많은 상호 연결 = 서로 알 확률이 높음
• 친구의 친구: 2차 연결은 자연스러운 후보
• 공유 관심사: 공통 태그, 그룹 또는 활동 패턴
• 네트워크 근접성: 그래프에서 가까울수록 더 관련성 있음

각 신호는 예측 가치에 따라 가중치를 부여할 수 있다.

2. 상호 친구 알고리즘

가장 단순하고 효과적인 신호—상호 친구가 있는 사람들은 종종 서로 안다:

@Query("""
    MATCH (me:User {username: $username})-[:FRIENDS_WITH]-(friend:User)
          -[:FRIENDS_WITH]-(candidate:User)
    WHERE candidate <> me
      AND NOT (me)-[:FRIENDS_WITH]-(candidate)
      AND NOT (me)-[:BLOCKED]-(candidate)
    WITH candidate, count(DISTINCT friend) as mutualCount
    WHERE mutualCount >= $minMutual
    RETURN candidate, mutualCount
    ORDER BY mutualCount DESC
    LIMIT $limit
    """)
List<FriendRecommendation> recommendByMutualFriends(String username, int minMutual, int limit);

count(DISTINCT friend)는 me와 candidate 사이에 친구를 통해 존재하는 경로 수를 계산한다—이것이 상호 친구 수와 같다.

3. 가중치 기반 다중 신호 추천

더 나은 추천을 위해 신호를 가중치와 결합한다:

@Query("""
    MATCH (me:User {username: $username})

    // Find candidates (friends of friends)
    OPTIONAL MATCH (me)-[:FRIENDS_WITH]-(friend)-[:FRIENDS_WITH]-(candidate)
    WHERE candidate <> me AND NOT (me)-[:FRIENDS_WITH]-(candidate)

    WITH me, candidate, count(DISTINCT friend) as mutualFriends
    WHERE candidate IS NOT NULL

    // Shared interests signal
    OPTIONAL MATCH (me)-[:INTERESTED_IN]->(interest)<-[:INTERESTED_IN]-(candidate)
    WITH me, candidate, mutualFriends, count(DISTINCT interest) as sharedInterests

    // Same location signal
    OPTIONAL MATCH (me)-[:LIVES_IN]->(loc)<-[:LIVES_IN]-(candidate)
    WITH candidate, mutualFriends, sharedInterests,
         CASE WHEN loc IS NOT NULL THEN 1 ELSE 0 END as sameLocation

    // Calculate weighted score
    WITH candidate,
         mutualFriends,
         sharedInterests,
         sameLocation,
         (mutualFriends * 3) + (sharedInterests * 2) + (sameLocation * 1) as score

    WHERE score > 0
    RETURN candidate.username as username,
           candidate.displayName as displayName,
           mutualFriends,
           sharedInterests,
           sameLocation,
           score
    ORDER BY score DESC
    LIMIT $limit
    """)
List<ScoredRecommendation> getRecommendationsWithScore(String username, int limit);

가중치(3, 2, 1)는 상호 친구를 공유 관심사보다, 공유 관심사를 위치보다 우선시한다. 사용자 기반에 맞게 조정한다.

4. 추천 서비스

@Service
public class RecommendationService {

    private final UserRepository userRepository;

    public RecommendationService(UserRepository userRepository) {
        this.userRepository = userRepository;
    }

    public List<ScoredRecommendation> getFriendRecommendations(String username, int limit) {
        // Get weighted recommendations
        List<ScoredRecommendation> recommendations =
            userRepository.getRecommendationsWithScore(username, limit * 2);

        // Filter out recently rejected suggestions (optional)
        Set<String> recentlyRejected = getRecentlyRejected(username);
        recommendations = recommendations.stream()
            .filter(r -> !recentlyRejected.contains(r.username()))
            .limit(limit)
            .toList();

        return recommendations;
    }

    public List<User> getPeopleYouMayKnow(String username, int limit) {
        // Simpler version for quick suggestions
        return userRepository.recommendByMutualFriends(username, 2, limit);
    }
}

5. Jaccard 유사도

더 정교한 매칭을 위해 Jaccard 유사도를 계산한다—친구 집합의 교집합을 합집합으로 나눈 값:

@Query("""
    MATCH (me:User {username: $username})-[:FRIENDS_WITH]-(myFriend:User)
    WITH me, collect(myFriend) as myFriends

    MATCH (candidate:User)-[:FRIENDS_WITH]-(theirFriend:User)
    WHERE candidate <> me
      AND NOT (me)-[:FRIENDS_WITH]-(candidate)
      AND NOT (me)-[:BLOCKED]-(candidate)
    WITH me, myFriends, candidate, collect(theirFriend) as theirFriends

    // Calculate intersection
    WITH candidate, myFriends, theirFriends,
         [f IN myFriends WHERE f IN theirFriends] as intersection

    // Calculate union (myFriends + theirFriends not in myFriends)
    WITH candidate,
         size(intersection) as intersectionSize,
         size(myFriends) + size([f IN theirFriends WHERE NOT f IN myFriends]) as unionSize

    WHERE unionSize > 0
    WITH candidate,
         intersectionSize,
         toFloat(intersectionSize) / unionSize as jaccardSimilarity

    WHERE jaccardSimilarity > $threshold
    RETURN candidate, jaccardSimilarity, intersectionSize as mutualFriends
    ORDER BY jaccardSimilarity DESC
    LIMIT $limit
    """)
List<SimilarityResult> findSimilarUsers(String username, double threshold, int limit);

Jaccard 유사도는 0에서 1 사이다. 0.1-0.2의 임계값은 보통 노이즈를 필터링하면서 관련 제안을 유지한다.

6. 콜드 스타트 문제

새 사용자는 친구가 없어서 친구 기반 추천이 실패한다. 폴백 전략으로 처리한다:

public List<User> getRecommendationsForNewUser(String username, int limit) {
    User user = userRepository.findByUsername(username)
        .orElseThrow(() -> new UserNotFoundException(username));

    // Strategy 1: Same location
    if (user.getLocation() != null) {
        List<User> localUsers = userRepository.findPopularUsersInLocation(
            user.getLocation().getId(), limit);
        if (!localUsers.isEmpty()) {
            return localUsers;
        }
    }

    // Strategy 2: Shared interests
    if (!user.getInterests().isEmpty()) {
        List<User> interestMatch = userRepository.findUsersBySharedInterests(
            username, limit);
        if (!interestMatch.isEmpty()) {
            return interestMatch;
        }
    }

    // Strategy 3: Popular/active users
    return userRepository.findMostActiveUsers(limit);
}

@Query("""
    MATCH (u:User)-[:LIVES_IN]->(:Location {id: $locationId})
    WHERE u.status = 'ACTIVE'
    OPTIONAL MATCH (u)<-[:FOLLOWS]-(follower)
    WITH u, count(follower) as followerCount
    ORDER BY followerCount DESC
    LIMIT $limit
    RETURN u
    """)
List<User> findPopularUsersInLocation(Long locationId, int limit);

@Query("""
    MATCH (me:User {username: $username})-[:INTERESTED_IN]->(interest)
          <-[:INTERESTED_IN]-(other:User)
    WHERE other <> me AND NOT (me)-[:FRIENDS_WITH]-(other)
    WITH other, count(interest) as sharedCount
    ORDER BY sharedCount DESC
    LIMIT $limit
    RETURN other
    """)
List<User> findUsersBySharedInterests(String username, int limit);

7. Neo4j Graph Data Science (선택사항)

대규모 추천을 위해 Neo4j의 Graph Data Science 라이브러리가 최적화된 알고리즘을 제공한다:

// First, project the graph
@Query("""
    CALL gds.graph.project(
        'social-network',
        'User',
        {
            FRIENDS_WITH: {orientation: 'UNDIRECTED'},
            FOLLOWS: {orientation: 'NATURAL'}
        }
    )
    """)
void projectGraph();

// Node similarity using GDS
@Query("""
    CALL gds.nodeSimilarity.stream('social-network', {
        topK: $topK,
        similarityCutoff: $cutoff
    })
    YIELD node1, node2, similarity
    WHERE gds.util.asNode(node1).username = $username
    RETURN gds.util.asNode(node2) as similarUser, similarity
    ORDER BY similarity DESC
    """)
List<SimilarityResult> findSimilarUsersGDS(String username, int topK, double cutoff);

GDS는 최적화된 알고리즘과 병렬 처리를 사용하여 대규모 그래프에서 유사도를 더 효율적으로 계산한다.

8. REST 컨트롤러

@RestController
@RequestMapping("/api/recommendations")
public class RecommendationController {

    private final RecommendationService recommendationService;

    @GetMapping("/friends")
    public ResponseEntity<List<ScoredRecommendation>> getFriendRecommendations(
            @AuthenticationPrincipal UserDetails user,
            @RequestParam(defaultValue = "10") int limit) {
        return ResponseEntity.ok(
            recommendationService.getFriendRecommendations(user.getUsername(), limit));
    }

    @GetMapping("/people-you-may-know")
    public ResponseEntity<List<UserDto>> getPeopleYouMayKnow(
            @AuthenticationPrincipal UserDetails user,
            @RequestParam(defaultValue = "5") int limit) {
        List<User> suggestions = recommendationService.getPeopleYouMayKnow(
            user.getUsername(), limit);
        return ResponseEntity.ok(suggestions.stream().map(UserDto::from).toList());
    }

    @PostMapping("/dismiss/{username}")
    public ResponseEntity<Void> dismissRecommendation(
            @AuthenticationPrincipal UserDetails user,
            @PathVariable String username) {
        recommendationService.dismissRecommendation(user.getUsername(), username);
        return ResponseEntity.ok().build();
    }
}

9. 추천 캐싱

추천 계산은 비용이 많이 든다. 캐시한다:

@Service
public class CachedRecommendationService {

    private final RecommendationService recommendationService;
    private final Cache<String, List<ScoredRecommendation>> cache;

    public CachedRecommendationService(RecommendationService recommendationService) {
        this.recommendationService = recommendationService;
        this.cache = Caffeine.newBuilder()
            .expireAfterWrite(Duration.ofHours(1))
            .maximumSize(10_000)
            .build();
    }

    public List<ScoredRecommendation> getRecommendations(String username, int limit) {
        return cache.get(username, key ->
            recommendationService.getFriendRecommendations(key, limit));
    }

    public void invalidate(String username) {
        cache.invalidate(username);
    }
}

사용자가 친구를 추가하거나, 관심사를 업데이트하거나, 위치를 변경하면 캐시를 무효화한다.

10. 결론

그래프 기반 친구 추천은 이미 소셜 신호를 인코딩하고 있는 네트워크 구조를 활용한다. 상호 친구가 여전히 가장 강력한 예측 변수지만, 여러 신호를 결합하면 관련성이 향상된다. 새 사용자의 경우 위치, 관심사 또는 인기도로 폴백한다. 대규모에서는 Neo4j의 Graph Data Science 라이브러리가 최적화된 유사도 알고리즘을 제공한다. 이것으로 소셜 네트워크 시리즈를 마무리한다—기본 설정부터 스키마 설계, 관계, 피드, 추천까지.