A study in Indian Institute of Science has yielded an algorithm that can allow companies to advertize their products, or political parties to campaign over social networks within a fixed budget. The algorithm ensures that the campaign reaches maximum people, through an optimal combination of mass media broadcasts and providing incentives to people having good social contact.
Social media has become part and parcel of life over the last decade. Most of us use it not only as a tool to get in touch with friends, relatives and colleagues, but also as a source of information. It is not surprising that companies are increasingly taking to social media to advertise their products; recently, politicians have been using it for election campaigns.
To reach out to the public, advertising or political campaigners may use two strategies: broadcasting over mass media like radio and television, or relying on a few people to spread the information to their social contacts, and allow the information to gradually disseminate. Such propagation of information is quite analogous to the spread of a disease across the population through infections. This phenomenon has been studied quite extensively using a mathematical concept called “graph”. A graph comprises of points (called nodes), pairs of which may be joined by lines (called edges). These ideas can be used to model information dissemination over social networks. This is what Kundan Kandhway, a graduate researcher in the Indian Institute of Science (Bangalore) has been investigating, under his advisor Prof Joy Kuri.
The problem with broadcasting over the mass media is that it is expensive, while dissemination via social contacts is slow and unpredictable. The campaigners have the option of providing some incentive to people for spreading the message. The big question is how to select the right strategy, so that the campaigners may expect the information to spread rapidly through the population, under a limited budget. Kundan says, "By allocating campaigning resources non-uniformly over the campaign duration, like incentivizing and directly reaching out to a few influential individuals, one can achieve considerable savings over simple uniform allocation to everyonethe strategy that simply allocates the resources uniformly over the campaign duration to all individuals”.
The researchers have attempted to model the social network by representing it as a graph, and using broadcast costs, incentives and information spreading rate as unknown variables. They divide the entire duration of the campaign into a fixed number of time-slots to simplify their algorithm. In each time-slot, the people are categorized as “infected” (those who have already received the campaign's message), and “susceptible” (those who have not received it yet). Incentives need to be decided for the “infected” users, so that they can spread the message to their “susceptible” friends on social media. It is expected that the persons with more social contacts will be able to disseminate the information more effectively than those with few contacts. On the other hand, not every person will be interested in joining the campaign. It may make sense to give incentives to more connected people to spread the message, as they may do it more effectively.
The researchers propose dividing “infected” people into groups based on number of contacts, For each group an incentive is computed, and this is done in very time-slot. At the same time, a limited part of the budget may also be spent on directly reaching out to the people by mass media broadcasts, instead of propagation over social media. The final aim is that at the end of the campaign duration, the number of “infected” people should be maximized, without exceeding the budget for broadcasts and incentives. The researchers solved an optimization problem to find the “optimal solution”, i.e. the most appropriate strategies to ensure swift spreading of information within the budget.
According to Kundan, the campaigners need to figure out details about the scenario to deploy the algorithm effectively. "The networks may be homogeneous or heterogeneous. Also the interest generated among people may vary from one campaign to another. The budget is another factor. One should know these variables before starting the campaign."
The researchers have tested their algorithm on various simulated graphs which, according to them, model real-life social networks quite well. The graphs are quite heterogenous, i.e. number of social media friends vary considerably over the population. They carried out extensive testing, where they study the effects of incentivizing different user groups, timing of incentivization, budget constraints, probability of information propagation etc. They found that incentivizing and direct broadcasting are more important at the early stages of the campaign than later. Also, they found that in heteogenous networks, it is best to target the most connected people (having high “degree”) for incentivization, but in homogeneous networks, targeting moderately connected ones may be better. As a future direction, they want to explore measures other than “degree” to group the users. They are also planning to test their algorithm on real social networks.
About the authors:
Prof Joy Kuri is a Professor at the Department of Electronic System Engineering. Kundan Kandhway is a PhD scholar with Prof Kuri.
Phone: +91 80 23600810 Ext 228 / +91 80 22933091
About the paper: The work has been published IEEE/ACM Transactions on Networking, a leading international journal.