The authors of this paper start their text with a challenging problem in the area of graph mining with applications in various disciplines: Given a large graph, which edges should be deleted or added so as to affect the propagation of a network?
Due to the rapid proliferation of online social networks, this problem has recently gained a lot of attention. In this paper, the authors formally define this problem as one of eigenvalue optimization and provide an elegant solution. Specifically, the main idea of this work is to use the changes on the leading eigenvalue of the directed graph to control or speed up the dissemination process. Their method selects edges between nodes that create the largest decrease (for edge deletion) or increase (for edge addition) of the leading eigenvalue of the graph. In this framework, the authors present two algorithms to solve the introductory problem, followed by a theoretical analysis of their effectiveness and efficiency. In addition, the authors provide empirical evaluations on real topologies. The proposed algorithms seem to work well in practice.
The paper is well organized and the authors (who are authorities in this area) have made a significant intellectual contribution to the study of the most cost-effective way to reduce or increase the entity dissemination ability of a large-scale network. Data mining researchers and data analysts will find it worthwhile. The target audience includes graduate students and researchers with a theoretical background in computer science and graphs. Although there are a lot of formulas, the paper is well written and the formalization does not make the reading hard for practitioners.