Limiting the diffusion of information by a selective PageRank-preserving approach

Loukides, Grigorios ORCID: https://orcid.org/0000-0003-0888-5061 and Gwadera, Robert 2016. Limiting the diffusion of information by a selective PageRank-preserving approach. Presented at: IEEE International Conference on Data Science and Advanced Analytics, Montreal, Canada, 17-19 October 2016. Data Science and Advanced Analytics (DSAA), 2016 IEEE International Conference on. IEEE, pp. 90-99. 10.1109/DSAA.2016.16

Preview

PDF - Accepted Post-Print Version Download (543kB) | Preview

Abstract

The problem of limiting the diffusion of information in social networks has received substantial attention. To deal with the problem, existing works aim to prevent the diffusion of information to as many nodes as possible, by deleting a given number of edges. Thus, they assume that the diffusing information can affect all nodes and that the deletion of each edge has the same impact on the information propagation properties of the graph. In this work, we propose an approach which lifts these limiting assumptions. Our approach allows specifying the nodes to which information diffusion should be prevented and their maximum allowable activation probability, and it performs edge deletion while avoiding drastic changes to the ability of the network to propagate information. To realize our approach, we propose a measure that captures changes, caused by deletion, to the PageRank distribution of the graph. Based on the measure, we define the problem of finding an edge subset to delete as an optimization problem. We show that the problem can be modeled as a Submodular Set Cover (SSC) problem and design an approximation algorithm, based on the well-known approximation algorithm for SSC. In addition, we develop an iterative heuristic that has similar effectiveness but is significantly more efficient than our algorithm. Experiments on real and synthetic data show the effectiveness and efficiency of our methods.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Published Online
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher:	IEEE
ISBN:	9781509052073
Funders:	Royal Academy of Engineering
Date of First Compliant Deposit:	13 September 2016
Date of Acceptance:	31 July 2016
Last Modified:	01 Nov 2022 11:18
URI:	https://orca.cardiff.ac.uk/id/eprint/94487

Citation Data

Cited 2 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item