Celebrity

In the context of computer science, „celebrity“ often refers to a specific type of problem or concept in graph theory and social network analysis. A celebrity is defined as an individual within a social network who is known by everyone else but does not know anyone in return.

Formally, in a directed graph where vertices represent individuals and edges represent knowledge (an edge from A to B indicates that A knows B), a celebrity is a vertex C such that:
1. For every individual A (other than C), A knows C.
2. C does not know any individual A.

The celebrity problem involves determining whether a celebrity exists within a group and, if so, identifying who it is, typically through a series of queries (e.g., determining if one individual knows another).

This problem is often used as a programming exercise to test understanding of data structures and algorithms, as it can be solved efficiently with an optimal approach that reduces the number of required comparisons.