The “Smaller is Smarter” Approach to Networks
In networks, many times it’s important to identify a minimal set of influential nodes. In other words, how can we target some small subset of nodes in a graph so that we can most efficiently and effectively spread influence? While “influence” is an extremely vague term, it can apply to a multitude of different real-life scenarios. For instance, social media marketers want to choose an initial set of people to best spread information about their products, or we may want to selectively immunize a small group of people to help prevent the spread of disease.
Unfortunately for us, identifying the minimal set of influential nodes is an NP-hard problem. Thus, we must turn to heuristics and algorithms that can only give approximations of the optimal solution if we want to solve this problem in a reasonable amount of time. Among some of these heuristics, in the past it was thought that the more strongly connected a node is in a network, the greater chance that this is one of nodes in the solution subset. However, some new research has seemingly contradicted this widely-held idea.
In the article “Influence maximization in complex networks through optimal percolation”, the authors came up with a new algorithm to find an optimal set of influential nodes. After studying their algorithm, they noticed that the subset of nodes returned did not necessarily have strong connectedness to the rest of the graph. That is, nodes with only several edges might actually have a greater influence in a network compared to nodes that have many edges. The following picture illustrates this concept – many of the nodes have the same number of edges as the center node, but due to its strategic location, this node is one of the more influential ones.
These findings are very interesting because they fundamentally change our perspective on what actually makes nodes influential in a graph. Rather than the “bigger is better” approach, we can see that “smaller is smarter” is perhaps the better expression in this case. Until we prove whether or not P = NP, perhaps these findings will allow us to write even better approximation algorithms to these types of problems, and give us more insight into how networks function.
http://lev.ccny.cuny.edu/~hmakse/CI6.pdf