Last week, Social Network Analysis and Mining published a new research article that I coauthored with a few colleagues—my first published data science paper. We did the work itself quite a while ago as part of a high-performance computing project, and my gratitude goes to Hautahi for steering the paper to completion.
In the article we studied the problem of Influence Maximization, a subfield of social network analytics and network science that searches for ways of identifying the most influential entities in a network (think Instagram ‘influencers’ 🙄). This kind of problem turns out to be a computational nightmare, and so most approaches are either heuristic—seeming to work well in practice but not mathematically guaranteed to return good solutions—or are only proven to provide OK solutions. This second group of so-called “provable” algorithms typically guarantee solutions within % of the best possible answer. It’s still possible that they give a perfect solution in a given case, but it’s only assured that their solutions will be close to optimal.
In the paper we took a really fast algorithm, tweaked it to provide brute-force calculations of the exact1 solution, and implemented it using HPC and GPUs. Then we compared various approximate approaches to the exact solution: do they only give 63%-optimal solutions, or do they perform better in practice? It turns out they perform extremely well on our test networks, representing common cases. There are likely pathological networks out there, but the techniques perform well with common graph constructions.
The paper is available through SNAM, and Hautahi has provided source code, a workshop presentation, and a preprint through his website.
-
As exact as you can get using a Monte Carlo approach. ↩︎