Celebrity

In computer science, the term „celebrity“ often refers to a specific type of problem or concept in social network analysis. The celebrity problem is a scenario in which a group of people is present, and one person can be identified as a „celebrity“ if they are known by everyone else in the group, but they do not know any of them in return.

This concept is formalized in the context of a directed graph, where nodes represent individuals and directed edges represent the knowledge of one person by another. The celebrity can be defined using the properties of this graph: a person is a celebrity if they have incoming edges from all other nodes and no outgoing edges to any other nodes.

The celebrity problem is often used to illustrate algorithms for finding the celebrity efficiently, typically in O(n) time complexity, where n is the number of people in the group. There are various approaches to solve this issue, including stack-based algorithms or iterative comparisons. The problem is often presented in programming contests and is a popular example of algorithm design and analysis in computer science.