Towards Understanding News Plagiarism: Theoretical and Experimental Analysis

In this paper we carry out a step towards understanding news plagiarism and propagation as follows. First, we develop a software that has the ability to crawl various news domains, to collect the news and to carry out similarity search between the collected news. Then, we create a mathematical model for influence in news propagation that uses temporal graphs based on the collected data. We also design a random data generator for the above-mentioned model. We compare the real data with the random generated data and show that they follow the same distribution using four statistical tests. Using the mathematical model that we introduce, we formulate several combinatorial optimization problems whose goal are to maximize various aspects of influence. We theoretically analyze each of these problems and prove NP-hardness and hardness-of approximation results. These results show that, unless P=NP, polynomial time exact algorithms for these problems do not exist. Given the NP-hardness results, we formulate our problems as integer programs and use the state of the art solver, Gurobi, to solve them both on collected data and random generated data. Our experiments show that the results on the real data follow the ones on the generated data of similar size, thus validating the model from a different perspective. We also derive several empirical conclusions on how much budget is necessary in order to get a big influence in the media. Last, but not least, using random generated data, we test the computational limit of our model, namely what is the largest input that is feasible to solve using Gurobi.