Find the Celebrity in a Graph

What is the Celebrity Problem?

The celebrity problem is a classic challenge in graph theory and coding interviews. Imagine you’re in a party with n people. A celebrity is someone who is known by everyone but knows no one in return. Your goal is to identify this person, if they exist.

This problem is modeled as a directed graph using an adjacency matrix, and the solution revolves around concepts like in-degree, out-degree, and efficient candidate identification. In this guide, we’ll break down the problem, explore multiple algorithmic approaches, and answer popular user queries.

Problem Statement: Celebrity in a Social Network

You're given a n x n boolean adjacency matrix M, where M[i][j] = 1 means person i knows person j, and M[i][j] = 0 means they don’t. Your task is to determine whether a celebrity exists in this social network.

To qualify as a celebrity:

• The celebrity knows no one: Their entire row should be zeros.
• Everyone knows the celebrity: Their entire column (except diagonal) should be ones.

This problem can be visualized as finding a node in a directed graph with zero out-degree and in-degree equal to n - 1.

Modeling the Problem with Graph Theory

Adjacency Matrix Representation

The relationships are captured using an adjacency matrix, a common tool in graph theory for representing node connectivity. The rows indicate whom a person knows, and the columns represent who knows them.

In-Degree and Out-Degree Logic

• Out-degree of a node = Number of people the person knows (row sum).
• In-degree of a node = Number of people who know the person (column sum).

A celebrity is a person with:

• In-degree = n - 1
• Out-degree = 0

Naive Solution: Matrix Traversal and Degree Count

One simple way is to traverse the adjacency matrix and compute in-degree and out-degree for each person.

1
2
3
4
5
6
7
8
def findCelebrity(M):
    n = len(M)
    for i in range(n):
        out_deg = sum(M[i])
        in_deg = sum(M[j][i] for j in range(n))
        if out_deg == 0 and in_deg == n - 1:
            return i
    return -1

Time Complexity

• O(n²) due to matrix traversal
• Not optimal for large networks

Optimal Algorithm: Candidate Identification via Elimination

Instead of checking everyone, we eliminate non-celebrities using logical deductions.

Step-by-Step Explanation

1. Start with two people, a and b.
2. If a knows b, then a can’t be the celebrity.
3. If a doesn’t know b, then b can’t be the celebrity.
4. Repeat until one candidate remains.
5. Verify if the candidate meets both conditions.

Python Code for Optimal Solution

1
2
3
4
5
6
7
8
9
10
11
12
def findCelebrity(M):
    n = len(M)
    candidate = 0
    for i in range(1, n):
        if M[candidate][i] == 1:
            candidate = i

    for i in range(n):
        if i != candidate:
            if M[candidate][i] == 1 or M[i][candidate] == 0:
                return -1
    return candidate

Why This Works

This smart algorithm narrows down possibilities in O(n) time. It avoids full matrix traversal and makes decisions using graph theory insights and logical deductions.

Real-Life Analogy: The Celebrity in a Social Network

Imagine a social network like Twitter:

• A celebrity has many followers (high in-degree) but follows no one (zero out-degree).
• By analyzing node connectivity, the celebrity problem mirrors how influence or centrality is measured in social graphs.

Conclusion

The Find the Celebrity problem blends intuition and graph theory into a single powerful challenge. By representing people and relationships using an adjacency matrix, leveraging node connectivity, and applying clever candidate identification strategies, you can efficiently solve what initially seems like a brute-force task.

Whether you're preparing for interviews, working with social network data, or learning about in-degree and out-degree, this problem offers valuable insight into efficient graph-based problem solving.