On social network firewall selection

Anisha Mazumder, Arunabha Sen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


It is common knowledge that the decision of an individual regarding adoption of a product or technology is, more often than not, heavily influenced by their friends and acquaintances. In real world, there are different competing products and innovations that try to garner as many loyal followers as possible. Over the past few years, there has been a significant interest in the research community to study social network problems with a flavor of competition. Such problems often focus on identification of a set of people in a given social network by the competing players in order to achieve some goal. In this paper, we introduce the weighted Segregating Vertex Set (wSVS) problem, in which we are given a weighted undirected graph with a subset of nodes identified as the seedset of the first player and the goal for the second player is to identify a subset of nodes (firewall) of minimum cumulative weight, such that the total weight of the nodes reachable by the first player is strictly less than the total weight of the nodes not reachable by the first player. Thus, the second player tries to contain the reach of the first player within the social network community. This problem is also relevant for containment of disease in epidemiology, containment of forest fire and several other domains. We prove that this problem is NP-complete and provide an optimal solution through the use of Mixed Integer Linear Programming. We also provide a heuristic solution for the wSVS problem and show its efficacy through detailed experimentation. Our heuristic solution delivers near optimal solution in lesser time compared to that needed to find the optimal solution.

Original languageEnglish (US)
Title of host publication2016 International Conference on Computing, Networking and Communications, ICNC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781467385794
StatePublished - Mar 23 2016
EventInternational Conference on Computing, Networking and Communications, ICNC 2016 - Kauai, United States
Duration: Feb 15 2016Feb 18 2016


OtherInternational Conference on Computing, Networking and Communications, ICNC 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications
  • Social Sciences (miscellaneous)


Dive into the research topics of 'On social network firewall selection'. Together they form a unique fingerprint.

Cite this