SUTD Develops New Model of Influence Maximization
SUTD - Divya Padmanabhan, Chee Chin Lim and Karthik Natarajan
Naval Postgraduate School Monterey - Louis Chen
The model will enhance the robustness of networks to adversarial attacks and will benefit both practitioners and organizations.
If you were an owner of a newly set-up company, you would most likely be focused on building brand awareness to reach out to as many people as possible. But how can you do so with budget constraints?
These days, businesses have turned to a select group of people who are active on social media platforms as a cost efficient way to drive their promotional efforts. Also referred to as ‘influencers’, they have the ability to influence the opinions or buying decisions of others.
The company would then focus their efforts on influencing the influencers, hoping that, in turn, their product information gets disseminated to the largest possible number of people through these influencers’ wide social media networks.
This process, referred to as ‘influence maximization’ is well studied in social networks and computer science. Most often, one aspires to choose only a small number (let us call this k) of influencers, due to budget considerations.
The important questions to answer would then be; how do companies go about choosing these k influencers? How would they, in turn, model their behaviour? Does each of them influence their contacts independently or are their behaviours somehow linked? What are the computational implications?
Traditionally a popular model in influence maximization has been the independent cascade model wherein the assumption is that all the members in the network influence their contacts independently of others.
However, there could be hidden correlations in their behaviour which are not immediately evident.
In a study led by a team of researchers from the Singapore University of Technology and Design (SUTD), they computed the best k influencers, assuming the correlations between the way the members in the network behave is most detrimental to the company’s interest. Thus the model assumed is of adversarial nature.
The team showed that such a model has computational benefits over an independent cascade model. They also performed a comparison of the set of seed agents chosen by their model versus the set chosen by the independent cascade model.
Their research work also provided a snapshot of their results from a sample network (refer to image).
Results from a sample network. The red nodes denote the influencers chosen by their model. The model tends to choose influencers with relatively larger number of connections and also those belonging to different sub-components of the network.
“Evaluating and enhancing the robustness of networks to adversarial attacks will be important in various domains in the future. This work provides some useful computationally tractable models which can be used by practitioners, agencies and companies in such setups,” said principal investigator Professor Karthik Natarajan from SUTD.
This work ‘Correlation Robust Influence Maximization’ was presented at NeurIPS 2020.
Reference:
Correlation Robust Influence Maximization, 34th Conference on NeurIPS 2020
Acknowledgements:
The research of the SUTD authors was partly supported by the MOE Academic Research Fund Tier 2 grant MOE2019- T2-2-138, “Enhancing Robustness of Networks to Dependence via Optimization”.