How Do Ideas Spread
Through Networks?
I find dynamics on networks very interesting. Before starting graduate school, in 2018, a library near me was giving away free books. One of which was Social and Economic Networks by Mathew Jackson. The book opens with the story of Italy's Medici family in Florence. In the early 1400s, the Medici were not the most established or the wealthiest family in Florence; the Strozzi and Albizzi families were their major rivals and arguably held more traditional prestige. However, by 1434, Cosimo de' Medici had effectively consolidated power and became the de facto ruler of the city. Jackson demonstrates how Medici's high Betweenness Centrality helped the family consolidate power by controlling the flow of resources and information.
I was deeply fascinated by how your position in the network, and how this network is structured, can have a consequential impact on your life. This interest was resurfaced in 2020 during the COVID-19 pandemic. I started to read more about epidemiology, network science, and computational social science in general. I was curious to understand how our social ties determined if you get infected or not. So when I joined graduate school, I jumped at the chance to work on some problems in network science. One of which is the Influence Maximization problem. Here goes-
Influence Maximization (in brief)
Network
Imagine a social network. Here, each person is a node. They are connected to another node, with an edge if they are friends. Here, we can see a few communities.
What is a Contagion?
A contagion is anything that spreads on a network through edges. For example, an idea, a virus, a rumor. There are many ways this information can be spread. For example, you can infect a friend with a fixed probability, p. Or, you can infect your friend with a higher probability if they have also have lot of friends that are infected.
In this walkthrough, we will just focus on transmissions with fixed probabilities.
Whom to Infect?
In your group, whom would you tell a rumor, such that everybody finds out? The node that is seeded in the network has a huge impact on how the outbreak size. For instance, removed from any community, and not many friends, will likely not have a huge influence. However, a node that bridges two communities (cue, the Medici family) will infect a lot more people.
The Influence Maximization Problem
Finding the most influential person is easy. You tell your secret to everybody and figure out how many people find out. (𝒪(n)) Now, instead of one person, you can tell your secret to k people. How do you pick those people? It blows up fast. (𝒪(C(n,k))). That's the problem.
How Do We Solve It?
Since we cannot try every combination, we need smarter strategies. Two main families of approaches exist:
Greedy algorithms — slow but with theoretical guarantees.
Heuristic methods — faster but approximate, like genetic algorithms that evolve solutions over generations.
The Greedy Approach
The greedy algorithm builds its seed set one person at a time. First, we simulate spreading from every node and picks the best node. Next, we fix that choice and seed the infection with that node and every other node. And so on.
This guarantees a solution within 63% of the true optimum (a mathematical bound of 1 − 1/e). But it requires running thousands of simulations, and each round tests every remaining node. This is still expensive.
Our Approach: Neighbor-Hop Mutation
We use a genetic algorithm. The algorithm start with a population of random seed nodes and evolve this population over generations through mutation and selection. Also why it is called an Evolutionary algorithm. The key innovation is in our work is how we mutate.
Standard Mutation
Standard mutation replaces a seed with a random node anywhere in the network. This often destroys what made a solution good.
Neighbor-Hop Mutation
By "walking" along edges instead of jumping randomly, the algorithm preserves structural quality while efficiently searching for improvements. In our experiments, it consistently matched or beat the greedy baseline — in a fraction of the time.
Key Takeaway
Network structure matters — not just for how contagions spread, but for how we design algorithms to study them. By making mutations "network-aware," we can find better solutions faster.