  Influence Maximization (IM), which aims to select a set of users from a
social network to maximize the expected number of influenced users, has
recently received significant attention for mass communication and commercial
marketing. Existing research efforts dedicated to the IM problem depend on a
strong assumption: the selected seed users are willing to spread the
information after receiving benefits from a company or organization. In
reality, however, some seed users may be reluctant to spread the information,
or need to be paid higher to be motivated. Furthermore, the existing IM works
pay little attention to capture user's influence propagation in the future
period as well. In this paper, we target a new research problem, named
Reconnecting Top-l Relationships (RTlR) query, which aims to find l number of
previous existing relationships but being stranged later, such that
reconnecting these relationships will maximize the expected benefit of
influenced users by the given group in a future period. We prove that the RTlR
problem is NP-hard. An efficient greedy algorithm is proposed to answer the
RTlR queries with the influence estimation technique and the well-chosen link
prediction method to predict the near future network structure. We also design
a pruning method to reduce unnecessary probing from candidate edges. Further, a
carefully designed order-based algorithm is proposed to accelerate the RTlR
queries. Finally, we conduct extensive experiments on real-world datasets to
demonstrate the effectiveness and efficiency of our proposed methods.
