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. Credit: SUTD

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 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 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, their behavior? Does each of them influence their contacts independently or are their behaviors 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 influence their contacts independently of others.

However, there could be hidden correlations in their behavior 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).

"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.

More information: Correlation Robust Influence Maximization, papers.nips.cc/paper/2020/file … ad3e9ea4ee-Paper.pdf