|Talks|

Approximating the Maximum Independent Set Problem Using Lotka-Volterra Dynamics

Visiting speaker
Hybrid
Past Talk
Niek Mooij
Utrecht University
Wed, Sep 13, 2023
7:30 PM UTC
Wed, Sep 13, 2023
7:30 PM UTC
In-person
4 Thomas More St
London E1W 1YW, UK
The Roux Institute
Room
100 Fore Street
Portland, ME 04101
Network Science Institute
2nd floor
Network Science Institute
11th floor
177 Huntington Ave
Boston, MA 02115
Room
58 St Katharine's Way
London E1W 1LP, UK

Talk recording

Systems of ordinary differential equations (ODEs) are rarely thought of as a means of discrete computations. We consider finding the maximum independent set in a complex network, which is known to be a computationally demanding (NP-hard) problem. This problem is at the heart of many real-world computations, e.g., the more efficient invention of new drugs, communication systems, and information flows. We construct an approximate solution by exploring the limiting behavior of ecology dynamics under constant interacting species assumption. We see that we can generate maximal independent sets in any complex network, and we show numerical performance results.

About the speaker
Niek Mooij is a PhD student from Utrecht University, located in the Netherlands. After studying physics and mathematics, Niek started a PhD in network theory with Ivan Kryven. He is currently a visiting student at the Center for Complex Network Research at Northeastern University. Niek is fascinated by the intricate relationship between dynamical systems and underlying network topology, as well as the diverse network characteristics that influence their behavior. In addition to this fundamental interest, he is driven by the practical applications of complex systems and network theory, such as their potential to approximate combinatorial optimization problems.
Share this page:
Sep 13, 2023