Maximizing Contrasting Opinions in Signed Social Networks

Maximizing Contrasting Opinions in Signed Social Networks

A summary of the IEEE BigData 2019 research paper by Kaivalya Rawal and Arijit Khan.

Background: A central characteristic of social networks is that it facilitates rapid dissemination of information among large groups of individuals [1]. Online social networks, such as Facebook, Twitter, LinkedIn, Flickr, and Digg are used for spreading ideas and messages. Users’ behaviors and opinions are highly affected by their friends in social networks, which is defined as the social influence. Motivated by various real-world applications, e.g., viral marketing [2], social and political campaigning [3], social influence studies have attracted extensive research attention. The classic influence maximization problem [4], [2] identifies the top-k seed users in a social network such that the expected number of influenced users in the network, starting from those seeds and following an influence diffusion model, is maximized. The budget k on the seed set size usually depends on how many initial users the campaigner can directly influence by advertisements, re-tweets from “bots”, free samples, and discounted prices.

Problem: We investigate a novel influence diffusion problem: COSiNe (Contrasting Opinions Maximization in a Signed Social Network). We find limited influential seed nodes which maximize the adoption of two distinct, antithetical opinions in two non-overlapping user groups with opposing views. The objective behind such influence maximization is to create awareness in a population by improving the quality of the debate on naturally contentious issues.

Applications: An ideal application of our problem would be to increase awareness about infrequently discussed issues that are nonetheless controversial (such as capital punishment, nuclear energy, or affirmative action) — in a target population that naturally splits into two distinct ideological groups (such as democrats and republicans); in a forum that extensively debates topics and proposes mutually agreeable solutions based on compromise, diversity, and inclusion (such as the United States Senate or House of Representatives). Contrary to initial expectations, polarization of opinions and increased conflict can often be beneficial [5], [6], [7], [8], as discussed in the following.

The benefit of conflicting opinions among collaborators has been clearly observed in Wikipedia. Controversial articles such as those on the Syrian Civil War, Israel/Palestine, or George W. Bush attract a higher number of edits. Higher polarization in the contributing community is associated with higher article quality for a broad range of articles – from politics to science and social issues [6]. Increased diversity is often correlated also with greater business performance. Similarly, disagreements amongst co-workers have been found to improve the decision making capabilities at the organisation level. Thus, encouraging different opinions about the same topic can be leveraged to improve the productivity of the organisation [7]. When dealt with correctly, such differences in thought and opinions are a force for good.

Lastly, we illustrate an example from the world of politics that is most similar to our “ideal” application scenario. Unlike the American presidential system, in countries based upon the Westminster parliamentary system, there is an appointed head of government, different from the head of the state, and an appointed head of opposition. This balance between the government and the opposition is considered integral to the success of a functioning democracy in diverse countries such as in Britain and in India [8]. An equivalent analysis was made for the political system in the United States of America in 1950 by the American Political Science Association [5] which recommended a stronger two party system in order to strengthen the democratic process. Both these analyses point to the importance of opposition in political discourse, and go on to show that policies being enacted and implemented benefit from engagement, and even opposition. Meaningful discourse and spirited debate requires people who inherently hold opposing beliefs on a given issue, and thus maximizing opposing influences can be beneficial for a legislative body from the point of view of the general population.

Challenges: Contrasting opinions maximization, as required in our problem setting, is a non-trivial one. First, one must employ an influence cascade model that has properties different from those for commercial, one-time product purchasing based marketing strategies. For example, people’s opinions change over time; thus, activation based models, such as independent cascade (IC) and linear threshold (LT) models [4] are less appropriate in political contexts. Second, in reality a signed social network might not be perfectly balanced [9], that is, there may not exist a partition V1, V2 of the node set V, such that all edges with V1 and V2 are positive and all edges across V1 and V2 are negative. Such a network does not follow the social balance theory, and adds more complexity to the social influence cascade.

Contributions: In this work, we employ the voter model [9] [10], [11], [12] to characterize influence diffusion in the two population groups of a social network. We define our model such that opposite influences, when applied on the same user, cancel each other, leading to a decay in the influence strength on any given user. Our model does not mandate that a user’s choice be frozen upon one-time activation, explicitly allowing the user to switch opinions at later times. Moreover, voter model, being a stochastic one (it has a random walk based interpretation), can deal with signed networks that are not perfectly balanced. We then formulate our novel COSiNe problem (contrasting opinions maximization), and design an efficient, exact solution.

For more information, click here for our paper.  Codes and datasets: GitHub.

Blog post contributed by: Arijit Khan

  

[Reference]

[1] W. Chen, L. V. S. Lakshmanan, and C. Castillo, “Information and Influence Propagation in Social Networks”, Morgan & Claypool, 2013.

[2] P. Domingos and M. Richardson, “Mining the Network Value Customers”, KDD, 2001.

[3] B. A. Conway, K. Kenski, and D. Wang, “The Rise of Twitter in the Political Campaign: Searching for Intermedia Agenda-Setting Effects in the Presidential Primary”, Journal of Computer-Mediated Communication, vol. 20(4), 2015, pp. 363–380.

[4] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the Spread of Influence through Social Network”, KDD, 2003.

[5] A. Schlesinger JR, “Toward A More Responsible Two-Party System: A Report”, American Political Science Association, 1950.

[6] F. Shi, M. Teplitskiy, E. Duede, and J. A. Evans, “The Wisdom of Polarized Crowds”, Human Behaviour, 2019.

[7] K. Ferrazzi, “The Benefits of Conflict at Work”, 2014, http://fortune.com/2014/03/11/the-benefits-of-conflict-at-work.

[8] A. Beteille, “Democracy and It’s Institutions”, Oxford University Press, Chapter Government and Opposition, 2012.

[9] Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang, “Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships”, WSDM, 2013.

[10] P. Clifford and A. Sudbury, “A Model for Spatial Conflict”, Biometrika, vol. 60(3), 1973, pp. 581–588.

[11] R. A. Holley and T. M. Liggett, “Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model”, Ann. Probab., vol. 3(4), 1975, pp. 643–663.

[12] E. Even-Dar and A. Shapira, “A Note on Maximizing the Spread of Influence in Social Networks”, “Internet and Network Economics”, 2007.