Essec Business School

Analyzing the relationships between people can reveal valuable patterns in how groups function. Two recent studies explore what can be learned while protecting privacy, the limits of this ambition, and the role of collective choices.

Imagine a company that wants to understand how its teams work together. By examining interactions among employees, it hopes to identify informal working groups that do not appear on the organizational chart and to improve the flow of information. Yet the same analysis could also reveal relationships that employees would rather keep private. How can a group’s inner workings be studied without subjecting its members to surveillance?

The difficulty lies in the nature of the data. Every relationship involves at least two people. Even when the goal is simply to understand the bigger picture, the information still concerns individuals. Insights intended to improve collaboration could later be used to assess individual behavior.

Replacing names with numbers may seem like a sensible first precaution. But in this example, someone familiar with certain interactions might still identify an employee from the pattern of their connections. Removing names therefore leaves a crucial question unanswered: what might the findings reveal about the people whose data contributed to the analysis?

This question is at the heart of two studies conducted by Olga Klopp, a professor at ESSEC Business School. The first was co-authored with Ilias Zadik of Yale University. The second also involved Laurentiu Marchis and Po-Ling Loh of the University of Cambridge. Together, the researchers investigated community detection in networks under mathematically defined privacy constraints.

Protecting a person—and all their connections

In a network, people are represented by points and their relationships by links. Protecting a single link is not the same as protecting every connection associated with one person. Professor Klopp and her co-authors focus on the second, stronger form of protection.

Professor Klopp explains: “We use differential privacy. Its basic principle is to compare the probabilities of possible results from two datasets that differ only in one person’s protected information. These probabilities must remain close, within a specified bound. The algorithm introduces randomness to achieve this: it may produce different answers rather than always returning the same one. The protection concerns how an individual’s data can influence the results.”

The strength of this guarantee is governed by a parameter known as the “privacy budget.” The smaller the budget, the stronger the protection. A larger budget permits greater differences between the probabilities of possible outcomes and may allow for more accurate results. It does not represent the percentage of people whose privacy is protected.

This guarantee does not mean that every piece of information about an individual becomes impossible to infer. Findings about a group may still reveal something about one of its members, based on what is already known about the group. Differential privacy limits the effect of that individual's own contribution to the data.

Establishing what is possible—and where the limits lie

Dr. Klopp and her co-authors study networks generated by a probabilistic model in which individuals belong to groups and connections are more likely to form within a group than between groups. This simplified setting makes it possible to establish precise mathematical guarantees.

The goal is particularly demanding: to recover the groups and correctly identify which group every individual belongs to. Known as “exact recovery,” this goes far beyond identifying broad patterns.

The first study shows that exact recovery remains possible under suitable conditions on the strength of the signal and the level of privacy protection. It also establishes limits that apply to any method satisfying the privacy requirement under consideration, regardless of its computational power.

One finding is especially important. To make the probability of even a single incorrect group assignment sufficiently small as the network grows, the privacy budget must increase at least on the order of the logarithm of the network size. In other words, the privacy guarantee has to become less stringent.

A proven limit changes the terms of the debate. In the setting examined, it is not possible to demand both this level of accuracy and an unchanged privacy budget while hoping that a better algorithm will somehow reconcile the two. Instead, the requirements themselves must be reconsidered.

For an organization, this means being clear about what it really needs to know. Must it assign every employee to a particular group, or is the aim to understand the main barriers to collaboration? These are different goals and call for different measures of success. The findings on exact recovery do not, by themselves, establish the limits of every form of collective analysis.

Using research to inform collective decisions

These studies suggest that project managers need to first identify the intended use of an analysis, rather than with the technology. In this hypothetical company, the person leading the project should be able to explain why data about relationships are needed, what level of accuracy would be useful, and who will have access to the results. A map of collaboration patterns intended to improve communication serves a very different purpose from a ranking of employees. Their value and their consequences need to be considered separately.

It is also important to ask exactly what a promise of privacy protection covers. Does it protect a single interaction or all of one person’s connections? What privacy budget has been chosen? What level of accuracy is claimed, and for what kinds of networks has it been established? These questions make it possible to compare concrete proposals. The label “privacy-preserving” alone tells little about the trade-off being made.

Finally, if stronger privacy protection makes an analysis less accurate, that loss of accuracy must be judged in light of how the results will be used. When redesigning an organization, a few incorrect group assignments might be acceptable. But when a decision directly affects an individual, the same errors could carry much greater weight. What matters is what will be done with the findings, who will be affected, and what the consequences may be.

Mathematics can draw a boundary between what is possible and what is not. It cannot decide how much privacy protection a company or a society should accept. That decision requires weighing the value of the knowledge being sought against what people are prepared to reveal in order to obtain it.

Understanding how a group functions without unnecessarily exposing its members therefore requires a clearly defined objective and an explicit privacy guarantee. Before asking data to reveal everything they can, it is worth deciding what would be useful and legitimate to ask. Scientific results provide concrete limits for that discussion; responsibility for the choices remains collective.

References

Olga Klopp and Ilias Zadik (2026). “Node-Private Community Detection in Stochastic Block Models.” Preprint. https://arxiv.org/abs/2604.09078

Laurentiu Marchis, Olga Klopp, Po-Ling Loh, and Ilias Zadik (2026). “Near-optimal node-private community estimation in polynomial-time.” Preprint. https://arxiv.org/abs/2607.09441

For a general introduction: Cynthia Dwork and Aaron Roth (2014). “The Algorithmic Foundations of Differential Privacy.” https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf