In network science, we often ask "who is connected to whom?" This question leads us to community detection, where we find clusters of nodes that are densely connected, like a group of friends in a high school or a cluster of web pages on the same topic.
However, there is a second, equally important question: "what does this node do?" This is the domain of role discovery. While community detection looks for proximity, role discovery looks for structural similarity. Two nodes might be on opposite sides of the world, but if they both act as "hubs" for their local communities or "bridges" between disconnected groups, they share the same structural role.
The Intuition: Proximity vs. Behavior
The fundamental difference between communities and roles is best understood through an analogy. In a corporate network, community detection identifies which department you work in (e.g., Marketing or Engineering). Role discovery identifies your job title (e.g., Manager or Intern).
As Keith Henderson and colleagues argue in their work on RolX RolX: Role Extraction and Mining in Large Networks, traditional analysis often conflates these two. But identifying roles allows for "sense-making" that transcends specific identities. If you understand the role of a "bridge" node in a social network, you can find the equivalent "bridge" in a protein-interaction network, even though the nodes and edges represent entirely different things.
Defining Structural Equivalence
How do we mathematically define "acting the same"? Researchers use several levels of "equivalence" to group nodes:
- Regular Equivalence: Two nodes are equivalent if they are connected to nodes that are themselves equivalent. As Amirreza Masoumzadeh and James Joshi explain, this allows us to identify functional positions—like "managers" who oversee "workers"—independent of the specific individuals involved Preserving structural properties in anonymization of social networks.
- Stochastic Equivalence: This is a probabilistic version of the same idea. Xuan Guo and collaborators recently proposed using discrete Ricci curvature to model the distribution of a node's neighborhood, allowing for role discovery that is more robust to the noise found in real-world data Learning Stochastic Equivalence based on Discrete Ricci Curvature.
- Equitable Partitions (EP): A more rigorous mathematical framing involves partitioning nodes such that every node in a group has the same number of neighbors in every other group. Michael Scholkemper and Michael T. Schaub developed optimization frameworks to approximate these partitions, providing a benchmark to finally separate role discovery from local density An Optimization-based Approach To Node Role Discovery in Networks: Approximating Equitable Partitions.
Flow Profiles in Directed Networks
In directed networks—where edges represent the flow of information, money, or energy—roles become even more distinct. Kathryn Cooper and Mauricio Barahona introduced the concept of flow profiles Role-based similarity in directed networks.
Instead of just looking at who a node points to, they analyze the patterns of incoming and outgoing paths across all lengths. This reveals structural hierarchies, such as "trophic levels" in a food web or "broadcasters" versus "engagers" in social media networks like Twitter Communities, roles, and informational organigrams in directed networks.
Embedding Roles into Vector Space
To use these roles in machine learning, we must represent them as vectors. Traditional node embeddings (like DeepWalk) place nodes that are near each other close together in vector space. Role-preserving embeddings do the opposite: they place nodes with similar functions close together, even if they are far apart in the graph.
- struc2gauss: Yulong Pei and colleagues developed a method that maps nodes to Gaussian distributions rather than points struc2gauss: Structural role preserving network embedding via Gaussian embedding. This captures the inherent uncertainty and noise in structural roles.
- Recursive Aggregation: Wenwu Zhu and Peng Cui highlight that by processing neighborhood information through recursive sequences rather than simple averaging, deep learning models can better capture the "regular equivalence" required to identify hubs and bridges Deep Learning for Learning Graph Representations.
Why It Matters: Network Cartography
The ultimate goal of role discovery is to create a "map" of a network that is actually readable. Jia Wang and Hari Sundaram call this Network Cartography Network Cartography: Seeing the Forest and the Trees.
By modeling landmarks as functional roles rather than just dense communities, we can zoom out to see the "forest" (the global architecture of how roles interact) without losing the "trees" (the individual nodes). This approach has been used to identify the structural influence of academic disciplines Author multidisciplinarity and disciplinary roles in field of study networks and even to compare the social architectures of different TV sitcoms Similar Yet Different: the Structure of Social Networks of Characters.