Most entrepreneurs with a pioneer product face a common set of challenges - knowing how their product would be received in the market, finding the best strategy to advertise it and identifying the initial set of “seed users” who would use the product and provide feedback on its improvements. In the age of social media where information diffuses at massive speeds, how should one identify the set of users who have the maximum influence in reaching out to a larger crowd? In a recent collaborative study, researchers at the Indian Institute of Science, Bangalore and IBM India Research Labs have studied how information diffuses on social networks and have identified strategies to answer this question.
Dynamics of social networks are of great interest to computer scientists who try to understand the parameters affecting interactions on various social networks. They formulate and analyse such problems in the language of graph theory. A ‘friendship-network’ on Facebook is a good example of a social network where individuals are represented by ‘nodes’, and two nodes are ‘connected’ if the individuals representing them are friends with each other. Other forms of social networks may have different criteria for the nodes to be connected. Information diffuses across a network through the connections between nodes.
A central question on information diffusion is - which nodes should one choose from the network to maximise information diffusion, given a constraint on the the number of nodes to choose? Most of the existing literature assumes that diffusion starts, or is ‘triggered’, at all nodes in one go. This study, led by Mr. Swapnil Dhamal and Prof. Y. Narahari at the department of Computer Science and Automation, IISc and Dr. Prabuchandran K. J. from IBM India Research Labs, looked into the effects of triggering the seed nodes in two phases. Understandably, the diffusion would be greater in the latter case, since one could choose, in the second phase, those nodes whose vicinities have not been triggered in the first phase. A two-phase diffusion requires ‘budgeting’ the total number of nodes between the two phases, where a few nodes are allocated to the first phase and the rest to the second, and also ‘scheduling’ the second phase.
The first step in analysing information diffusion in a network is to define an objective function - a relationship between the decision variables and the extent of diffusion. To begin with, the researchers assumed a certain allocation of nodes between the two phases and formulated an objective function that balances accuracy and ease of computation. This function is a far-sighted function, meaning that it looks ahead how diffusion would proceed in the first phase and which nodes need to be selected in the second phase, based on observations in the first. Then, they explored algorithms to optimise the objective function.
To demonstrate the efficiency of the proposed method, the team tested it with extensive computer simulations over a standard large network dataset. The results showed that although a two-phase process performs better under the standard setting of no time constraints, there is a delay before the second phase is triggered. Hence, under a strict time constraint, the single-phase process fared better. Even in the absence of time constraints, a wise allocation of nodes for each of the phases maximised the benefit. It was also found that the set of “seed nodes” that were identified in the first phase were very influential in directing the diffusion, and a budget split of 1:2 nodes for the first and the second phases is optimal.
In an era of rapid expansion of social media, targeted advertisement is not only feasible, but also lucrative. To implement it, one needs to understand dynamics of social networks accurately. “Currently, most studies assume simplistic models for information diffusion which cannot capture the complex social interactions that take place over multiple channels of varying degrees. Developing reliable models for information diffusion remains an open problem. Until then, entrepreneurs won’t mind using the current research as long as it fetches them profits,” says Mr. Swapnil Dhamal, a member of the study group, reflecting on the research.
About the researchers and publication:
Swapnil Dhamal is a Ph.D. student and Prof. Y. Narahari is a Professor at the department of Computer Science and Automation at IISc, Bangalore. Dr. Prabuchandran K. J. is a Research Scientist at IBM India Research Labs in Bangalore. The authors can be contacted via e-mail. Prof. Y Narahari - firstname.lastname@example.org, Swapnil Dhamal - email@example.com.
The paper “Information diffusion in Social Networks in Two Phases” was published in IEEE Transactions on Network Science and Engineering.