Determining the most important node of a graph depends on your definition of importance. This definition itself depends on the goal you are trying to achieve. In this chapter, we will study two examples of importance:
- Information spread within a social network
- Critical nodes in a road or computer network
We will learn that each of these problems can be tackled with centrality algorithms. In this section, we will consider the following graph as an example to help us understand the different definitions of importance:
Which node is the most important in this network? The answer depends on what important means in a given context. Let's consider the different ways of defining importance.
Popularity and information spread
The most obvious way to define importance is with the influencer concept. Most influential nodes have many connections and, as such, are well placed to spread information. In the context of social networks, influencers often get offered advertising...